💻 computer science

CacheMPC: Certified Cached Model Predictive Control for Quadruped Locomotion

This paper presents Certified CacheMPC, a framework that accelerates quadruped locomotion control by caching and reusing MPC solutions with rigorous feasibility and suboptimality certificates, achieving significant speedups on both simulation and hardware without compromising closed-loop stability.

Original authors: Nimesh Khandelwal, Mehul Anand, Shakti S. Gupta, Mangal Kothari

Published 2026-06-29

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Nimesh Khandelwal, Mehul Anand, Shakti S. Gupta, Mangal Kothari

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a four-legged robot dog (like a Unitree Go2) trying to run across a room. To do this safely, it needs a "brain" that constantly calculates how hard to push with each foot to stay balanced. This brain uses a complex math tool called Model Predictive Control (MPC).

Think of MPC as a chess player who looks 10 moves ahead. Every time the robot takes a step, the brain has to solve a massive, difficult math puzzle to figure out the perfect force for the next few steps.

The Problem:
Solving this puzzle takes time. On the robot's small computer (an NVIDIA Orin NX), this calculation is so slow that it barely keeps up with the robot's movements. It's like trying to solve a Sudoku puzzle while running a marathon; you might finish the puzzle, but you've already tripped over a rock because you were too slow.

The Solution: Certified CacheMPC
The authors propose a clever shortcut called Certified CacheMPC. Here is how it works, using a simple analogy:

1. The "Recipe Book" (The Cache)

Imagine the robot has a giant cookbook of "recipes" for how to push its feet. These recipes are stored in a Cache.

The Old Way: Every time the robot needs to move, it ignores the cookbook and tries to cook the meal from scratch (solving the math puzzle from zero). This is slow.
The New Way: The robot looks up the recipe in the cookbook. Since the robot often walks in similar patterns (like trotting), it has likely solved this exact puzzle before. It just grabs the old solution.

2. The "Safety Inspector" (The Certificate)

Here is the tricky part. Just because a recipe is in the book doesn't mean it's safe to use right now. Maybe the robot is slightly off-balance, or the floor is slippery. If it uses an old recipe blindly, it might fall.

This is where the "Certified" part comes in.

When the robot pulls a recipe from the book, a Safety Inspector (the Certificate) checks it instantly.
The Inspector asks two questions:
1. "Is this recipe physically possible?" (Primal Feasibility)
2. "Is this recipe good enough?" (Suboptimality Bound)
If the recipe passes the inspection, the robot uses it immediately. If it fails, the robot throws the recipe away and solves the math puzzle from scratch.

The Magic Analogy:
Think of it like a GPS navigation app.

Standard MPC: You ask the GPS for directions every single second. It recalculates the whole route from scratch every time. It's accurate but slow.
CacheMPC: The GPS remembers the route you took 5 minutes ago. It says, "Hey, you're still on this road! Let's just reuse that route."
The Certificate: Before reusing the old route, the GPS checks the live traffic. "Is the road still open? Is there a new accident?" If yes, it reuses the route instantly. If no, it recalculates.

What They Found (The Results)

The researchers tested this on a robot dog in a computer simulation and then on a real robot.

Speed: In the simulation, using the "recipe book" made the robot's brain 25 times faster on average. On the real robot, it was 18.7 times faster.
Safety: They tested the robot under very stressful conditions (pushing it hard, making it climb stairs). They found that using the "recipe book" (even with the safety inspector) did not make the robot fall more often than solving the math from scratch.
The Catch: On the real robot, the "Safety Inspector" was very strict. It rejected many old recipes because the real world is messier than the simulation. This meant the robot had to solve the puzzle from scratch more often than in the simulation, which slowed it down a bit compared to the simulation results. However, it was still much faster than having no book at all.

The Bottom Line

This paper introduces a way to make robot brains faster by remembering past solutions, but with a strict "safety check" to ensure those old solutions are still safe to use. It proves that robots can be much quicker without becoming reckless, provided they have a way to verify their shortcuts.

Technical Summary: Certified CacheMPC for Quadruped Locomotion

Problem Statement

Model Predictive Control (MPC) serves as the standard predictive layer in hierarchical quadruped controllers, optimizing contact forces over a finite horizon. However, the computational cost of solving the Quadratic Program (QP) at every control cycle limits the achievable update rate on embedded processors (e.g., NVIDIA Orin NX). While legged gaits revisit bounded regions of the state space, suggesting opportunities for solution reuse, existing methods face significant trade-offs:

Explicit MPC suffers from exponential growth in polyhedral regions with problem dimension.
Neural approximations lack runtime correctness guarantees.
Warm-starting offers diminishing returns when state changes are significant.
Unverified caching lacks safety guarantees, risking the application of infeasible or highly suboptimal controls.

The core challenge is to accelerate MPC via caching without compromising the safety and feasibility guarantees required for closed-loop stability in legged locomotion.

Methodology: Certified CacheMPC

The paper proposes Certified CacheMPC, a framework that combines Locality-Sensitive Hashing (LSH) for fast retrieval with a deterministic, a-posteriori certificate to validate cached solutions.

1. Architecture and Retrieval

