Interpolation-based Off-line Robust MPC for Uncertain Polytopic Discrete-time Systems

Keywords: Off-line robust MPC, linear interpolation, pre-computed state feedback gains

In this paper, interpolation-based off-line robust MPC for uncertain polytopic discrete-time systems is presented. Instead of solving an on-line optimization problem at each sampling time to find a state feedback gain, a sequence of state feedback gains is precomputed off-line in order to reduce the on-line computational time. At each sampling time, the real-time state feedback gain is calculated by linear interpolation between the precomputed state feedback gains. Three interpolation techniques are proposed. In the first technique, the smallest ellipsoids containing the measured state are approximated and the corresponding real-time state feedback gain is calculated. In the second technique, the precomputed state feedback gains are interpolated in order to get the largest possible real-time state feedback gain while robust stability is still guaranteed. In the last technique, the realtime state feedback gain is calculated by minimizing the violation of the constraints of the adjacent inner ellipsoids so the real-time state feedback gain calculated has to regulate the state from the current ellipsoids to the adjacent inner ellipsoids as fast as possible. As compared to on-line robust MPC, the proposed techniques can significantly reduce on-line computational time while the same level of control performance is still ensured. 

Introduction

Model predictive control (MPC) has originated in the industry as an on-line computer control algorithm to solve multivariable control problems. At each sampling instant, MPC uses an explicit process model to solve the optimization problem and only the first computed input is implemented to the process. Although MPC has been successfully implemented to many industrial processes, it is well-known that stability of MPC cannot be guaranteed in the presence of model uncertainty [1]. For this reason, synthesis approaches for robust MPC have been widely investigated [2][3][4][5][6]. 
On-line robust MPC has been proposed by many researchers. Kothare et al. [2] proposed the algorithm that constructs an invariant ellipsoid containing the measured state at each sampling instant. Any states in this invariant ellipsoid can be driven to the origin by using the stabilizing state feedback gain. Thus, robust stability is guaranteed. The stabilizing state feedback gain is derived by using a single Lyapunov function so a certain degree of conservativeness is obtained. The conservativeness can be reduced by on-line robust MPC formulation using parameter-dependent Lyapunov function as proposed in [3][4][5][6]. However, the number of decision variables and constraints also increases. Thus, the algorithms are not suitable for relatively fast dynamic processes. Another approach to reduce the conservativeness is to increase the degrees of freedom in solving the optimization problem by adding a sequence of free control inputs to the state feedback control law [7][8][9][10][11]. By doing so, larger on-line computational time is required to calculate a sequence of free control inputs so the algorithms can only be implemented to slow dynamic processes. 
In order to reduce on-line computational time, various researchers have studied off-line robust MPC [12][13][14][15][16][17][18][19][20]. Wan and Kothare [12] proposed an off-line robust MPC formulation using linear matrix inequalities (LMIs). The on-line computational time is reduced by pre-computing off-line a sequence of state feedback gains corresponding to a sequence of ellipsoidal invariant sets. At each sampling instant, the state is measured and the real-time state feedback gain is calculated by linear interpolation between the precomputed state feedback gains. Although the on-line computational time is significantly reduced, a certain degree of conservativeness is obtained because the algorithm is derived by minimizing the worst-case performance cost. This strategy can be further improved by using the nominal performance cost as proposed by Ding et al. [13]. However, the approach in [13] is restricted to the case of a single Lyapunov function. Another idea is to incorporate the scheduling parameter into off-line MPC formulation. In [14], the sequences of state feedback gains corresponding to the sequences of ellipsoids are pre-computed offline. At each sampling instant, the scheduling parameter is measured and the real-time state feedback gain is calculated by linear interpolation between the pre-computed state feedback gains of each sequence. Off-line robust MPC can also be formulated by using polyhedral invariant sets [15][16][17][18][19][20] in order to enlarge the size of stabilizable region. Later, an interpolation technique for polyhedral invariant sets was developed to reduce conservativeness and improve the control performances [21]. 
Recently, Bumroongsri and Kheawhom [22] have developed on-line robust MPC based on nominal performance cost by extending the results of Ding et al. [13] to the case of parameter-dependent Lyapunov function. However, the optimization problem solved at each sampling instant has many decision variables and constraints so its application is rather restricted to relatively slow dynamic processes. This algorithm was then further improved by off-line pre-computing a sequence of state feedback gains corresponding to the sequences of ellipsoidal invariant sets [23]. 
In this paper, the off-line robust MPC based on nominal performance cost for uncertain polytopic discrete-time systems [23] is further improved by implementing interpolation techniques. Three interpolation techniques are proposed. A sequence of state feedback gains is pre-computed off-line. At each sampling time, the real-time state feedback gain is calculated by linear interpolation between the precomputed state feedback gains. The control performance of each technique is evaluated and compared within an example. 
The paper is organized as follows. In section 2, the problem description is presented. In section 3, interpolation-based off-line robust MPC is presented. In section 4, we present an example to illustrate the implementation of the proposed algorithm. Finally, in section 5, we conclude the paper. 

