The explicit solution of constrained LP-based receding horizon control

For discrete-time linear time-invariant systems with constraints on inputs and states, we develop an algorithm to determine explicity, as a function of the initial state, the solution to optimal control problems that can be formulated using a linear program. In particular, we focus our attention on a receding horizon control scheme where the performance criterion is based on a mixed 1/∞-norm (i.e., 1-norm with respect to time and ∞-norm with respect to space). We show that the optimal control profile is a piecewise linear and continuous function of the initial state. Thus, when the optimal control problem is solved at each time step according to a moving horizon scheme, the on-line computation of the resultant MPC controller is reduced to a simple linear function evaluation, instead of the typical expensive linear program required up to now. The technique proposed has both theoretical and practical advantages. From a theoretical point of view, the explicit solution gives insight on the action of the controller in different regions of the state space, and highlights conditions of degeneracy. From a practical point of view, the proposed technique is attractive for a wide range of applications where the simplicity of the on-line computational complexity is a crucial requirement.