Enlarging the domain of attraction of MPC controllers

EnlargingthedomainofattractionofMPCcontrollers D. Limon, T. Alamo and E.F. Camacho Departamento de Ingenier´ ıa de Sistemas y Autom´ atica, Universidad de Sevilla. Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n. 41092 Sevilla, SPAIN. Telephone: +34 954487357 Fax: +34 954487340 Abstract This paper presents a method for enlarging the domain of attraction of nonlinear model predictive control (MPC). The usual way of guaranteeing stability of nonlinear MPC is to add a terminal constraint and a terminal cost to the optimization problem such that the terminal region is a positively invariant set for the system and the terminal cost is an associated Lyapunov function. The domain of attraction of the controller depends on the size of the terminal region and the control horizon. By increasing the control horizon, the domain of attraction is enlarged but at the expense of a greater computational burden, while increasing the terminal region produces an enlargement without an extra cost. In this paper, the MPC formulation with terminal cost and constraint is modified, replacing the terminal constraint by a contractive terminal constraint. This constraint is given by a sequence of sets computed off-line that is based on the positively invariant set. Each set of this sequence does not need to be an invariant set and can be computed by a procedure which provides an inner approximation to the one-step set. This property allows us to use one-step approximations with a trade off between accuracy and computational burden for the computation of the sequence. This strategy guarantees closed loop stability ensuring the enlargement of the domain of attraction and the local optimality of the controller. Moreover, this idea can be directly translated to robust MPC. Key words: Model Predictive Control, constrained nonlinear systems, domain of attraction, invariant sets, stability. 1 Introduction One of the main factors of the success of MPC both in industry and academia is the ease with which it incorporates constraints in both the states and the inputs of the system. Furthermore, a theoretical framework for analyzing such topics as stability, robustness, optimality, etc. for nonlinear systems has recently been developed: see (Mayne, Rawlings, Rao & Scokaert 2000) for a survey, or (Camacho & Bordons 1999) for process industry application issues. One of the most important results in the stability analysis of MPC is the addition of a terminal constraint based on an invariant set (Michalska & Mayne 1993). This technique improves previous terminal equality constraint results, but requires commutation to a local controller when the state reaches the terminal region. This problem is overcome by ?A preliminary version of this paper was presented at IFAC World Congress 2002 (Barcelona, Spain). The authors would like to acknowledge MCYT-Spain (contract DPI2002-04375-c03-01) for funding this work and also to thank the anonymous reviewers for their helpful comments. Email address: { limon, alamo, eduardo } @cartuja.us.es (D. Limon, T. Alamo and E.F. Camacho). adding a terminal cost to the functional to be optimized (Chen & Allg¨ ower 1998, Mayne et al. 2000). The domain of attraction of the MPC controller is the set of states which can be steered to the terminal region in N steps or less, where Nis the control horizon. The size of the domain of attraction depends on the size of the terminal region and the chosen control horizon. Increasing both of them yields a bigger domain of attraction. The most used procedure to enlarge the domain of attraction is to increase the prediction horizon N. This leads to a greater number of decision variables and, therefore, to a greater computational effort. However, enlarging the size of the terminal set provides a larger domain of attraction with the same computational cost. The enlargement of the terminal set has been used for constrained linear systems in (De Don´ a, Seron, Mayne & Goodwin 2002, Limon, Gomes da Silva, Alamo & Camacho 2003), where the saturated local control law has been considered. In (Chen, Ballance & O’Reilly 2001) the terminal set is enlarged by using a local LDI representation for the nonlinear system and by solving off-line an LMI optimization problem. In (Cannon, Deshmukh & Kouvaritakis 2003), a local LDI representation is also used, Preprint submitted to Automatica 14 October 2004 and a polytopic terminal set and an associated terminal cost are computed. In (Magni, De Nicolao, Magnani & Scattolini 2001), the enlargement of the domain of attraction is achieved by considering a prediction horizon larger than the control horizon. This paper presents a method to enlarge the domain of attraction of MPC by increasing the size of the terminal region. It is achieved by a new idea: replacing the terminal constraint by a contractive constraint given by a sequence of reachable sets to a given invariant set. This is a sequence of sets (not necessarily invariant) where the system can be admissibly steered from one set to the following, ultimately reaching the target invariant set. This sequence of sets is computed off line by recursion based on the positively invariant set. It is shown that this sequence can be computed using an inner approximation of the one step set to relax the computational burden of exact computation. The proposed controller guarantees the enlargement of the domain of attraction, asymptotic stability and local optimality of the closed loop system. Furthermore, it can be directly translated to the robust MPC formulation by using a sequence of robustly reachable sets. It is worth remarking that the optimization problem, and hence the on line computational effort, of the proposed MPC is similar to the original one. 2 System description Considerasystemdescribedby a nonlinearinvariant discrete time model x+=f(x,u)(1) where x∈IRnis the system state, u∈IRmis the current control vector and x+is the successor state. The system is subject to constraints on both states and control actions, and they are given by x∈X(2) u∈U(3) where Xis a closed set and Ua compact set, both of them containing the origin. Consider a sequence of control actions uto be applied to the system at current state x. Then, the predicted state of the system at time j, if the initial state is x(at time 0) and the control sequence uis applied, will be denoted as x(j) = ϕ(j;x,u). 3 Computation of a sequence of reachable sets. In the following some well established definitions and results on invariance set theory (see (Blanchini 1999)) are presented: Consider an autonomous system x+=f(x), then the set Ω⊂IRnis a positively invariant set if f(x)∈Ω, for all x∈Ω. A set Ω⊂IRnis a control invariant set for the system (1) subject to constraint (3) if for all x∈Ω, there exists an admissible input u=u(x)∈Usuch that f(x,u)∈Ω. Let Ω⊂IRnbe a positively (or control) invariant set for a system (1) subject to constraint (2) and (3), then the i-step stabilizable set Xi(Ω)is the set of admissible states which can be steered to the target set Ωin isteps or less by a sequence of admissible control actions. A interesting definition in invariant set theory is the socalled one-step set: let Ω⊂IRn, then the one-step set of Ω,Q(Ω), for the system (1) subject to (3), is the set of states which can be steered in one step to the target set Ωby an admissible control action, i.e. Q(Ω) = {x∈IRn: ∃u(x)∈Usuch thatf(x,u)∈Ω}. If the system is controlled by u=h(x), the closed loop system is constrained to the admissible set Xh={x∈X:h(x)∈U}and the closed-loop one-step set is given by Qh(Ω) = {x∈Xh:f(x,h(x)) ∈Ω}. It is easy to see that Qh(Ω)⊆Q(Ω). This set operation allows us to claim that a given set Ωis a control invariant set if and only if Ω⊆Q(Ω). Moreover, the one step set has the following properties: a) if Ω1⊆Ω2, then Q(Ω1)⊆Q(Ω2)and b) Q(Ω1∪Ω2) = Q(Ω1)∪Q(Ω2). In the following lemma, some interesting properties of the i-step stabilizable set are given. Lemma 1 Consider X0(Ω) = Ω⊆X, then (i) Xi(Ω) = Q(Xi−1(Ω))∩X, for i ≥1. (ii) Xi(Ω)⊇Xi−1(Ω)and Xi(Ω)is a control invariant set. (iii) Xi(Xj(Ω)) = Xi+j(Ω). (iv) Xi(Ω1∪Ω2) = Xi(Ω1)∪Xi(Ω2). 3.1 Obtaining a sequence of reachable sets. The objective of this section is to present a general and practical procedure to compute a contractive sequence of reachable sets, {Ωi}, based on the terminal set Ω. We denote as sequence of reachable sets a sequence of sets where the system state can be steered from one set Ωito the following, Ωi−1, in an admissible way, finally reaching the target invariant set Ω. This problem has been studied in (Bertsekas 1971) where it is demonstrated that the maximal sequence that can be obtained is the stabilizable set Xi(Ω). The computation of this sequence is based on the calculation of the one-step set. The computation of invariant sets, and hence of the one-step set, is an open field (see (Blanchini 1999) for a compilation of the existing results). Efficient procedures exist to compute it for linear systems subject to polytopic constraints, for systems with polytopic constraints described by linear differential inclusions (Blanchini 1999). However, for nonlinear systems there is not a general procedure for this. 2 In order to relax the complexity of computation, the onestep set can be replaced by an inner approximation to it, i.e. Qap(Ω)⊆Q(Ω). This relaxation makes sense for the sake of the tractability of the procedure used to compute it. Using Qap(·), and based on the invariant set Ω, a contractive sequence of reachable sets can be computed by the following recursion: Ωi=Qap(Ωi−1)∩X,with Ω0=Ω(4) This sequence of sets has the following properties: Lemma 2 Let {Ωi}be a sequence of sets obtained by (4), then (i) Ωi⊆Xi(Ω). In fact, if Qap(·) = Q(·), then Ωi=Xi(Ω). (ii) If Ωi−1⊆Ωithen Ωiand Ωi−1are control invariant sets. (iii) XN−1(Ωi)⊆XN(Ωi−1), for all N ≥1and i ≥1. Proof: (i) Ω1=Qap(Ω)∩X⊆Q(Ω)∩X=X1(Ω). Consider that Ωi−1⊆Xi−1(Ω), then Ωi=Qap(Ωi−1)∩X⊆ Q(Ωi−1)∩X⊆Q(Xi−1(Ω))∩X=Xi(Ω). (ii) Ωi−1⊆Ωi=Qap(Ωi−1)∩X⊆Q(Ωi−1)⊆Q(Ωi), and the proof is derived from the geometric condition for invariance. (iii) The computed sequence satisfies that Ωi⊆Q(Ωi−1)∩ X=X1(Ωi−1). Then XN−1(Ωi)⊆XN−1(X1(Ωi−1)) = XN(Ωi−1).2 Note that the obtained sequence inherits some properties from the stabilizable sets, but, it is not guaranteed that Ωi includes either the set Ωi−1or Ω, given the approximate character of Qap(·). Consequently, the obtained sequence is a sequence of reachable sets (not necessarily invariant sets) to the target set Ω. This result allows us to design algorithms less computationally demanding for determining a sequence of invariants sets or merely reachable sets. Similar ideas have been used for the computation of positively invariant sets of nonlinear systems based on an LDI approximation of the system by solving an LMI (Chen et al. 2001). In (Cannon et al. 2003), using an LDI representation of the nonlinear systems, a sequence of polytopic invariant sets is computed and an interpolation based controller is proposed. An algorithm for computing a polytopic set Qap(Ω)for nonlinear systems based on interval arithmetics is presented in (Bravo, Limon, Alamo & Camacho 2003). The approximation can be obtained with a given bound on the error, which allows a trade off between the accuracy of the approximation and the computational burden to be found. 4 The MPC technique MPC is a well established control strategy capable of obtaining an optimal control law that takes into account constraints on the state and on the control actions. Moreover, under mild assumptions, it is possible to guarantee closed loop asymptotic stability (Mayne et al. 2000). The control law KN(x)is obtained by solving the following constrained optimization problem min uVN(x,u) = N−1 ∑ i=0 `(x(i),u(i))+F(x(N)) s.t.x(i)∈X,u(i)∈U,i=0,···,N−1 x(N)∈Ω where x(i) = ϕ(i;x,u), and applying the optimal solution to the system in a receding horizon way. This finite horizon nominal MPC optimization problem with terminal cost and terminal constraint is the most general way of formulating the MPC controller, and in the following this formulation will be denoted as standard MPC. Taking into account that the optimal minimizer u∗(x)only depends on the actual state xand the receding horizon policy, the control law is given by u=KN(x) = u∗(0). This control law stabilizes the system asymptotically under the following assumptions: Theorem 3 (Mayne et al. 2000) Let u =h(x)be a control law such that Ω⊆Xh={x∈X:h(x)∈U}is a positively invariant set for the closed loop system. Let F(x)be a Lyapunov function associated to the system in Ω, such that for all x ∈Ω, F(f(x,h(x)))−F(x)≤ −`(x,h(x)) then, the MPC control law stabilizes the system asymptotically for all initial states such that the optimization problem is feasible. Under these assumptions, the optimal cost function V∗ N(x)is a Lyapunov function for the closed loop system and its domain of attraction is the N-step stabilizable set to the terminal region Ω,XN(Ω). The domain of attraction XN(Ω)can be enlarged by two methods: either increasing the prediction horizon N(since a greater prediction horizon N1>N2 yields XN2(Ω)⊆XN1(Ω)) or considering a bigger terminal set (since Ω1⊆Ω2leads to XN(Ω1)⊆XN(Ω2)). The first way increases the number of decision variables, and hence, the computational burden of the optimization problem to be solved on-line, whilst in the second the optimization problem is similar. This second method is more convenient and it has been used in several papers such as (Magni et al. 2001, Chen et al. 2001, Limon, Gomes da Silva, Alamo & Camacho 2003). 5 MPC based on a contractive terminal constraint Let us consider a system given by (1), subject to constraints on states (2) and on control actions (3). Under the assumption that a sequence of Nrreachable sets {Ωi}is available, the following optimization problem is established at sample 3 instant k, min uVN(xk,u) s.t.x(i)∈X,u(i)∈U,i=0,···,N−1 x(N)∈Ωj,j=max(Nr−k,0)(5) where x(i) = ϕ(i;xk,u). This problem is similar to the standard formulation, but substituting the terminal constraint by the contractive constraint (5). The terminal set at time 0 is ΩNr, and for the first Nrsample times, the index jin Ωjis reduced until k=Nr, when the terminal set is Ω. Therefore, the control law derived from this problem is time-varying for the first Nrsample times. For k≥Nrthe control law is the same as that of the (time-invariant) MPC with terminal set Ω. Note that the optimization problem can be solved on line with similar computational cost and that the main computation required is the calculation of the contractive sequence {Ωi}, which is done off line. In the following theorem it is proved that the proposed MPC controller stabilizes the system asymptotically in XN(ΩNr). Theorem 4 Let a system given by (1) be subject to constraint on state (2) and on control actions (3). Let Ωbe a positively invariant set of the system and let F(x)be an associated Lyapunov function such that the assumptions of theorem 3 are satisfied. Let {Ωi}be a sequence of Nrreachable sets with Ω0=Ω. Then the system controlled by the proposed MPC is asymptotically stable, with a domain of attraction XN(ΩNr). Proof: First, the feasibility of the controller is proved by induction. Let xkand ukdenote the state and the control action applied to the system at sampling time k. Let us consider that the problem is feasible at k=i, that is, xi∈XN(ΩNr−i); then there is a sequence of Ncontrol actions which steers the state to ΩNr−i. Thus, given that no mismatches exist between the nominal and the real system, xi+1∈XN−1(ΩNr−i). Taking into account lemma 2, it yields xi+1∈XN(ΩNr−i−1). Then, the optimization problem is feasible at k=i+1. Thus, if x0∈XN(ΩNr)then by induction it is inferred that the controller is feasible for all k<Nr. Since xNr∈XN(Ω), and because the terminal set is Ωfor k≥Nr, then the optimization problem will be feasible all the time in virtue of theorem 3. The stability is derived from the fact that the system evolves to XN(Ω)after Nrsamples. For k≥Nr, the optimization problem is the same as the standard MPC and, given that the assumptions of theorem 3 are satisfied, the system evolves asymptotically to the origin. 2 Note that, if the assumptions proposed in (Scokaert, Mayne & Rawlings. 1999) hold for k≥Nr, then the optimality of the solution is not necessary to guarantee the asymptotic stability. Remark 5 (Enlargement of the domain of attraction) (i) If Ω⊂ΩNrthen the proposed controller enlarges the domain of attraction of the controller, i.e. XN(Ω)⊆ XN(ΩNr). (ii) If the set ΩNrdoes not include Ω, then the enlargement can be guaranteed by a simple procedure: consider any initial state x0∈XN(SNr i=0Ωi), then a j such that x∈XN(Ωj)can be found and the contraction can be begun from it. (iii) If the one-step set is computed accurately for obtaining the sequence {Ωi}, then XN(ΩNr) = XN+Nr(Ω). Hence, the domain of attraction of the proposed controller is the same as that obtained by standard MPC with prediction horizon N+Nr, but considering only N control actions as decision variables. Remark 6 (Local optimality) Since for k ≥Nrthe optimization problem of the proposed controller is the same as that of MPC with terminal region Ω, its solution is the same and retains the local optimality of standard MPC. Furthermore, it has been proved that under the stabilizing conditions of theorem 3, there is a neighborhood of the origin (which contains the terminal region Ω) where the terminal constraint is no longer active and can be removed from the optimization problem (Limon, Alamo & Camacho 2003). Consequently, in this region the optimality of the solution depends on the chosen terminal cost, but not on the (contractive) terminal region. Remark 7 (Robustness) Thanks to its asymptotic stability, the proposed MPC controller retains a certain degree of robustness for those uncertainties that are small enough, as in the case of the standard formulation of MPC (Limon, Alamo & Camacho 2002, Scokaert, Rawlings & Meadows 1997). If a robust design of the MPC is carried out, for instanceby means of a closed-loopformulation (Mayne etal. 2000), then the proposed idea can still be applied. The only requirement that should be added is that the sequence of terminal sets be a sequence of robustly reachable sets to the robust invariant terminal region. Thus, the computation of the approximate one step set must be robust; that is, for all possible uncertainties. The proposed MPC is related to that presented in (Magni et al. 2001), as both of them enlarge the domain of attraction of the MPC by considering a larger terminal set. However, both approaches are different, and in some way, complementary. In Magni’s MPC a prediction horizon, Np, larger than the control horizon, Nc, is considered and the local control law is used to predict the evolution from Ncto Np. This is equivalent to considering a terminal cost given by FNc,Np(x(Nc)) = Np−1 ∑ i=Nc `(x(i),h(x(i)))+F(x(Np)) (6) where x(i) = f(x(i−1),h(x(i−1))) for i=Nc+1,···,Np 4 and the terminal region given by ΩNp−Ncderived from (4) using Qap(·) = Qh(·). The main novelty is that this set is not computed explicitly, but implicitly described by the defining equations and added as terminal constraint in the optimization problem. The MPC proposed in this paper exploits the notion of control invariance: the terminal set is replaced by a sequence of reachable sets computed off-line from (4) using an approximate tractable approach Qap(·)to the one step set Q(·). Since Qh(Ω)⊆Q(Ω)for any Ω, our approach can potentially provide a larger domain of attraction than Magni’s one (as can be seen in the examples); this depends on how good the approximation Qap(·)is with relation to Qh(·). Note also that if the terminal cost (6) is considered, both approaches provide the same solution in a neighborhood of the origin. It is worth noting that the extension to the robust case of the MPC proposed in this paper is achieved in a less involved way than Magni’s extension. 6 Examples Example 1: Consider a second order unstable linear system given by x+=A·x+B·uwhere A="1.2775 −1.3499 1.0 0.0#B="1.0 0.0# the constraints are kxk∞≤5, |u|<1. The cost is given by `(x,u) = kxk2 2+kuk2 2. The system is controlled by an LQR control law and the associated maximal positively invariant set is Ω(see Fig.1). Based on Ω, the contractive sequence of Nr=5 control invariant sets has been calculated accurately, and then Ωi= Xi(Ω). The prediction and control horizon is considered to be N=3. In Fig.1 the domain of attraction of the proposed MPC, X3(Ω5), and the one of the original MPC (even with a larger prediction horizon) X3(Ω)are depicted by a solid line. In this case X3(Ω5) = X8(Ω), and therefore the proposed controlleris able to stabilize with N=3 anystate stabilizable bythe original MPC with N=8. In this figure the trajectories of the states of the system are plotted. As can be seen, the state evolves asymptotically to the origin. Example 2: Consider the system used in (Chen & Allg¨ ower 1998) described by ˙x1=x2+u·(µ+(1−µ)·x1) ˙x2=x1+u·(µ−4·(1−µ)·x2) where the parameter µis 0.5. The input is constrained to |u| ≤ 2. The system has been discretized using a 4th order Runge-Kutta method with a sampling time of 0.1 time-units. The stage cost is given by `(x,u) = 0.5kxk2 2+kuk2 2. −4 −3 −2 −1 0 1 2 3 4 −4 −3 −2 −1 0 1 2 3 4 x1 x2 X3(Ω5) X3(Ω) Ω Fig. 1. Evolution of the system of example 1 The system is locally asymptotically stabilized by a local linear controller u=h(x)with an associated Lyapunov function F(x) = 16.5926(x2 1+x2 2)+23.1852x1x2in the positively invariant set Ω={x∈IR2:F(x)≤0.7}. Both of them satisfy the assumptions of theorem 3. A sequence of 10 reachable sets has been computed off line using as approximation of the one-step set the one proposed in (Bravo et al. 2003). Based on this sequence, the proposed MPC technique has been applied to the system with a control horizon of Nc=3. The considered terminal cost is given by (6) considering a prediction horizon of 33. The sequence of sets and the closed loop state portrait are shown in figure 2. −1 0 1 −4 −3 −2 −1 0 1 x1 x2 A B C D E F Fig. 2. The sequence of reachable sets and state portrait of the system of example 2 It is worth remarking that none of the depicted initial states are feasible for a standard MPC with prediction and control horizon of 3. If Magni’s MPC is used with Np=33 and Nc=3, then the initial states A,B,E and F are feasible, while C and D are only feasible for the proposed MPC. 7 Conclusions In this paper a formulation of MPC to enlarge the domain of attraction without increasing the prediction horizon is presented. It is based on substituting the standard invariant terminal region by a sequence of reachable sets, and hence, the terminal constraint by a contractive terminal constraint. This sequence of sets can be computed by a proposed method 5 based on the calculation of an inner approximation of the one-step set. The proposed controller stabilizes the system under the same assumptions as the MPC with terminal constraint, guaranteeing the enlargement of the domain of attraction as well as the local optimality. It is also shown that this idea can be straightforwardly translated to the robust case. References Bertsekas, D. P. (1971), ‘On the minimax reachability of target sets and target tubes’, Automatica 7, 233–247. Blanchini, F. (1999), ‘Set invariance in control’, Automatica 35, 1747– 1767. Bravo, J. M., Limon, D., Alamo, T. & Camacho, E. (2003), On the computation of invariant sets for constrained nonlinear systems: An interval arithmetic approach, in ‘Proceedings of the ECC’. Camacho, E. F. & Bordons, C. (1999), Model Predictive Control, 2 edn, Springer-Verlag. Cannon, M., Deshmukh, V. & Kouvaritakis, B. (2003), ‘Nonlinear model predictive control with polytopic invariant sets’, Automatica 39, 1487–1494. Chen, H. & Allg¨ ower, F. (1998), ‘A quasi-infinite horizon nonlinear model predictive control scheme with guaranteed stability’, Automatica 34(10), 1205–1218. Chen, W., Ballance, D. & O’Reilly, J. (2001), Optimisation of attraction domains of nonlinear MPC via LMI, in ‘Proceedings of the ACC’. De Don´ a, J. A., Seron, M. M., Mayne, D. Q. & Goodwin, G. C. (2002), ‘Enlarged terminal sets guaranteeing stability of receding horizon control’, Systems & Control Letters 47, 57–63. Limon, D., Alamo, T. & Camacho, E. F. (2002), Stability analysis of systems with bounded additive uncertainties based on invariant sets: Stability and feasibility of MPC, in ‘Proceedings of the ACC’. Limon, D., Alamo, T. & Camacho, E. F. (2003), Stable constrained MPC without terminal constraint, in ‘Proceedings of the ACC’. Limon, D., Gomes da Silva, J., Alamo, T. & Camacho, E. F. (2003), Improved MPC design based on saturating control laws, in ‘Proceedings of the ECC’. Magni, L., De Nicolao, G., Magnani, L. & Scattolini, R. (2001), ‘A stabilizing model-based predictive control algorithm for nonlinear systems’, Automatica 37, 1351–1362. Mayne, D. Q., Rawlings, J. B., Rao, C. V. & Scokaert, P. O. M. (2000), ‘Constrained model predictive control: Stability and optimality’, Automatica 36, 789–814. Michalska, H. & Mayne, D. Q. (1993), ‘Robust receding horizon control of constrained nonlinear systems’, IEEE Transactions on Automatic Control 38(11), 1623–1633. Scokaert, P. O. M., Mayne, D. Q. & Rawlings., J. B. (1999), ‘Suboptimal model predictive control (feasibility implies stability)’, IEEE Transactions on Automatic Control 44(3), 648–654. Scokaert, P. O. M., Rawlings, J. B. & Meadows, E. S. (1997), ‘Discretetime stability with perturbations: Application to model predictive control’, Automatica 33(3), 463–470. 6