Keywords

Introduction

Model predictive control (MPC) is a well-known methodology for synthesizing feedback control laws that optimize closed-loop performance subject to prespecified operating constraints on inputs, states, and outputs (Borrelli et al. 2011; Mayne and Rawlings 2009). In MPC, the control action is obtained by solving a finite horizon open-loop optimal control problem at each sampling instant. Each optimization yields a sequence of optimal control moves, but only the first move is applied to the process: At the next time step, the computation is repeated over a shifted time horizon by taking the most recently available state information as the new initial condition of the new optimal control problem. For this reason, MPC is also called “receding horizon control.” In most practical applications, MPC is based on a linear discrete-time time-invariant model of the controlled system and quadratic penalties on tracking errors and actuation efforts; in such a formulation, the optimal control problem can be recast as a quadratic programming (QP) problem, whose linear term of the cost function and right-hand side of the constraints depend on a vector of parameters that may change from one step to another (such as the current state and reference signals). To enable the implementation of MPC in real industrial products, a QP solution method must be embedded in the control hardware. The method must be fast enough to provide a solution within short sampling intervals and require simple hardware, limited memory to store the data defining the optimization problem and the code implementing the algorithm itself, a simple program code, and good worst-case estimates of the execution time to meet real-time system requirements.

Several online solution algorithms have been studied for embedding quadratic optimization in control hardware, such as active-set methods (Ricker 1985), interior-point methods (Wang and Boyd 2010), and fast gradient projection methods (Patrinos and Bemporad 2014). Explicit MPC takes a different approach to meet the above requirements, where multiparametric quadratic programming is proposed to pre-solve the QP off-line, therefore converting the MPC law into a continuous and piecewise-affine function of the parameter vector (:̧def :̧def Bemporad et al. 2002b). We review the main ideas of explicit MPC in the next section, referring the reader to Alessio and Bemporad (2009) for a more complete survey paper on explicit MPC.

Model Predictive Control Problem

Consider the following finite-time optimal control problem formulation for MPC:

$$\displaystyle\begin{array}{rcl} V ^{{\ast}}(p) = \min _{ z}& & \ell_{N}(x_{N}) +\sum _{ k=0}^{N-1}\ell(x_{ k},u_{k}){}\end{array}$$
(1a)
$$\displaystyle\begin{array}{rcl} \mathrm{s.t.}& & x_{k+1} = Ax_{k} + Bu_{k}{}\end{array}$$
(1b)
$$\displaystyle\begin{array}{rcl} & & C_{x}x_{k} + C_{u}u_{k} \leq c{}\end{array}$$
(1c)
$$\displaystyle\begin{array}{rcl} & & \ \ \ \ \ \ k = 0,\ldots ,N - 1 \\ & & C_{N}x_{N} \leq c_{N}{}\end{array}$$
(1d)
$$\displaystyle\begin{array}{rcl} & & x_{0} = x{}\end{array}$$
(1e)

where N is the prediction horizon; \(x \in \mathbb{R}^{m}\) is the current state vector of the controlled system; \(u_{k} \in \mathbb{R}^{n_{u}}\) is the vector of manipulated variables at prediction time k, \(k = 0,\ldots ,N - 1\); \(z \triangleq \left [\begin{matrix}\scriptstyle u\prime_{0}\ \ldots \ u\prime_{N-1}\end{matrix}\right ]\prime \in \mathbb{R}^{n}\), \(n \triangleq n_{u}N\), is the vector of decision variables to be optimized;

$$\displaystyle\begin{array}{rcl} \ell(x,u)& =& \frac{1} {2}x\prime Qx + u\prime Ru{}\end{array}$$
(2a)
$$\displaystyle\begin{array}{rcl} \ell_{N}(x)& =& \frac{1} {2}x\prime Px{}\end{array}$$
(2b)

are the stage cost and terminal cost, respectively; Q, P are symmetric and positive semidefinite matrices; and R is a symmetric and positive definite matrix.

