Fast Non-Parametric Learning to Accelerate Mixed-Integer Programming for Online Hybrid Model Predictive Control

Jia-Jie Zhu, Georg MartiusarXiv 2019 · arXiv

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.

  1. Non-Parametric Learning: Instead of complex polyhedral partitions, LNMS simply stores a dataset of previously solved state-mode sequence pairs.
  2. 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."
  3. 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.
  4. Iterative Improvement: A "relabeling" scheme post-processes stored samples, gradually improving the optimality of the stored sequences over time.
The nearest-neighbor rule implicitly creates a Voronoi tessellation of the state space, approximating the true control law.

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.
Trajectory (a) and phase plot (b) of a cart system bouncing between two walls, successfully managed by the LNMS controller.

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

Abstract

Today's fast linear algebra and numerical optimization tools have pushed the frontier of model predictive control (MPC) forward, to the efficient control of highly nonlinear and hybrid systems. The field of hybrid MPC has demonstrated that exact optimal control law can be computed, e.g., by mixed-integer programming (MIP) under piecewise-affine (PWA) system models. Despite the elegant theory, online solving hybrid MPC is still out of reach for many applications. We aim to speed up MIP by combining geometric insights from hybrid MPC, a simple-yet-effective learning algorithm, and MIP warm start techniques. Following a line of work in approximate explicit MPC, the proposed learning-control algorithm, LNMS, gains computational advantage over MIP at little cost and is straightforward for practitioners to implement.
BibTeX
@misc{zhu2019fast,
  author = {Jia-Jie Zhu and Georg Martius},
  title = {{Fast Non-Parametric Learning to Accelerate Mixed-Integer Programming for Online Hybrid Model Predictive Control}},
  year = {2019},
  eprint = {1911.09214},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.09214},
}
Figure