The paper introduces LNMS (Learning from Nearest-neighbor Mode Sequences), an algorithm that accelerates hybrid Model Predictive Control (MPC) by predicting discrete decision sequences from past experiences. By using a non-parametric "lazy learning" approach, it achieves up to 17x speedups over standard solvers, making real-time control of complex hybrid systems like robots in contact much more practical.
The Challenge of Hybrid Systems
Many physical systems are "hybrid," meaning their behavior changes abruptly due to discrete events—think of a legged robot making and breaking contact with the ground, or a ball bouncing off a wall. Controlling these systems optimally using MPC typically requires solving a Mixed-Integer Program (MIP) at every time step.
While theoretically elegant, MIPs are computationally expensive because they involve a combinatorial search over all possible sequences of discrete events (modes). This often makes them too slow for high-speed, real-time applications. Previous attempts to pre-calculate these solutions ("explicit MPC") struggle with the "curse of dimensionality," becoming unmanageable as the system complexity grows.
Methodology: Learning from Nearest-neighbor Mode Sequences
The authors propose a "learning-control" algorithm called LNMS. Its core insight is that the geometric structure of hybrid MPC solutions—the specific sequence of modes the system will follow—can be learned from previously visited states.
- Non-Parametric Learning: Instead of complex polyhedral partitions, LNMS simply stores a dataset of previously solved state-mode sequence pairs.
- Nearest Neighbor (NN) Lookup: For a new state, the algorithm finds the closest state in its database and tries its associated mode sequence as a "warm start."
- Fallback to MIP: If the predicted sequence is feasible, the problem simplifies into a fast Quadratic Program (QP), solvable in microseconds. If it's infeasible, the algorithm falls back to a full MIP solver and adds the new result to its dataset.
- Iterative Improvement: A "relabeling" scheme post-processes stored samples, gradually improving the optimality of the stored sequences over time.
Experimental Evaluation
The researchers evaluated LNMS on three simulated hybrid dynamical systems: a basic cart-wall scenario, a complex two-wall cart system with high initial velocities, and a pendulum with an elastic wall.
Key Results
- Computational Speedup: LNMS achieved wall-clock speedups ranging from 2x to 17x compared to the industry-standard Gurobi MIP solver.
- Reduced Solver Calls: As the dataset grows, the probability of needing the expensive MIP solver drops toward zero. In tests, the fraction of required MIP runs plummeted after just a few thousand samples.
- Handling Complexity: The method successfully scaled to complex control laws featuring nearly 500 distinct regions of different mode sequences.
Discussion and Future Work
The primary bottleneck in hybrid MPC is finding any feasible mode sequence. Once a feasible sequence is found via lookup, the continuous optimization part is trivial. Because LNMS falls back to a standard hybrid MPC solver when predictions fail, it inherits the stability and feasibility guarantees of the underlying MPC framework.
While tree-based structures make lookups fast, extremely large datasets could eventually slow down the search or consume significant memory. Future directions include using LNMS as an efficient "oracle" to generate data for training parametric policies, like neural networks, while maintaining the safety of the MPC framework.
Summary updated