Problem Description

The model considered here is the following linear time varying (LTV) system with polytopic uncertainty 
) ( ) ( ) ( ) ( ) ( ) ( ) 1 ( k Cx k y k u k B k x k A k x     (1)
where 
) (k x
is the vector of states, ) (k u is the vector of control inputs and ) (k y is the vector of plant outputs. Moreover, we assume that 
]} , [ ],.., , [ ], , {[ , )] ( ), ( [ 2 2 1 1 L L B A B A B A Co Ω Ω k B k A   (2)
where Ω is the polytope, 
Co denotes convex hull, ] , [ j j B
A are the vertices of Ω and L is the number of the vertices of Ω . Any 
)] ( ), ( [ k B k A
within the polytope is a linear combination of the vertices such that 
1 0 , 1 ], , [ )] ( ), ( [ 1 1         j L j j j j L j j B A k B k A    (3) where ] ,..., , [ 2 1 L     
is the uncertain parameter vector. The aim of this research is to find the state feedback control law 
) / ( ) / ( k i k Kx k i k u   
(4) which stabilizes the system (1) and minimizes the following nominal performance cost 
) ( min , 0 ), / ( k J n i k i k u    ) ( min , 0 ), / ( k J n i k i k u                                     ) / ( ) / ( 0 0 ) / ( ) / ( 0 , ) ( k i k u k i k x R k i k u k i k x T i n k J  (5) 
h h u k i k u   , u n h ,..., 3 , 2 , 1  (6) max , ) / ( r r y k i k y   , y n r ,..., 3 , 2 , 1  (7) 
where u n is the number of control inputs and y n is the number of plant outputs. In [22], the optimization problem ( 5) is formulated as the convex optimization involving linear matrix inequalities (LMIs). At each sampling time, the state feedback control law which minimizes the upper bound n  on the nominal performance cost 
) ( , k J n 
and asymptotically stabilizes the closed-loop systems within the ellipsoids 
} ,..., 2 1 , 1 / { 1 L , j x Q x x j T j       is given by 1 ), / ( ) / (      YG K k i k Kx k i k u
where Y and G are obtained by solving the following problem denotes the nominal model of the plant, the symbol  denotes the corresponding transpose of the lower block part of symmetric matrices, I denotes the identity matrix, X is the diagonal matrix of input constraints and S is the diagonal matrix of output constraints. 
γ n Y,G,Q j min (8) L , j , Q k/k x j ,..., 2 1 0 ) ( 1 s.t.           (9) L , l L, , j , I γ Y R I γ G Θ Q Y B G A Q G G n n l ^j T ,..., 2 1 ,..., 2 1 0 0 0 0 2 1 2 1                                 (10) L , l L, , j , Q Y B G A Q G G l j j j T ,..., 2 1 ,..., 2 1 0                  (11) u h, hh j T T n , , h , u X L, , j , Q G G Y X ..., 2 1 ,..., 2 1 0 2 max               (12) y r, rr j T T T j j n , , ,r y S L , j , Q G G C Y) B G (A S ..., 2 1 , ,..., 2 1 0 2 max                ( 13 
Robust stability is guaranteed by the Lyapunov stability constraint (10). For proof details, the reader is referred to [22]. Since the on-line optimization problem contains many decision variables and constraints, the algorithm requires large on-line computational time. Moreover, the number of constraints grows exponentially with the number of vertices of the polytope Ω . 

The Proposed Algorithm

In this section, interpolation-based off-line robust MPC for uncertain polytopic discrete-time systems is presented. The aim is to reduce the on-line computational burdens while the same level of control performance is still ensured. The on-line computational time is reduced by solving off-line the optimization problem ( 8) to find a sequence of state feedback gain 
N i K i ,..., 2 , 1 ,  corresponding to the sequences of ellipsoids   1 / 1 , ,    x Q x x j i T j i 
where 
N i ,..., 2 , 1 
is the number of ellipsoids and 
L j ,..., 2 , 1 
is the number of vertices of polytope Ω . At each sampling time, the real-time state feedback gain is calculated by linear interpolation between the pre-computed state feedback gains. 

3.1.

Interpolation-Based Off-Line Robust MPC Off-line: Choose a sequence of states 9) by i x and solve the optimization problem (8) to obtain the corresponding state feedback gain 
N i x i ,..., 2 , 1 ,  . For each i x , substitute ) / ( k k x in (
1   i i i G Y K and ellipsoids   . ,..., 2 , 1 , 1 / 1 , , L j x Q x x j i T j i     
Note that i x should be chosen such that 
j i j i , , 1     .
Moreover, for each N i  , the following inequality must be satisfied 
, 0 ) ( ) ( 1 1 , 1 1 ,         i j j l i T i j j j i K B A Q K B A Q . 2 1 , 2 1 ....L , l ....L , j    
On-line: The real-time state feedback gain is calculated by linear interpolation between the pre-computed state feedback gains. Three interpolation techniques are proposed as follows Technique 1: The first technique is based on an approximation of the smallest ellipsoids containing the measured state. Instead of solving the optimization problem (8) at each sampling instant, the solution of the optimization problem ( 8) is approximated by finding the smallest ellipsoids containing the measured state. Then the corresponding real-time state feedback gain can be calculated by linear interpolation between the pre-computed state feedback gains. At each sampling time, when 
, ) ( , ) ( , 1 , j i j i k x k x      N i L ... , j    , , , 2 1 
, the real-time state feedback gain 
1 )) ( 1 ( ) ( )) ( (     i i K k K k k K    can be calculated from ) (k 
obtained by solving the following problem. 
) ( min k  ( 14 
) 1 1 , 1, s.t. ( ) ( ( )[ ] (1 ( ))[ ]) ( ) 1, 1 2, , T i j i j x k k Q k Q x k j , .... L           (15) 1 ) ( 0   k  ( 16 
)
It is seen that 
0 ) (  k  and 1 ) (  k  correspond to the ellipsoids j i , 1 
 and j i,  , respectively. Thus, the smallest ellipsoids containing the measured state ) (k x can be found by minimizing 14). Moreover, it is seen that the optimization problem ( 14) is linear programming and the number of constraints grows only linearly with the number of vertices of the polytope Ω . 
) (k  in ( 
Figure 1 shows the graphical representation of the state feedback gain in each prediction horizon. It is seen that the same state feedback gain 
)) ( ( k K 
is implemented throughout the prediction horizon and control horizon. Thus, the state must be restricted to lie in the smallest ellipsoids approximated by (15) and robust stability is guaranteed. 
j i j i k x k x      N i L ... , j    , , , 2 1 
, the real-time state feedback gain 
1 )) ( 1 ( ) ( )) ( (     i i K k K k k K    can be calculated from ) (k 
obtained by solving the following problem. 
) ( min k  (17) s.t. L j Q k x k K B A k x k K B A j i j j T j j ,..., 2 , 1 , 0 ) ( ))) ( ( ( )) ( ))) ( ( (( 1 
,               (18) 0 1 )) ( )) ( ( ( 2 max 
, 
          h h k x k K u  (19) 1 ) ( 0 
  k  ( 20 
)
1  i K
is always larger than i K because input and output constraints impose less limit on the state feedback gain as i increases. Thus, the largest possible real-time state feedback gain 
   i i K k K k k K    1 )) ( 1 ( ) ( )) ( (  
can be calculated by minimizing 17). The next predicted state is restricted to lie in the ellipsoidal invariant set by ( 18) so robust stability is still guaranteed. The input constraint is guaranteed by (19). Note that the output constraint does not need to be incorporated into the problem formulation because the satisfaction of (18) also guarantees output constraint satisfaction. It is seen that the optimization problem ( 17) is formulated as the convex optimization involving linear matrix inequalities (LMIs) and the number of constraints grows only linearly with the number of vertices of the polytope Ω . 
) (k  in ( 
Figure 2 shows the graphical representation of the state feedback gain in each prediction horizon. It is seen that the largest possible real-time state feedback gain 
)) ( ( k K 
is only implemented at each sampling time k . At time 1  k and so on, the state feedback gain i K is implemented. Thus, the state must be restricted to lie in the ellipsoids 
N i L ... , j k x k x j i j i       , , , 2 1 , ) ( , ) ( , 1 , 

 

, the real-time state feedback gain 
1 )) ( 1 ( ) ( )) ( (     i i K k K k k K   
can be calculated from 
) (k 
obtained by solving the following problem. 
) ( min k  (21) s.t. L j Q k x k K B A k x k K B A k j i j j T j j ,..., 2 , 1 , 0 ) ( ))) ( ( ( 
)) ( ))) ( ( (( ) ( 1 , 1                  ( 22 
) L j Q k x k K B A k x k K B A j i j j T j j ,..., 2 , 1 , 0 ) ( ))) ( ( ( 
)) ( ))) ( ( (( 1 ,               ( 23 
) 0 1 )) ( )) ( ( ( 2 max ,           h h k x k K u  (24) 1 ) ( 0   k  ( 25 
)
By applying Schur complement to (22), we obtain 
) ( 1 ) 1 ( ) 1 ( 1 , 1 k k x Q k x j j i T j        where ) ( ))) ( ( ( ) 1 ( k x k K B A k x j j j    
. By minimizing 21), the real-time state feedback gain 
) (k  in (
1 )) ( 1 ( ) ( )) ( (     i i K k K k k K   
calculated has to regulate the state from the current ellipsoids 23) so robust stability is still guaranteed. The input constraint is guaranteed by (24). Note that the output constraint does not need to be incorporated into the problem formulation because the satisfaction of ( 23) also guarantees output constraint satisfaction. It is seen that the optimization problem ( 21) is formulated as the convex optimization involving linear matrix inequalities (LMIs) and the number of constraints grows only linearly with the number of vertices of the polytope Ω . 
Figure 3 shows the graphical representation of the state feedback gain in each prediction horizon. It is seen that the real-time state feedback gain calculated 
)) ( ( k K 
is only implemented at each sampling time k . At time 
1  k
and so on, the state feedback gain i K is implemented. Thus, the state must be restricted to lie in the ellipsoids j i,  and robust stability is guaranteed. 

Example

We will consider an application of our approach to an angular positioning system [2]. The system consists of an electric motor driving a rotating antenna so that it always points in the direction of a moving object. The motion of the antenna can be described by the following discrete-time equation 
) ( 0787 . 0 0 ) ( ) ( ) ( 1 . 0 1 0 1 . 0 1 ) 1 ( ) 1 ( . . k u k k k k k                                                  ) ( ) ( 0 1 ) ( . k k k y   (26) where ) (k 
is the angular position of the antenna, ) ( . k  is the angular velocity of the antenna and ) (k u is the input voltage to the motor. The uncertain parameter ) (k  is proportional to the coefficient of viscous friction in the rotating parts of the antenna. It is assumed to be arbitrarily time-varying in the range of 
10 ) ( 1 . 0   k 
. Since the uncertain parameter 
) (k



is varied between 0.1 and 10, we conclude that 
Ω k A  ) (
where Ω is given as follows 
                       0 0 1 . 0 1 , 99 . 0 0 1 . 0 1 Co Ω (27)
The objective is to regulate  to the origin by manipulating u . The input constraint is 
2 ) (  k u volts. Here ) ( , k J n  is given by (5) with        0 0 0 1 Θ and . 00002 . 0  R Figure 4 shows two sequences of ellipsoids   2 1 9 2 1 , 1 / 1 , , , j , ,..., , i x Q x x j i T j i       constructed off-line.
Note that the ellipsoids are constructed such that 
j i j i , , 1     .
In this example, two sequences of ellipsoids are constructed because the polytope Ω has two vertices. Each sequence contains 9 ellipsoids.   
9 2 1 , 1 / a) 1 1 , 1 , ,..., , i x Q x x i T i        9 2 1 , 1 / b) 1 2 , 2 , ,..., , i x Q x x i T i      Fig. 4. Two sequences of ellipsoids   2 1 9 2 1 , 1 / 1 , , , j , ,..., , i x Q x x j i T j i      
, each sequence has 9 ellipsoids. 7. The state trajectories: a) 
  9 2 1 , 1 / a) 1 1 , 1 , ,..., , i x Q x x i T i        9 2 1 , 1 / b) 1 2 , 2 , ,..., , i x Q x x i T i      Fig.
