Real-Time Algorithms for Model Predictive Control of Hybrid Dynamical Systems

Real-Time Algorithms for Model Predictive Control of Hybrid Dynamical Systems

Background and Motivation

Model Predictive Control (MPC) is traditionally effective for systems governed by smooth dynamics, leveraging real-time optimization of a finite-horizon OCP to respect constraints and drive multivariable systems. However, many engineering systems exhibit nonsmooth events (e.g., contact, phase transitions) foundational to hybrid dynamical systems. MPC for such systems brings substantial computational and theoretical challenges, primarily due to discontinuities and nonsmoothness in the underlying optimization problems. The hybrid systems considered here are modeled as dynamic complementarity systems (DCS), leading naturally to mathematical programs with complementarity constraints (MPCC), which fundamentally differ from standard nonlinear programs (NLPs) due to their degeneracy and violation of classical constraint qualifications.

Mathematical Programming and Sensitivity in MPCCs

The paper rigorously formulates hybrid MPC for DCS as a parametric MPCC, establishing that their solution maps are generically discontinuous and prone to infeasibility when the hybrid state undergoes discrete transitions. Under MPCC-LICQ and MPCC-SSOSC, isolated locally optimal solutions exist, and the solution map displays piecewise continuous differentiability, but only under partial upper-level strict complementarity (PULSC). In degenerate cases, discontinuities and branching in the solution map arise, as articulated in Theorems covering both continuous selections and jump discontinuities at complementarity active-set changes.

Figure 1: Solution map of a parametric MPCC, illustrating discontinuities and the necessity of QPCC approximations for accurate feedback.

Existing NLP-based MPC algorithms hinge upon piecewise affine approximations via the implicit function theorem, leveraging local sensitivity for rapid feedback; these fail in hybrid settings, owing to discontinuities in MPCC solutions. The paper demonstrates that QP subproblems become infeasible at switching events, thus motivating the need for QPCC (Quadratic Programs with Complementarity Constraints) as minimal-computation feedback correctors that inherently capture complementarity structure and switching events.

Sequential Quadratic Programming for MPCCs

The SQPCC (Sequential Quadratic Programming with Complementarity Constraints) method is presented as the natural generalization of standard SQP for MPCCs. A formal local convergence theorem is established, including contraction estimates; SQPCC achieves linear to quadratic convergence depending on the accuracy of Hessian approximations, and does not necessitate active-set stabilization or strict complementarity.

A key practical insight is that, for real-time MPC, solving a single QPCC per feedback sample suffices to maintain bounded tracking errors—even in the presence of solution jumps. The QPCC step tangently tracks the local solution branches, and, unlike QP, can detect new switching sequences online without prior enumeration or heuristics.

Figure 2: Solution maps for BNLP branches underscore how active sets change and continuity is lost at complementarity junctions.

Figure 3: Discontinuous solution mappings in MPCC, marking jump outcomes when complementarity pairs transition.

Real-Time Hybrid MPC Algorithms

Three hybrid real-time MPC algorithms are introduced:

• Hybrid Real-Time Iteration (HyRTI): Single SQPCC step per sample, with all QPCC setup computations performed in a preparation phase before the state update. Guarantees bounded error as per path-following theorems, with high efficiency for systems requiring low feedback latency.
• Hybrid Advanced-Step Controller (HyASC): Predicts the next state, solves the MPCC for this advance estimate to convergence, then applies a QPCC correction at the true state in the feedback phase, retaining accuracy when prediction errors are small and compensating even for discontinuity-jump errors.
• Hybrid Advanced-Step RTI (HyAS-RTI): Combines advanced prediction with inexact (partial) SQPCC iterations in preparation, balancing computational load and error reduction.

Figure 4: Tracking errors for SQPCC path-following schemes. Left: single-step tracking error versus parameter increment. Right: error reduction through multiple SQPCC iterations per parameter value.

These algorithms systematically minimize online computation while ensuring approximation errors remain uniformly bounded, crucial for embedded applications and real-time constraints.

Numerical Results and Application: Robotic Manipulation

The algorithms are validated on a robotic manipulation task—a two-link finger spinning an unactuated wheel through frictional and normal contacts modeled by complementarity constraints. Time-varying reference tracking is imposed in the presence of disturbances and model-plant mismatch.

Figure 5: Snapshots of a two-link finger spinning a wheel, exemplifying hybrid MPC in real-time manipulation with online contact-sequence discovery.

Closed-loop simulations reveal the ability of HyRTI, HyASC, and HyAS-RTI to automatically detect and adapt to new contact sequences with bounded tracking errors and rapid disturbance rejection. Performance is comparable to fully converged MPC, while smoothed MPCC (NLP) methods exhibit inferior tracking due to model approximation. Preparation and feedback computation times demonstrate the substantial savings for real-time algorithms—feedback delays being consistently well below the sample interval (0.1s).

Figure 6: Preparation and feedback times for various MPC algorithms, and Pareto comparison relative to tracking cost and worst-case feedback latency.

Implications and Future Directions

The work rigorously lays the theoretical and algorithmic groundwork for real-time MPC of hybrid dynamical systems, establishing that QPCC-corrected feedback is necessary to capture solution discontinuities due to switching. The algorithms are immediately practical for embedded controllers where feedback latency is paramount, and where switching sequences are unknown and must be discovered online.

The bounded-error results and solution map characterizations open new theoretical avenues for robust, stable hybrid MPC, especially under model uncertainty and adversarial disturbances. The provision of open-source implementations in nosnoc further facilitates adoption in control and robotics.

Anticipated future developments include structure-exploiting QPCC solvers, potentially leveraging Riccati-factorization analogs to unlock further computational savings. Extension to systems with discrete control decisions and broader hybrid system classes would generalize the applicability, with ongoing research into stability and robustness in such regimes.

Conclusion

This paper presents a mathematically rigorous and computationally efficient framework for real-time MPC of hybrid dynamical systems via MPCC formulations. Through the analytic study of solution map sensitivity and the development of SQPCC-based feedback algorithms, it bridges the gap between theoretical requirements and practical constraints, offering robust tools for real-time control tasks with hybrid dynamics. Numerical results validate the practical suitability, achieving rapid feedback corrections and online adaptation to discrete events.