Let \(n_{c} \in \mathbb{N}\) be the number of constraints imposed at prediction time \(k = 0,\ldots ,N - 1\), namely, \(C_{x} \in \mathbb{R}^{n_{c}\times m}\), \(C_{u} \in \mathbb{R}^{n_{c}\times n_{u}}\), \(c \in \mathbb{R}^{n_{c}}\), and let n N be the number of terminal constraints, namely, \(C_{N} \in \mathbb{R}^{n_{N}\times m}\), \(c_{N} \in \mathbb{R}^{n_{N}}\). The total number q of linear inequality constraints imposed in the MPC problem formulation (1) is \(q = Nn_{c} + n_{N}\).

By eliminating the states \(x_{k} = A^{k}x +\sum _{ j=0}^{k-1}A^{j}Bu_{k-1-j}\) from problem (1), the optimal control problem (1) can be expressed as the convex quadratic program (QP):

$$\displaystyle{ V ^{\star }(x) \triangleq \min _{ z}\quad \frac{1} {2}z\prime Hz + x\prime F\prime z + \frac{1} {2}x\prime Y x }$$
(3a)
$$\displaystyle{ \mathrm{s.t.}\quad Gz \leq W + Sx }$$
(3b)

where \(H = H\prime \in \mathbb{R}^{n}\) is the Hessian matrix; \(F \in \mathbb{R}^{n\times m}\) defines the linear term of the cost function; \(Y \in \mathbb{R}^{m\times m}\) has no influence on the optimizer, as it only affects the optimal value of (3a); and the matrices \(G \in \mathbb{R}^{q\times n}\), \(S \in \mathbb{R}^{q\times m}\), \(W \in \mathbb{R}^{q}\) define in a compact form the constraints imposed in (1). Because of the assumptions made on the weight matrices Q, R, P, matrix H is positive definite and matrix \(\left [\begin{matrix}\scriptstyle H&\scriptstyle F\prime \\ \scriptstyle F &\scriptstyle Y \end{matrix}\right ]\) is positive semidefinite.

The MPC control law is defined by setting

$$\displaystyle{ u(x) = [I\ 0\ \ldots \ 0]z(x) }$$
(4)

where z(x) is the optimizer of the QP problem (3) for the current value of x and I is the identity matrix of dimension n u × n u .

Multiparametric Solution

Rather than using a numerical QP solver online to compute the optimizer z(x) of (3) for each given current state vector x, the basic idea of explicit MPC is to pre-solve the QP off-line for the entire set of states x (or for a convex polyhedral subset \(X \subseteq \mathbb{R}^{m}\) of interest) to get the optimizer function z, and therefore the MPC control law u, explicitly as a function of x.

The main tool to get such an explicit solution is multiparametric quadratic programming (mpQP). For mpQP problems of the form (3), :̧def :̧def Bemporad et al. (2002b) proved that the optimizer function \(z^{{\ast}} : X_{f}\mapsto \mathbb{R}^{n}\) is piecewise affine and continuous over the set X f of parameters x for which the problem is feasible (X f is a polyhedral set, possibly X f = X) and that the value function \(V ^{{\ast}} : X_{f}\mapsto \mathbb{R}\) associating with every x ∈ X f the corresponding optimal value of (3) is continuous, convex, and piecewise quadratic.

An immediate corollary is that the explicit version of the MPC control law u in (4), being the first n u components of vector z(x), is also a continuous and piecewise-affine state-feedback law defined over a partition of the set X f of states into M polyhedral cells;

