Enlarging the domain of attraction of MPC controller using invariant sets

ENLARGING THE DOMAIN OF ATTRACTION OF MPC CONTROLLER USING INVARIANT SETS D. Limón Marruedo, T. Álamo and E.F. Camacho Departamento de Ingeniería de Sistemas y Automática, Universidad de Sevilla Escuela Superior de Ingenieros, Camino de los Descubrimientos s/n. 41092 Sevilla, SPAIN Telephone: +34 954487357 Fax: +34 954487340, email: {limon,alamo,eduardo}@cartuja.us.es Abstract: This paper presents a method for enlarging the domain of attraction of nonlinear model predictive control (MPC). The useful way of guaranteeing stability of nonlinear MPC is to add a terminal constraint and a terminal cost in the optimization problem. The terminal constraint 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 prediction horizon. By increasing the prediction horizon, the domain of attraction is enlarged but at expense of a greater computational burden. A strategy to enlarge the domain of attraction of MPC without increasing the prediction horizon is presented. The terminal constraint is replaced by a contractive terminal constraint which is given by a sequence of control invariant sets for the system. This strategy guarantees closed loop stability under the same assumptions. Keywords: Predictive control, Stability domain, Invariants, Nonlinear control systems, Discrete time systems, Asymptotic stability, Constraints 1. INTRODUCTION The ease with which MPC incorporates constraints on both the state and the input of the system has proved very successful in the process industry and in academia. 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). 1The authors acknowledge MCYT-Spain (contract QUI99-0663C02-01) for funding this work. This technique improves previous terminal equality constraint results, but requires commutation to a local controller when the state reaches the terminal region. This is overcome by adding a terminal cost in the functional to be optimized (Chen & Allgower 1998, Mayne et al. 2000). The domain of attraction of the controller is the set of states which can be steered towards the terminal region in Nsteps, where Nis the prediction horizon. This paper is devoted to enlarge this region. The size of the domain of attraction depends on the size of the terminal region and the chosen prediction horizon. Increasing both of these may yield a bigger domain of attraction. The size of the terminal region depends on the computed local controller, the constraints on the system and the procedure used to Copyright © 2002 IFAC www.elsevier.com/locate/ifac Copyright © 2002 IFAC 15th Triennial World Congress, Barcelona, Spain 47 compute it. Thus, the most used procedure to enlarge the domain of attraction is by increasing prediction horizon N. This leads to a greater number of decision variables and therefore, to a greater computational effort. In this paper, a formulation of MPC focused on enlarging the domain of attraction without increasing the prediction horizon is presented. The terminal region of MPC is replaced by a sequence of contractive control invariant sets based on it. Thus, the terminal constraint is transformed into a contractive terminal constraint. Consequently, the optimization problem formulation, and hence the computational effort, is similar to the original one. Closed loop stability is guaranteed under the same assumptions as the original MPC controller. The paper is organized as follows: first, some definitions on invariance sets and preliminary results are given, next the MPC technique is analyzed. In the following section, the MPC formulation proposed is established. Stability results are presented in the next section and the paper finishes with some examples and some conclusions. 2. PRELIMINARY RESULTS 2.1 System description Consider a system described by a nonlinear invariant discrete time model xk  1  f  xk  uk  (1) where xk  IRnis the system state and uk  IRmis the control vector at sample time k. The system is subject to constraint on both states and control actions, and they are given by xk  X(2) uk  U(3) where Xis a closed set and Ua compact set, both of them containing the origin. 2.2 Some concepts on invariant sets This paper has evolved within the framework of invariance set theory and so, well established definitions and results used in the paper are shown. See (Kerrigan 2000) for a very good compilation of definitions and results in set invariance theory and (Blanchini 1999) for a very comprehensive survey paper. In this paper, Kerrigan’s notation is followed (Kerrigan 2000). If the system is controlled by a control law uk  h  xk   U, the closed loop model is given by an autonomous system model xk  1  f  xk  h  xk  . The state is constrained to the set Xh, where Xh   xk  X  h  xk   U  Definition 1. Let Ω  IRn,the one-step set of Ω, Q  Ω  associated to a system (1) subject to (3), is given by:  x  IRn:  u  U  f  x  u   Ω  . That is, the set of states which can be steered in one step to the set Ωby an admissible control action. Proposition 2. Let Ω1and Ω2such that Ω1  Ω2, then Q  Ω1   Q  Ω2  . Definition 3. A set Ω  IR nis a positively invariant set for an autonomous system xk  1  f  xk  , if for all x  Ω, then f  x   Ω. Definition 4. A set Ω  IR nis a control invariant set of a system with a model (1) subject to constraint (3) if for all x  Ω, there exists an admissible input u  h  x   Usuch that f  x  u   Ω. Theorem 5. (Geometric condition for invariance) The set Ω  IRnis a control invariant set if and only if Ω  Q  Ω  . Definition 6. Let Ω  IR nbe a positively invariant set for a system (1) subject to constraint (2) and (3), the i-step stabilizable set Si  X  Ω  is given by  x0  IRn  uk  U  k  0    i  1  xk  X  xi  Ω  k  0    i  1  That is, the set of feasible states which can be steered to the invariant set Ωin i steps by a sequence of admissible control actions. Proposition 7. Let us consider S0  X  Ω  Ω  X, then the i-step stabilizable set satisfies the following propositions (1) Si  1  X  Ω  Q  Si  X  Ω   X. (2) Si  X  Ω   Si  1  X  Ω  (3) If there is an integer i  such that Si  X  Ω  Si  1  X  Ω   i  i  , then the i-step stabilizable set is finitely determined, and Si   X  Ω  S∞  X  Ω  . (4) If xk  Si  X  Ω  then an admissible control action uk  Uexists such that xk  1  Si  1  X  Ω  . (5) Si  X  Ω  is a control invariant set. (6) S∞  X  Ω  is the set of states which can be steered to the invariant set Ωby an admissible control law. 3. THE MPC TECHNIQUE MPC controller are well established control strategy capable of obtaining an optimal control law considering constraints on tha state and on the control actions. Moreover, under mild assumptions, it is possible 48 to guarantee closed loop asymptotic stability (Mayne et al. 2000). The control law KMPC  xk  is obtained by solving a constrained optimization problem and applying it to the system in a receding horizon way. The finite horizon nominal MPC optimization problem with terminal cost and terminal constraint is the most general way of formulating the MPC controller. This problem is stated as follows: MPC optimization problem: min uF JN  xk  uF  N  1 ∑ i  0 L  x  k  i  k   u  k  i  k   F  x  k  N  k  subject to: x  k  i  k   Xi  0    N u  k  i  k   Ui  0    N  1 x  k  N  k   Ω (4) where the decision variables are uF  k   u  k  k   u  k  1  k     u  k  N  1  k   and x  k  i  k  denotes the predicted state using the nominal model, i.e. x  k  i  1  k  f  x  k  i  k   u  k  i  k  for i  0    N  1, where x  k  k  xk. Taking into account that the optimal minimizer u  F  xk  depends only on xkand the receding horizon policy, the control law is given by uk  KMPC  xk  u   k  k  . This control law asymptotically stabilizes the system under the following assumptions: Theorem 8. (Asymptotic stability of MPC (Mayne et al. 2000)) (A1) Let uk  h  xk  be a control law such that Ω  Xh is a positively invariant set for the closed loop system. (A2) Let F  x  be a Lyapunov function associated to the system in Ω, such that for all xk  Ω, F  f  xk  h  xk   F  xk   L  xk  h  xk  then, the MPC control law stabilizes asymptotically the system. Under these assumptions, the optimal cost function J  N  xk  is a Lyapunov function of the closed loop system and the domain of attraction of the controller XN is the set where the optimization problem is feasible. Note that this is the N-step stabilizable set XN  SN  X  Ω  . 3.1 Enlarging MPC domain of attraction The domain of attraction XNcan be enlarged by increasing the prediction horizon or by enlarging the size of the terminal region Ω. The first way enlarges XNsince a grater prediction horizon N1  N2yields to SN2  X  Ω   SN1  X  Ω  . However, note that if Si  X  Ω  is finitely determined with determinedness index i  , for N  i  the domain of attraction is not enlarged. A drawback of this procedure is that it yields a greater computational burden because the number of decision variables of the NLP problem is greater and hence, it requires more computation time , which is limited by the sampling time. Another way of enlarging the domain of attraction is by obtaining a bigger terminal invariant set, since Ω1  Ω2leads to Si  X  Ω1   Si  X  Ω2  . This is achieved in (Magni, Nicolao, Magnani & Scattolini 2001) by considering a different horizon for prediction Npand for control Nc, in such a way that the local controller is applied as the control action until the prediction horizon. The domain of attraction is SNc  X  ΦNp  Nc  where ΦNp  Ncis the set of states of the system controlled by the local controller with an admissible action which reach the set Ωin Np  Nc steps. Since Ω  ΦNp  Nc, the domain of attraction is enlarged. This paper follows the last approach, but from a different point of view of the one presented in (Magni et al. 2001). The invariant set is replaced by a control invariant set, which is bigger than the positively invariant set computed by using the local controller. Notice that no more computation is necessary for solving the optimization problem, so that the prediction horizon is not increased. The only computational burden is carried out off line to calculate a bigger invariant set. 4. MPC BASED ON INVARIANT SETS The proposed MPC controller is similar to the standard one, but a contractive terminal constraint is added to the MPC problem. This constraint is based on a sequence of nested sets which is computed by using invariant set theory. 4.1 Obtaining a contractive sequence of control invariant sets. Proposition 9. Let a system given by (1) be subject to (2), and (3), let Ωbe a control invariant set and let Φ  IRnbe a set such that Ω  Φ  Q  Ω   X then Φis a control invariant set and for all xk  Φ, there is a uk  xk   U, such that f  xk  uk   Ω Based on this property, it is possible to obtain a contractive sequence of Nrcontrol invariant sets. This is based on the computation of the one step set Q    49 which is, in general, a difficult task, especially when the system is nonlinear. Then, this operation can be replaced by an approximation to it, Qap    . Given a positively invariant set of system Ω, the computation of a contractive sequence of control invariant sets may be done using the following algorithm: (1) Make Ω0  Ωand i  0 (2) Compute Ωi  Qap  Ωi  1   X  Ωi  1 (3) If i  Nr,goto5 (4) Else, make i  i  1 and go to 2 (5) End The set obtained by Qap  Ωi  1  must be accurate enough to find a solution to step 2 in the algorithm, that is, the obtained set must contain Ωi  1. Remark 10. Set Ωicomputed by the above algorithm verifies that Ωi  Si  X  Ω  . In fact, if Qap    Q    , then Ωi  Si  X  Ω  . The sequence of control invariant sets obtained can be finitely determined. That is, there may be a i   0 such that Ωi  Ωi  1  i  i  . This can be a consequence of the fact that Si  X  Ω  is finitely determined or due to the approximate calculation Qap    . In this case, Ω∞  Ωi  . The computation of Q    or Qap    is the key for the proposed algorithm and it is an open issue in academia. Note that the computation of the contractive sequence is carried out off line. If the system is linear or piecewise linear, there are efficient numerical algorithms to compute it accurately. See (Blanchini 1999) for linear systems and (Kerrigan 2000) for both, linear and piecewise linear systems. If the system is nonlinear, an inner politopic approximation to each control invariant set can be used as a procedure to compute Qap    . Let us denote a politope as P  A  b   x:A  x  b  where the dimension of x is derived from the context. Let us consider that the constraint sets given by (2) and (3) are politopes, i.e X  P  Ax  bx  and U  P  Au  bu  . Let Ωbe control invariant set and let Ωp  P  C  d  an inner politope of Ω, i.e Ωp  Ω, then the one-step set Q  Ωp  is given by next inequality  C0 0Au    f  x  u  u    C0 0Au   F  z    d bu  This region Q  P  C  d  is a nonlinear map of a politope in the extended state space z  x  u  . In order to use it to implement the algorithm, it is necessary to compute an inner politope of this region, i.e. P  Rz  rz   Q  P  C  d  . This is a difficult task since Q  P  C  d  is non-convex in general. Given that the obtained politope P  Rz  rz  is in the extended state space, it must be projected onto the xcoordinates. It can be done by efficient algorithms such as Fourier-Motzkin elimination. It yields another politope P  Rx  rx   IRn. Notice that P  Rx  rx   Q  P  C  d   Q  Ω  The condition Ω  P  Rx  rx  must be checked. In this case, the politope given by the intersection P  Rx  rx   P  Ax  bx  is a control invariant set. It is worth to remark that this procedure is under research by the authors. 4.2 MPC with contractive terminal constraint Let us consider a system given by (1), subject to constraint on states (2) and on control actions (2). Under the assumption that a contractive sequence  Ωi  of Nr control invariant sets exists, it is possible to establish the following optimization problem MPC optimization problem with contractiveterminal constraint min uF JN  xk  uF  N  1 ∑ i  0 L  x  k  i  k   u  k  i  k   F  x  k  N  k  subject to: x  k  i  k   Xi  0    N(5) u  k  i  k   Ui  0    N  1 (6)  x  k  N  k   ΩNr  kif k  Nr x  k  N  k   Ωif k  Nr (7) where x  k  i  k  is the predicted state using the nominal model, i.e. x  k  i  1  k  f  x  k  i  k   u  k  i  k  i  0    N  1, with x  k  k  xk. Notice that this problem is similar to the standard formulation, but substituting the terminal constraint by the contractive constraint (7). Then, the computational burden is similar, and it can be solved on line with similar computation time. The main computation required is the calculation of the contractive sequence  Ωi  , which is done off line. Proposition 11. Let  Ωi  be a contractive sequence of control invariant sets calculated by the proposed algorithm. Then SN  1  X  Ωi   SN  X  Ωi  1  . Proof: The computed sequence satisfies that Ωi  Q  X  Ωi  1   X  S1  X  Ωi  1  then SN  1  X  Ωi   SN  1  X  S1  X  Ωi  1  . Considering that SN  1  X  S1  X  Ωi  1   SN  X  Ωi  1  the proof is completed. 50 Theorem 12. (Stability of MPC with contractive terminal constraint) 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 8 are satisfied. Let  Ωi  be a contractive sequence of Nrcontrol invariant sets with Ω0  Ω. Then the system controlled by the MPC with constractive terminal constraint is asymptotically stable, with a domain of attraction Xc N  SN  X  ΩNr  . Proof: For k  Nr: This is proved by induction. Let us consider x0  Xc N  SN  X  ΩNr  , then a sequence of N control actions exists which steers the state to ΩNr and then the problem is feasible. Furthermore, given that no mismatches exists between the nominal and the real system, x1  SN  1  X  ΩNr  . From property 11 it follows that x1  SN  X  ΩNr  1  , and hence, the optimization problem is feasible in this state. Let us consider xk  SN  X  ΩNr  k  , then there is a sequence of Ncontrol actions which steers the state to ΩNr  k. Thus the problem is feasible and xk  1  SN  1  X  ΩNr  k  . Taking into account property 11, it yields xk  1  SN  X  ΩNr  k  1  , and hence, the optimization problem is feasible in this state. Consequently, the system evolves towards SN  X  Ω  asymptotically and at k  Nr,xk  SN  X  Ω  . Moreover, the optimization problem is feasible all the time. For k  Nr: The optimization problem is the same as the original MPC and, since the assumptions of theorem 8 are satisfied, the system evolves to the origin asymptotically. Corollary 13. The control law obtained by suboptimal solution of the MPC optimization algorithm asymptotically stabilizes the system under the assumptions proposed by Scokaert et al. in (Scokaert, Mayne & Rawlings. 1999). Since the convergence of the closed loop system is based on the feasibility of the optimization problem for k  Nr, the suboptimal approach also assures the convergence. Corollary 14. If Ω  ΩNrand prediction horizon Nis lower than the determinedness index of the sequence Si  X  Ω  , then the domain of attraction of the proposed controller Xc Nis greater than that of the MPC XN. Proof: Since ΩNr  Ωand N  i  , where i  is the determinedness index, then SN  X  Ω   SN  X  ΩNr   SN  Nr  X  Ω  and therefore, XN  Xc N. If N  i  then SN  X  Ω  SN  Nr  X  Ω  S∞  X  Ω  and hence XN  Xc N  S∞  X  Ω  . Remark 15. If Qap    Q    , then the domain of attraction of the proposed controller is Xc N  SNr  N  X  Ω  . Thus, it is equivalent to the domain of attraction of the MPC with a prediction horizon N  Nr. This controller can be used to reduce the number of decision variables in the MPC problem maintaining the size of the domain of attraction. A drawback of the proposed controller is that for k  Nrthe performance of the closed loop system may be worse than the one of the original MPC since the terminal cost can not be considered as an upper bound of the cost-to-go outside the terminal region Ω. Anyway this property is recovered for k  Nr. 5. EXAMPLES Example 1: Let a second order unstable linear system given by xk  1  A  xk  B  ukwhere A   1  2775  1  3499 1  00  0  B   1  0 0  0  the constraints are  x  ∞  5,  u   1. The cost is given by L  x  u   x  2   u  2. The system controlled by an LQR control law provides a positively invariant set Ω(see Fig.1). In it, the contractive sequence of Nr  5 control invariant sets has been calculated accurately thanks to the Invariant Set Toolbox developed by Kerrigan in (Kerrigan 2000). In Fig.1 the domain of attraction of the proposed MPC Xc Nand the standard MPC XNare depicted by a solid line. The prediction horizon chosen is N  3. In this figure the trajectories of the states of the system are plotted. As it can be seen, the state evolves to the invariant sets. −4 −3 −2 −1 0 1 2 3 4 −4 −3 −2 −1 0 1 2 3 4 x1 x2 X N c X N Ω Fig. 1. Evolution of the system of example 1 51 Example 2: Consider the system used in (Chen & Allgower 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 sampling time used is 0  1 time-units. The stage cost is given by L  x  u   x  2 Q   u  2 R, where Q   0  50 00  5  R  1  0 The system is locally asymptotically stabilized by a linear controller with and associated Lyapunov function V  x  xt  P  x, where P   16  5926 11  5926 11  5926 16  5926  A positively invariant set is Ω   x  IR2:V  x   0  7  . Since both of them satisfies the assumptions of theorem 8, they are used as terminal cost and terminal constraint which guarantees asymptotic stability of the closed loop system. By using an inner politopic approximation of the invariant sets, a sequence of three control invariant sets have been computed. These are shown in Fig. 2. −0.5 −0.4 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 0.4 0.5 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 x 1 x 2 Ω Ω 1 Ω 2 Ω 3 Fig. 2. A sequence of control invariant set for the system of example 2 The proposed MPC technique has been applied to the system with a prediction horizon of N  10. The closed loop state portrait is shown in 3. All the trajectories depicted are not stabilizable by the MPC without contractive terminal constraint with the same prediction horizon. 6. CONCLUSIONS In this paper a formulation of MPC aimed at getting a greater domain of attraction without increasing the prediction horizon is presented. It is based on substituting the terminal region by a contractive sequence −1.5 −1 −0.5 0 0.5 1 1.5 −1.2 −0.7 −0.2 0.3 0.8 x 1 x 2 Fig. 3. Evolution of the system of example 2 of control invariant sets, and hence, the terminal constraint by a contractive terminal constraint. This sequence may be computed by a proposed algorithm based on the calculation of the one-step set in an approximate way. The proposed controller stabilizes the system under the same assumptions as the MPC with terminal constraint. The computation of the contractive sequence of control invariant sets is necessary for the proposed formulation. The key is the computation of the one-step set. This is solved for linear systems, but for nonlinear ones further research is currently being carried out by the authors. REFERENCES Blanchini, F. (1999), ‘Set invariance in control’, Automatica 35, 1747–1767. Camacho, E. & Bordons, C. (1999), Model Predictive Control, 2 edn, Springer-Verlag. Chen, H. & Allgower, F. (1998), ‘A quasi-infinite horizon nonlinear model predictive control scheme with guaranteed stability’, Automatica 34(10), 1205–1218. Kerrigan, E. (2000), Robust Constraint Satisfaction: Invariant Sets and Predictive Control, PhD thesis, University of Cambridge. Magni, L., Nicolao, G. D., Magnani, L. & Scattolini, R. (2001), ‘A stabilizing model-based predictive control algorithm for nonlinear systems’, Automatica 37, 1351–1362. Mayne, D., Rawlings, J., Rao, C. & Scokaert, P. (2000), ‘Constrained model predictive control: Stability and optimality’, Automatica 36, 789– 814. Michalska, H. & Mayne, D. (1993), ‘Robust receding horizon control of constrained nonlinear systems’, IEEE Transactions on Automatic Control 38(11), 1623–1633. Scokaert, P., Mayne, D. & Rawlings., J. (1999), ‘Suboptimal model predictive control (feasibility implies stability)’, IEEE Transactions on Automatic Control 44(3), 648–654. 52