Set-Based Reachability and the Explicit Solution of Linear MPC using Hybrid Zonotopes

This paper presents a closed-form solution to the exact reachable sets of closed-loop systems under linear model predictive control (MPC) using the hybrid zonotope, a new mixed-integer set representation. This is accomplished by directly embedding the Karush Kuhn Tucker conditions of a parametric quadratic program within the hybrid zonotope set definition as mixed-integer constraints, and thus representing the set of all optimizers over a set of parameters. Using the set of explicit MPC solutions, it is shown how the plant's closed-loop dynamics may be propagated through an identity that is calculated algebraically and does not require solving any optimization programs or taking set approximations. The proposed approach captures the worst-case exponential growth in the number of convex sets required to represent the exact reachable set, but incurs only linear growth in the number of variables used in the hybrid zonotope set representation. Beyond reachability analysis, it is shown that the set of optimizers represented by a hybrid zonotope may be decomposed to give the explicit solution of general quadratic multi-parametric programs as a collection of constrained zonotopes.