1 , i  ; b) 2 , i  .
Table 1 shows the on-line computational time at each sampling instant. By using the proposed techniques, it is seen that the on-line computational time is significantly reduced. Technique 1 gives the smallest on-line computational time because only linear programming is involved in the optimization problem. The numerical simulations have been performed in Intel Core i-5 (2.4GHz), 2 GB RAM, using SeDuMi [24] and YALMIP [25,26] Next, the effect of the number of ellipsoids constructed off-line is investigated. Figures 8 and9 show the sequences of ellipsoids when the number of ellipsoids constructed off-line is varied from 9 in Fig. 4 to 3 and 5, respectively. Less computer memory is required as the number of ellipsoids constructed off-line is decreased. Note that in the construction of ellipsoids, the inequality 
, 0 ) ( ) ( 1 1 , 1 1 ,         i j j l i T i j j j i K B A Q K B A Q ....L , l ....L , j 2 1 , 2 1    
must be satisfied. This inequality tends to be violated if the number of ellipsoids constructed off-line is too small.   
3 2 1 , 1 / a) 1 1 , 1 , , , i x Q x x i T i        3 2 1 , 1 / b) 1 2 , 2 , , , i x Q x x i T i      Fig. 8. Two sequences of ellipsoids   2 1 3 2 1 , 1 / 1 , , , j , , , i x Q x x j i T j i      
, each sequence has 3 ellipsoids. 
  5 2 1 , 1 / a) 1 1 , 1 , ,..., , i x Q x x i T i        5 2 1 , 1 / b) 1 2 , 2 , ,..., , i x Q x x i T i      Fig. 9. Two sequences of ellipsoids   2 1 5 ... 2 1 , 1 / 1 , , , j , , , i x Q x x j i T j i      
