Abstract
We present CODEV, a Matlab-based tool for verifying systems employing Model Predictive Control (MPC). The MPC solution is computed offline and modeled together with the physical system as a hybrid automaton, whose continuous dynamics may be nonlinear with a control solution that remains affine. While MPC is a widely used synthesis technique for constrained and optimal control in industry, our tool provides the first automated approach of analyzing these systems for rigorous guarantees of safety. This is achieved by implementing a simulation-based verification algorithm for nonlinear hybrid models, with extensions tailored to the structure of the MPC solution. Given a physical model and parameters for desired system behavior (i.e. performance and constraints), CODEV generates a control law and verifies the resulting system will robustly maintain constraints. We have applied CODEV successfully to a set of benchmark examples, which illuminates its potential to tackle more complex problems for which MPC is used.
Introduction
Model Predictive Control (MPC) has become the industry standard for managing complex systems with strict constraints, such as autonomous vehicles or chemical processing plants. By solving an optimization problem over a finite prediction horizon, MPC determines optimal control actions. However, a significant "safety gap" exists: MPC typically only guarantees safety within its immediate horizon. There is no inherent mathematical proof that the system will remain safe over the long term, particularly when the internal linear model used by the controller differs from the complex, nonlinear reality of the physical system. Furthermore, the sheer complexity of MPC solutions—which can contain thousands of discrete control "modes"—makes manual formal modeling and verification practically impossible.
Methodology
CODEV bridges the gap between control design and formal methods through an automated three-step pipeline:
- Explicit MPC Synthesis: Instead of solving optimization problems online, CODEV utilizes the Multi-Parametric Toolbox (MPT3) to compute an "explicit" solution offline. This results in a piecewise affine (PWA) control law where the state-space is partitioned into numerous regions, each governed by a specific linear control rule.
- Hybrid Automaton Modeling: The tool automatically translates the closed-loop system into a hybrid automaton. Each partition from the MPC solution is mapped to a discrete "mode" within the automaton, enabling the tool to handle the vast number of sub-functions characteristic of modern MPC.
- Simulation-Based Reachability: CODEV employs a reachability algorithm to compute "reachtubes"—mathematical envelopes encompassing all possible future trajectories. If these tubes never intersect with predefined "unsafe sets," the system is certified as RobustlySafe.
A key innovation is the ability to design controllers using efficient linear mathematics while verifying them against the actual nonlinear dynamics of the physical system. However, the authors note a technical challenge termed the "cost of time": frequent control updates can lead to "over-approximation bloat," where reachtubes expand too quickly to provide definitive safety results.
Experimental Results
The authors evaluated CODEV across several control benchmarks, including a Double Integrator, a 4D Navigation System, and a Magnetic Pointer model.
As shown in the results table, CODEV successfully certified the "RobustlySafe" property for the double integrator, navigation, and cruise control benchmarks. While MPC solve times were rapid (e.g., 1.25s for the double integrator), verification runtimes were higher but remained manageable, ranging from 19s to 165s.
The "Magnetic Pointer" benchmark provided critical insights into edge cases. In one configuration (Pointer C), the tool returned an "Infeasible" result, indicating that the system state could drift into regions where the MPC had no valid solution. This demonstrates CODEV's utility in identifying potential failures that traditional simulation might miss.
Conclusion and Future Work
CODEV represents a significant step toward automated safety certification for MPC-based systems. Current limitations include the "wrapping effect," where over-approximation in reachtubes compounds over long horizons, and the requirement for manual Jacobian input. Future development will focus on automating system linearization, supporting Quadratic Programming (QP) for energy-efficient control, and improving scalability to higher-dimensional systems to mitigate the "curse of dimensionality" inherent in formal verification.
Summary updated