Partitioned Cache: The cache is partitioned by contact mode (the set of feet in contact). This ensures that the QP structural pattern (constraint shape and active swing/stance bits) remains consistent within a partition.
Feature Vector: Entries are indexed by an 18-dimensional feature vector $\phi$ comprising measured and desired Center of Mass (CoM) velocities and body-frame foot positions.
LSH Lookup: Approximate nearest-neighbor search is performed within the relevant contact-mode partition using LSH to generate candidate trajectories.
Sensitivity Correction: Retrieved solutions can be upgraded from constant proposals to first-order affine proposals using stored sensitivity matrices ( $K = \partial U^*/\partial x$ ), correcting for small state deviations.

2. The Per-Query Certificate

A cached candidate $\bar{U}$ is accepted only if it satisfies a deterministic certificate evaluated against the current QP's KKT data. The certificate verifies two conditions:

Primal Feasibility: The candidate must satisfy the current constraints within a numerical tolerance ( $\rho_{feas} \leq \epsilon_{feas}$ ).
Suboptimality Bound: The framework computes a Lagrangian dual-gap quantity $\Gamma(\bar{U})$ $Γ (\overset{ˉ}{U})$ . By weak duality, this quantity upper-bounds the true suboptimality $\Delta J = J(\bar{U}) - J^*$ $Δ J = J (\overset{ˉ}{U}) - J^{*}$ .
- The certificate is evaluated using the unconstrained relaxation ( $\lambda=0$ ) to ensure validity regardless of the candidate's origin.
- Acceptance requires $\Gamma(\bar{U}) \leq \beta(\bar{U})$ , where $\beta$ is a state-dependent budget (absolute + relative error).

3. Bounded-Budget Controller Schedule

To guarantee real-time performance, the controller enforces a strict schedule per tick:

Retrieval Phase: Attempt to find a top- $K$ certified candidate within a time budget $T_{cache}$ .
Solve Phase: If no candidate is certified, solve the QP within a deadline $T_{solve}$ .
Fallback: If deadlines are missed, apply a shifted version of the last-certified feasible sequence.

Key Contributions

Deterministic Per-Query Certificate: A novel certificate (Proposition 1) that provides a rigorous upper bound on the suboptimality of any feasible cached proposal, independent of its source (LSH, offline dictionary, or sensitivity correction).
Bounded-Budget Schedule: A controller logic that integrates top- $K$ certified retrieval, deadline-bounded solving, and a safe fallback mechanism, ensuring the controller never stalls or acts without a defined action.
Comprehensive Evaluation: A large-scale evaluation involving 2,038 usable cold-controller trials in MuJoCo and a first-deploy session on a Unitree Go2 robot with an onboard NVIDIA Orin NX.

Experimental Results

Simulation Performance (Unitree Go2 in MuJoCo)

Speedup: The un-gated cache (Cache-NoCert) achieved a 25× median speedup in solve time compared to the no-cache baseline. The certified variants (Cache-Cert, Cache-Full) achieved a 3.4–3.6× median speedup due to the overhead of the certificate evaluation on every tick.
Tracking: All cache configurations tracked velocity within $\pm14\%$ of the baseline. No statistically significant difference in tracking RMSE was observed.
Safety at Failure Boundaries: In a targeted campaign of 600 trials ( $n=50$ per cell) at three failure-boundary conditions (lateral pushes and step traversal), no statistically significant difference in closed-loop stable rates was detected between cache variants and the no-cache baseline. The largest observed difference (Cache-Full vs. Convex on WBC 80N push) had a p-value of 0.027, which did not survive Holm–Bonferroni correction.

Hardware Deployment (On-Robot NVIDIA Orin NX)

Speedup: The un-gated cache achieved an 18.7× median speedup on hardware.
Certified Performance: The certified cache (Cache-Full) was slower than the no-cache baseline on hardware. This inversion occurred because the certificate rejected the majority of LSH candidates (approx. 71% rejection rate) due to the specific QP data on the robot, forcing a fallback to the full QP solve. The certificate acted as designed, preventing the use of suboptimal cached solutions at the cost of speed in this specific deployment.
Stability: No falls were observed across push events for any configuration.

Significance and Claims

The paper positions Certified CacheMPC as a framework that elevates caching from a heuristic neighbor search to a verified local piece of the explicit-MPC law.

Safety Guarantee: The primary contribution is the deterministic certificate, which ensures that any applied control satisfies a known bound on suboptimality and feasibility, regardless of how the candidate was retrieved.
Operational Role: The authors modestly claim that the certificate functions as a "verifiable upper bound" rather than a runtime safety mechanism whose effect is resolvable in the current sample size. The evaluation suggests that while caching accelerates computation, the certificate's contribution to closed-loop safety (preventing falls) is not statistically resolvable at $n=50$ due to the robustness of the downstream Whole-Body Controller (WBC) and the specific failure boundaries tested.
Hardware Reality: The hardware results highlight a critical trade-off: on resource-constrained embedded systems, the overhead of strict certification can negate speed gains if the cache hit rate for certified solutions is low. The framework successfully transfers simulation-trained caches to hardware but requires careful tuning of the certificate budget or cache population strategies to realize speedups in practice.

The paper concludes that while the framework successfully decouples solution retrieval from safety verification, future work is needed to tighten the dual-gap bounds (e.g., by reusing cached multipliers) and to characterize the safety benefits in regimes with higher model mismatch or more aggressive failure boundaries.