, each sequence has 5 ellipsoids. 
Figure 10 shows the closed-loop responses of technique 1 when the number of ellipsoids constructed off-line is varied from 3, 5 and 9. The basic idea of this technique is to approximate the smallest ellipsoids containing the measured state. The approximated ellipsoids become closer to the ellipsoids computed online as the number of ellipsoids constructed off-line is increased. Thus, the control performance of technique 1 becomes closer to on-line robust MPC [22] as the number of ellipsoids constructed off-line is increased. Figure 11 shows the closed-loop responses of technique 2 when the number of ellipsoids constructed off-line is varied from 3, 5 and 9. Since 

Conclusions

This paper presents interpolation-based off-line robust MPC for uncertain polytopic discrete-time systems. The algorithm pre-computes off-line a sequence of state feedback gains corresponding to the sequences of ellipsoids. At each sampling time, the real-time state feedback gain is calculated by linear interpolation between the pre-computed state feedback gains. Three interpolation techniques are proposed. As compared to on-line robust MPC, the on-line computational time is significantly reduced while the same level of control performance is still ensured. 

DOI: 10 .Fig. 1 .Technique 2 :K

 1012 Fig.1. The graphical representation of the state feedback gain in each prediction horizon of technique 1. Technique 2: In the second technique, the pre-computed state feedback gains N i K i ,..., 2 , 1 ,  are interpolated in order to get the largest possible real-time state feedback gain. Since the pre-computed state feedback gains are larger as i increases, when the measured state lies between j i,  and 




  and robust stability is guaranteed. 


