CacheMPC introduces a certified caching framework that accelerates model predictive control for quadruped robots by reusing previously computed solutions from similar states, with a posteriori verification ensuring both feasibility and suboptimality bounds at every query.
Approaches to Accelerate MPC
Explicit MPC pre-computes the optimal control law as a piecewise affine function of the state by solving a multi-parametric QP offline. The online evaluation reduces to a point-location problem in a polyhedral partition of the state space. While effective for low-dimensional systems, the number of regions grows exponentially with problem dimension, making the full enumeration impractical for the 13-state MPC problems common in quadruped control. Our framework can be viewed as an online, sample-based variant of explicit MPC: each cache entry is a local affine piece of the explicit law, populated lazily from the same QPs that the controller would have solved anyway, and accepted at query time only when an a-posteriori certificate vouches for it.
Function approximation methods learn a mapping from state to MPC solution using supervised learning. MPCNET trains a neural network on MPC demonstrations and uses it for online inference. Similarly, iterative learning control (ILC) approaches maintain a library of control actions indexed by trajectory phase, achieving faster execution through lookup rather than optimization. These methods require offline training or separate optimization stages and are difficult to adapt online to changing environments.
TinyMPC achieves speedup by pre-computing and caching matrix factorizations within an ADMM solver, avoiding expensive operations at runtime. While effective for convex problems with fixed structure, it does not address the broader question of reusing full MPC solutions across similar states.
Warm-starting is a widely used technique where the solution from the previous time step initializes the solver for the current problem. While effective for reducing iteration counts, warm-starting provides diminishing returns when the state changes significantly between MPC updates, and still requires running the solver to completion.
Cache-Based and Lookup Approaches
The idea of caching and reusing optimization solutions has been explored in various control contexts. In one parameter-adaptive framework, MPC solutions indexed by system parameters are stored for fast retrieval. Our approach differs in that we cache solutions indexed by the full operational state using Locality-Sensitive Hashing (LSH), dynamically update the cache during operation, and exploit the contact-schedule structure specific to legged locomotion. To the best of our knowledge, CacheMPC is the first framework to combine LSH-based caching with contact-schedule partitioning and a per-query optimality certificate for quadruped MPC.
Certified Memory-Augmented MPC
A retrieved control is accepted only when an a-posteriori certificate, evaluated against the current predictive problem's own optimality conditions, confirms both primal feasibility and a budgeted suboptimality bound. The certificate elevates a cache entry from a heuristic neighbour in feature space to a verified local piece of the explicit-MPC law. Because the optimal-control map is piecewise affine with discontinuities at active-set boundaries, a near neighbour in feature space can lie in a different critical region; the per-query certificate is what rules this out.
Feature Vector and Candidate Generation via LSH
Each cache entry is indexed by a feature vector that compresses the operationally relevant state — the exact mathematical formulation is omitted for brevity.
Per-Query Certificate
Given a candidate control retrieved from cache, possibly with sensitivity correction, the certificate returns two quantities indicating feasibility and suboptimality, computed in one matrix–vector product.
Bounded-Budget Controller Schedule
The controller enforces a deterministic schedule at every MPC tick. Let the tick budget be partitioned into discrete time windows. Within the first window, solve the QP; if the solver returns within budget, apply the optimal control and insert into the cache. If the deadline is missed, apply a shifted last-certified feasible sequence. The controller executes this schedule at every tick. In nominal MPC the analogue of step (3) is absent: a solver that exceeds its deadline leaves the controller without a defined action.
Bounded-Budget Stress Test
The schedule was exercised under deliberately tight deadlines on a single trot trial. The schedule meets its wall-clock budget on every tick of the trial without a fall. This is descriptive single-trial evidence of behaviour under timing pressure, not a statistical comparison.
Frequently Asked Questions
How does CacheMPC ensure that a cached solution is valid for the current state? Each retrieved control is verified by an a-posteriori certificate that checks both primal feasibility and a budgeted suboptimality bound against the current MPC problem's optimality conditions.
What happens if the MPC solver exceeds its computational budget? The bounded-budget schedule applies a shifted last-certified feasible sequence, ensuring the controller always has a defined action even when the solver misses its deadline.
How does the cache scale with the dimensionality of the state space? CacheMPC uses Locality-Sensitive Hashing to efficiently index and retrieve solutions in high-dimensional feature spaces, avoiding the exponential growth of regions that limits explicit MPC.
Does CacheMPC require offline training or prior data collection? No, the cache is populated lazily during operation from the same QPs the controller would have solved anyway, with no separate training or offline optimization phase required.