$$\displaystyle{ u(x) = \left \{\begin{array}{rcl} F_{1}x + g_{1} & \mbox{ if}&H_{1}x \leq K_{1}\\ \vdots & & \vdots \\ F_{M}x + g_{M}&\mbox{ if}&H_{M}x \leq K_{M} \end{array} \right . }$$
(5)

An example of such a partition is depicted in Fig. 1. The explicit representation (5) has mapped the MPC law (4) into a lookup table of linear gains, meaning that for each given x, the values computed by solving the QP (3) online and those obtained by evaluating (5) are exactly the same.

Explicit Model Predictive Control, Fig. 1
figure 58figure 58

Explicit MPC solution for the double integrator example

Full size image

Multiparametric QP Algorithms

A few algorithms have been proposed in the literature to solve the mpQP problem (3). All of them construct the solution by exploiting the Karush-Kuhn-Tucker (KKT) conditions for optimality:

$$\displaystyle{ Hz + Fx + G\prime \lambda = 0 }$$
(6a)
$$\displaystyle{ \lambda _{i}(G^{i}z - W^{i} - S^{i}x) = 0,\ \forall i = 1,\ldots ,q }$$
(6b)
$$\displaystyle{ Gz \leq W + Sx }$$
(6c)
$$\displaystyle{ \lambda \geq 0 }$$
(6d)

where \(\lambda \in \mathbb{R}^{q}\) is the vector of Lagrange multipliers. For the strictly convex QP (3), conditions (6) are necessary and sufficient to characterize optimality.

An mpQP algorithm starts by fixing an arbitrary starting parameter vector \(x_{0} \in \mathbb{R}^{m}\) (e.g., the origin x0 = 0), solving the QP (3) to get the optimal solution z(x0), and identifying the subset

$$\displaystyle{ \tilde{G}z(x) =\tilde{ S}x +\tilde{ W} }$$
(7a)

of all constraints (6c) that are active at z(x0) and the remaining inactive constraints:

$$\displaystyle{ \hat{G}z(x) \leq \hat{ S}x +\hat{ W} }$$
(7b)

Correspondingly, in view of the complementarity condition (6b), the vector of Lagrange multipliers is split into two subvectors:

$$\displaystyle{ \tilde{\lambda }(x) \geq 0 }$$
(8a)
$$\displaystyle{ \hat{\lambda }(x) = 0 }$$
(8b)

We assume for simplicity that the rows of \(\tilde{G}\) are linearly independent. From (6a), we have the relation

$$\displaystyle{ z(x) = -H^{-1}(Fx +\tilde{ G}\prime \tilde{\lambda }(x)) }$$
(9)

that, when substituted into (7a), provides

$$\displaystyle{ \tilde{\lambda }(x) = -\tilde{M}(\tilde{W} + (\tilde{S} +\tilde{ G}H^{-1}F)x) }$$
(10)

where \(\tilde{M} =\tilde{ G}\prime (\tilde{G}H^{-1}\tilde{G}\prime )^{-1}\) and, by substitution in (9),

$$\displaystyle{ z(x) = H^{-1}(\tilde{M}\tilde{W} +\tilde{ M}(\tilde{S} +\tilde{ G}H^{-1}F)x - Fx) }$$
(11)

The solution z(x) provided by (11) is the correct one for all vectors x such that the chosen combination of active constraints remains optimal. Such all vectors x are identified by imposing constraints (7b) and (8a) on z(x) and \(\tilde{\lambda }(x)\), respectively, that leads to constructing the polyhedral set (“critical region”):

$$\displaystyle{ CR_{0} =\{ x \in \mathbb{R}^{n} :\ \tilde{\lambda } (x) \geq 0,\ \hat{G}z(x) \leq \hat{ W} +\hat{ S}x\} }$$
(12)

Different mpQP solvers were proposed to cover the rest \(X\setminus CR_{0}\) of the parameter set with other critical regions corresponding to new combinations of active constraints. The most efficient methods exploit the so-called “facet-to-facet” property of the multiparametric solution (Spjøtvold et al. 2006) to identify neighboring regions as in Tøndel et al. (2003a) and Baotić (2002). Alternative methods were proposed in Jones and Morari (2006), based on looking at (6) as a multiparametric linear complementarity problem, and in Patrinos and Sarimveis (2010), which provides algorithms for determining all neighboring regions even in the case the facet-to-facet property does not hold.

All methods handle the case of degeneracy, which may happen for some combinations of active constraints that are linearly dependent, that is, the associated matrix \(\tilde{G}\) has no full row rank (in this case, \(\tilde{\lambda }(x)\) may not be uniquely defined).

Extensions

The explicit approach described earlier can be extended to the following MPC setting:

$$\displaystyle\begin{array}{rcl} \min _{z}& \sum _{k=0}^{N-1}\frac{1} {2}(y_{k} -\mathbf{r_{k}})\prime Q_{y}(y_{k} -\mathbf{r_{k}}) + \frac{1} {2}\Delta u_{k}\prime R_{\Delta }\Delta u_{k}& \\ & \ \ \ \ + (u_{k} -\mathbf{u_{k}^{r}})\prime R(u_{k} -\mathbf{u_{k}^{r}})\prime +\rho _{\epsilon }\epsilon ^{2} &{}\end{array}$$
(13a)
$$\displaystyle{ \mathrm{s.t.}\ x_{k+1} = Ax_{k} + Bu_{k} + B_{v}\mathbf{v_{k}} }$$
(13b)
$$\displaystyle{ y_{k} = Cx_{k} + D_{u}u_{k} + D_{v}\mathbf{v_{k}} }$$
(13c)
$$\displaystyle{ u_{k} = u_{k-1} + \Delta u_{k},\ k = 0,\ldots ,N - 1 }$$
(13d)
$$\displaystyle{ \Delta u_{k} = 0,\ k = N_{u},\ldots ,N - 1 }$$
(13e)
$$\displaystyle{ \mathbf{u_{\mathrm{min}}^{k}} \leq u_{ k} \leq \mathbf{u_{\mathrm{max}}^{k}},k = 0,\ldots ,N_{ u} - 1 }$$
(13f)
$$\displaystyle{ \mathbf{\Delta u}_{\mathrm{min}}^{\mathbf{k}} \leq \Delta u_{ k} \leq \mathbf{\Delta u}_{\mathrm{max}}^{\mathbf{k}},\ k = 0,\ldots ,N_{ u} - 1 }$$
(13g)
$$\displaystyle\begin{array}{rcl} & & \mathbf{y_{\mathrm{min}}^{k}} -\epsilon V _{\mathrm{ min}} \leq y_{k} \leq \mathbf{y_{\mathrm{max}}^{k}} +\epsilon V _{\mathrm{ max}} \\ & & \ \ \ \ k = 0,\ldots ,N_{c} - 1 {}\end{array}$$
(13h)

where \(R_{\Delta }\) is a symmetric and positive definite matrix; matrices Q y and R are symmetric and positive semidefinite; \(\mathbf{v_{k}}\) is a vector of measured disturbances; y k is the output vector; \(\mathbf{r_{k}}\) its corresponding reference to be tracked; \(\Delta u_{k}\) is the vector of input increments; \(\mathbf{u_{k}^{r}}\) is the input reference; \(\mathbf{u_{\mathrm{min}}^{k}}\), \(\mathbf{u_{\mathrm{max}}^{k}}\), \(\mathbf{\Delta u_{\mathrm{min}}^{k}}\), \(\mathbf{\Delta u_{\mathrm{max}}^{k}}\), \(\mathbf{y_{\mathrm{min}}^{k}}\), \(\mathbf{y_{\mathrm{max}}^{k}}\) are bounds; and N, N u , N c are, respectively, the prediction, control, and constraint horizons. The extra variable ε is introduced to soften output constraints, penalized by the (usually large) weight ρ ε in the cost function (13a).

Everything marked in bold-face in (13), together with the command input u−1 applied at the previous sampling step and the current state x, can be treated as a parameter with respect to which to solve the mpQP problem and obtain the explicit form of the MPC controller. For example, for a tracking problem with no anticipative action (\(\mathbf{r_{k}} \equiv r_{0}\), \(\forall k = 0,\ldots ,N - 1\)), no measured disturbance, and fixed upper and lower bounds, the explicit solution is a continuous piecewise affine function of the parameter vector \(\left [\begin{matrix}\scriptstyle x \\ \scriptstyle r_{0} \\ \scriptstyle u_{-1}\end{matrix}\right ]\). Note that prediction models and/or weight matrices in (13) cannot be treated as parameters to maintain the mpQP formulation (3).

Linear MPC Based on Convex Piecewise-Affine Costs

A similar setting can be repeated for MPC problems based on linear prediction models and convex piecewise-affine costs, such as 1- and ∞-norms. In this case, the MPC problem is mapped into a multiparametric linear programming (mpLP) problem, whose solution is again continuous and piecewise-affine with respect to the vector of parameters. For details, see Bemporad et al. (2002a).

Robust MPC

Explicit solutions to min-max MPC problems that provide robustness with respect to additive and/or multiplicative unknown-but-bounded uncertainty were proposed in Bemporad et al. (2003), based on a combination of mpLP and dynamic programming. Again the solution is piecewise affine with respect to the state vector.

Hybrid MPC

An MPC formulation based on 1- or ∞-norms and hybrid dynamics expressed in mixed-logical dynamical (MLD) form can be solved explicitly by treating the optimization problem associated with MPC as a multiparametric mixed integer linear programming (mpMILP) problem. The solution is still piecewise affine but may be discontinuous, due to the presence of binary variables (Bemporad et al. 2000). A better approach based on dynamic programming combined with mpLP (or mpQP) was proposed in Borrelli et al. (2005) for hybrid systems in piecewise-affine (PWA) dynamical form and linear (or quadratic) costs.

Applicability of Explicit MPC

Complexity of the Solution

The complexity of the solution is given by the number M of regions that form the explicit solution (5), dictating the amount of memory to store the parametric solution (F i , G i , H i , K i , i = 1, …, M), and the worst-case execution time required to compute F i x + G i once the problem of identifying the index i of the region {x :  H i x ≤ K i } containing the current state x is solved (which usually takes most of the time). The latter is called the “point location problem,” and a few methods have been proposed to solve the problem more efficiently than searching linearly through the list of regions (see, e.g., the tree-based approach of Tøndel et al. 2003b).

An upper bound to M is 2q, which is the number of all possible combinations of active constraints. In practice, M is much smaller than 2q, as most combinations are never active at optimality for any of the vectors x (e.g., lower and upper limits on an actuation signal cannot be active at the same time, unless they coincide). Moreover, regions in which the first n u component of the multiparametric solution z(x) is the same can be joined together, provided that their union is a convex set (an optimal merging algorithm was proposed by Geyer et al. (2008) to get a minimal number M of partitions). Nonetheless, the complexity of the explicit MPC law typically grows exponentially with the number q of constraints. The number m of parameters is less critical and mainly affects the number of elements to be stored in memory (i.e., the number of columns of matrices F i , H i ). The number n of free variables also affects the number M of regions, mainly because they are usually upper and lower bounded.

Computer-Aided Tools

The Model Predictive Control Toolbox (Bemporad et al. 2014) offers functions for designing explicit MPC controllers in MATLAB since 2014. Other tools exist such as the Hybrid Toolbox (Bemporad 2003) and the Multi-Parametric Toolbox (Kvasnica et al. 2006).

Summary and Future Directions

Explicit MPC is a powerful tool to convert an MPC design into an equivalent control law that can be implemented as a lookup table of linear gains. Whether the explicit form is preferable to solving the QP problem online depends on available CPU time, data memory, and program memory and other practical considerations. Although suboptimal methods have been proposed to reduce the complexity of the control law, still the explicit MPC approach remains convenient for relatively small problems (such as one or two command inputs, short control and constraint horizons, up to ten states). For larger problems, and/or problems that are linear time varying, on line QP solution methods tailored to embedded MPC may be preferable.

Cross-References

Recommended Reading

For getting started in explicit MPC, we recommend reading the paper by :̧def :̧def Bemporad et al. (2002b) and the survey paper Alessio and Bemporad (2009). Hands-on experience using one of the MATLAB tools listed above is also useful for fully appreciating the potentials and limitations of explicit MPC. For understanding how to program a good multiparametric QP solver, the reader is recommended to take the approach of Tøndel et al. (2003a) and Spjøtvold et al. (2006) or, in alternative, of Patrinos and Sarimveis (2010) or Jones and Morari (2006).