Fig. 2 .Technique 3 :

 23 Fig.2. The graphical representation of the state feedback gain in each prediction horizon of technique 2. Technique 3: In the last technique, the real-time state feedback gain is calculated by minimizing the violation of the constraints of the adjacent inner ellipsoids. When the measured state lies between 




  possible. The next predicted state is restricted to lie in the ellipsoidal invariant set by ( 


Fig. 3 .

 3 Fig. 3. The graphical representation of the state feedback gain in each prediction horizon of technique 3. 


Figure 5 .Fig. 5 .Figure 6 Fig. 6 .

 5566 Figure 5 shows norm of state feedback gains 


Figure 7

 7 Figure7shows the state trajectories. It can be observed that the states at each time step of techniques 2 and 3 are closer to the origin that that of technique 1. In this example, techniques 2 and 3 behave almost identically in regulating the states. 


DOI: 10 .

 10 4186/ej.2014.18.1.87 ENGINEERING JOURNAL Volume 18 Issue 1, ISSN 0125-8281 (http://www.engj.org/) 99 


DOI: 10 .Fig. 10 .

 1010 Fig. 10. The closed-loop responses of technique 1 when the number of ellipsoids constructed off-line is varied from 3, 5 and 9; a) The regulated output; b) The control input. 


K

  is larger than i K as shown in Fig.5, larger real-time state feedback gain is obtained as the number of ellipsoids is decreased. For this reason, technique 2 tends to produce faster responses as the number of ellipsoids is decreased. DOI:10.4186/ej.2014.18.1.87 ENGINEERING JOURNAL Volume 18 Issue 1, ISSN 0125-8281 (http://www.engj.org/) 101 a) The regulated output.b) The control input. 


Fig. 11 .

 11 Fig. 11. The closed-loop responses of technique 2 when the number of ellipsoids constructed off-line is varied from 3, 5 and 9; a) The regulated output; b) The control input. 


