(389c) Vector Lattice Piecewise-Affine Representation for Explicit Model Predictive Control

Model predictive control (MPC) is one of the most successful techniques to control multivariable constrained systems. The expensive online computational costs prevent a wider application of MPC to fast dynamic and/or safe critical systems. In 2002, Bemporad, Morari, Dua & Pistikopolous introduced the concept of explicit MPC (eMPC) [1]. The eMPC reformulates the online optimization problems in traditional MPC into a mutli-parametric linear/quadratic program (mpLP/mpQP). The optimal control action is calculated off-line as a continuous piecewise-affine (PWA) function of the state and reference vectors. In this way, the repetitions of online optimizations are avoided, while the optimal solutions can be readily obtained by solving a function evaluation problem of continuous PWA functions.

The eMPC is essentially a strategy of trading time for space. It pre-calculates a complete PWA control map and stores it in memory for online usage. The efficiency of the eMPC is critically dependent on finding an efficient representation model for the explicit PWA controllers. According to the canonical PWA representation theorem, there are mainly two kinds of model structures for continuous PWA functions: function-region model and function-function model [2]. The function-region models describe the polyhedral regions in the domain space explicitly. The region index is used to retrieve the corresponding affine functions. The function-function models represent the PWA functions with their local affine functions. The information on domain partitions is implicitly defined by a map between the affine functions and polyhedral regions.

Many investigations have been done to develop different function-regions models to describe the eMPC solutions [3-6]. These algorithms are successful in dealing with the PWA functions defined over a large number of polyhedral regions. However, in an eMPC application, what we need is the affine feedback gains instead of the polyhedral regions. This fact initiates the investigation of using the function-function models to describe the eMPC controls. The class of lattice PWA functions forms an ideal function-function model set. The lattice PWA function has a universal representation capability for any continuous PWA function. They can be easily constructed from the solutions of multi-parametric programs. Wen, Ma & Ydstie proposed an analytical expression of the eMPC controllers by using the lattice PWA functions [7]. A lattice eMPC control has a good performance in term of description and evaluation complexities, because the complexities are specified by the number of different affine functions. Unfortunately, the lattice representation theorem only works for scalar PWA functions. Then the lattice eMPC representation algorithm is limited to the single-input systems.

This paper proposes a vector lattice PWA representation theorem. It is proved constructively that the global structure information of a vector PWA function can be fully represented by a scalar lattice PWA function. The scalar lattice representation theorem is generalized to vector PWA functions by introducing the concept of domain structure invariance and augmented parameter matrix. An efficient algorithm is developed to represent the eMPC controllers of multi-input systems with a vector lattice PWA functions. The class of vector lattice PWA functions presents a global and compact representation for the eMPC controllers. They have a lower description and online evaluation complexities compared with the tradition representations of eMPC control without a global description model.

Two benchmark MPC problems are illustrated to demonstrate the performance and effectiveness of this approach. In both cases, the vector lattice representation algorithm reduces the number of partitions in eMPC controllers efficiently by optimally merging the polyhedral regions with the same affine gains. The lattice eMPC representations achieve a good tradeoff between the pre-calculation complexity, memory requirements and online calculation time. The lattice eMPC solutions require much less memory and off-line pre-calculation time at the cost of marginally higher online evaluation complexity, when compared with the most efficient eMPC controls based on function-regions models.

[1] A. Bemporad, M. Morari, V. Dua & E. N. Pistikopoulos, ?The explicit linear quadratic regulator for constrained systems,? Automatica, vol. 38 (1), 3-20, 2002.

[2] C.Wen, S. Wang, F. Li & M. J. Khan, ?A compact f - f model of high-dimensional piecewise-linear function over a degenerate intersection.? IEEE Transactions on Circuits Systems I, Vol. 52(4), 815-821, 2005.

[3] F. Borrelli, M. Baotic, A. Bemporad, M. Morari. ?Efficient on-Line computation of constrained optimal control.? IEEE Conference on Decision and Control, Orlando, Florida, pp. 1187-1192, 2001.

[4] P. Tondel, T. A. Johansen and A. Bemporad. ?Evaluation of piecewise affine control via binary search tree.? Automatica, Vol. 39, pp. 743-749, 2003.

[5] F.J. Christophersen, M. Kvasnica, C. N. Jones, M. Morari. ?Efficient evaluation of piecewise control laws defined over a large number of polyhedra?, European Control Conference, Kos, Greece, 2007.

[6] Tobias Geyer, Fabio Danilo Torrisi, Manfred Morari. ?Optimal complexity reduction of polyhedral piecewise affine systems.? Automatica, vol. 44, no. 7: pp. 1728-1740, 2008.

[7] C. Wen, X. Ma, and B.E.Ydstie. ?Analytical expression of explicit MPC solution via lattice piecewise-affine function?, Automatica, Vol. 45, No. 4, pp. 910-917, 2009.