Approximate explicit linear MPC via Delaunay tessellation

In recent years, it has became well known that the Model Predictive Control (MPC) problem can be posed as a parametric optimization problem whose solution is given in an explicitly defined piecewise affine (PWA) function with dependence on the current state vector. Explicit MPC aims to extend the scope of applicability of MPC to situations which cannot be covered satisfactorily with existing schemes or where the on-line computations required by standard MPC are prohibitive for technical or cost reasons. A relevant problem with explicit MPC is that, with large dimensional problems, coding and implementing the exact explicit solution may be excessively demanding for the hardware available. In these cases, approximation is the way for practical implementation. In this paper we propose an algorithm that will determine an approximate PWA control that is suboptimal only over the regions of the state space which impose the constraints activation. In fact, the PWA solution is exact in the region where the unconstrained optimal controller is feasible; an approximate control is provided for the rest of the feasible state-space. The approximate solution is computed using a procedure based on the Delaunay tessellation, a particular computational geometry structure.