Figure 12

 12 Figure12shows the closed-loop responses of technique 3 when the number of ellipsoids constructed off-line is varied from 3, 5 and 9. The real-time state feedback gain calculated has to regulate the state from the current ellipsoids 




  to the adjacent inner ellipsoids 




  the origin so faster responses are obtained. a) The regulated output. b) The control input. 


Fig. 12 .

 12 Fig. 12. The closed-loop responses of technique 3 when the number of ellipsoids constructed off-line is varied from 3, 5 and 9: a) The regulated output; b) The control input. 




  




  




  




  




  :10.4186/ej.2014.18.1.87 



DOIENGINEERING JOURNAL Volume 18 Issue 1, ISSN 0125-8281 (http://www.engj.org/) 93 


  within Matlab R2008a environment.:10.4186/ej.2014.18.1.87 


	98

DOIENGINEERING JOURNAL Volume 18 Issue 1, ISSN 0125-8281 (http://www.engj.org/) 
Table 1 .

 1 The on-line computational time at each sampling instant. 


	Algorithms	On-line computational time (s)
	On-line robust MPC [17]	0.213
	Technique 1	0.001
	Technique 2	0.047
	Technique 3	0.101

Acknowledgement

This work was supported by Rajadapisek Sompoj Fund, Chulalongkorn University Centenary Academic Development Project, and the Thailand Research Fund (TRF). DOI:10.4186/ej.2014.18.1.87 ENGINEERING JOURNAL Volume 18 Issue 1, ISSN 0125-8281 (http://www.engj.org/) 103
Pornchai Bumroongsri, Soorathep Kheawhom
Interpolation-based Off-line Robust MPC for Uncertain Polytopic Discrete-time Systems