Constrained Dynamic Programming of Hybrid Systems and Explicit Model Predictive Control – a Multi-Parametric Programming Approach

In this work, we consider the solution of constrained dynamic programming problems involving hybrid linear models, such as piece-wise affine systems, where binary variables are introduced to describe the switches between different affine dynamics of the system. Linear or quadratic objective functions are considered, resulting in mixed integer linear (MILP) or quadratic (MIQP) formulations.
First, we present a multi-parametric (mp) programming approach to solve such hybrid linear constrained problems that involves: (i) reformulation of the original problem as an mp-MILP or mp-MIQP; (ii) decomposition of the problem into a set of sub-problems using dynamic programming; (iii) sequentially solving the resulting set of sub-problems of smaller dimensionality using suitable mp-MILP or mp-MIQP algorithms; (iv) obtaining the enclosure of parametric solutions as a piece-wise affine function of the vector of parameters.
Based on this, we then show how, by recasting model predictive control problems for hybrid systems within a dynamic programming formulation, the explicit solution of the hybrid MPC problem can be efficiently computed. By considering the states of the system to be controlled as parameters, the explicit control law is obtained as a piece-wise affine function of the states, thus reducing the computational burden involved in the online implementation of such controller to simple function evaluations.
Finally, we show how this approach can be extended to account for the presence of different types of uncertainty in the model equations. The work here presented outlines a general framework towards the design of explicit robust controllers for hybrid systems.