⚡ electrical engineering

CacheMPC: Certified Cached Model Predictive Control for Quadruped Locomotion

This paper introduces Certified CacheMPC, a framework that accelerates quadruped locomotion control by caching and reusing previously solved MPC trajectories 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-08-26

📖 6 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (https://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

Robots that walk on four legs have long been a dream of engineers, but making them move with the fluid grace of a dog or a cat requires solving a complex puzzle in real time. At the heart of this challenge is a mathematical process called model predictive control. Imagine a robot constantly looking ahead, simulating thousands of possible future steps to decide which foot to place next and how hard to push against the ground. This process ensures the robot stays balanced and follows its path, but it is incredibly demanding. On the small, powerful computers built into modern robots, running these simulations fast enough to keep up with the robot's movements is a major bottleneck. If the computer takes too long to calculate the next step, the robot stumbles. For years, researchers have sought ways to speed up these calculations without sacrificing the safety and precision needed for a machine to walk on uneven ground or recover from a shove.

A team of researchers from the Indian Institutes of Technology has developed a new approach to solve this timing problem, which they call Certified CacheMPC. Instead of forcing the robot's computer to solve the complex math problem from scratch every single time it needs to move, the system remembers solutions it has already found. Because a walking robot often revisits similar situations—like the same gait pattern or the same type of terrain—the researchers realized they could store these past solutions in a digital library. When the robot encounters a situation it has seen before, the system can quickly retrieve the old solution instead of recalculating it. However, simply reusing an old answer is risky; if the current situation is even slightly different, the old answer might be wrong and cause a fall. To handle this, the team built a strict verification system. Every time the robot considers using a saved solution, a quick check confirms that the answer is still safe and accurate enough for the current moment. If the check passes, the robot uses the saved answer instantly. If it fails, the computer falls back to solving the problem from scratch, ensuring the robot never acts on a bad guess.

The researchers tested this system on a quadruped robot known as the Unitree Go2, using both high-fidelity computer simulations and a physical robot equipped with an onboard computer. In the simulations, the new method allowed the robot to make decisions roughly twenty-five times faster than the standard method when it successfully retrieved a saved solution. This speedup was not just a theoretical gain; it translated directly to the physical robot, where the un-gated version of the system operated nearly nineteen times faster on average during successful retrievals. However, the researchers noted that when the strict safety verification was fully enabled on the physical robot, the system was actually slower than the standard method because the verification process itself consumed significant time. The team ran over two thousand separate trials to see how the system performed under pressure, including scenarios where the robot was pushed hard from the side or had to climb stairs. They found that using the memory system did not make the robot less stable. In fact, at the limits of what the robot could handle, the system performed just as well as the standard method, with no statistically significant difference in how often the robot stayed upright.

A critical part of their work was proving that the system would not fail silently. They designed the verification check to act as a gatekeeper. If the robot's computer tries to use a saved solution, the check calculates a specific margin of error. If the potential error is too high, the system rejects the saved solution and forces the computer to do the hard work of solving the problem fresh. This ensures that the robot never takes a shortcut that compromises its safety. The researchers also tested what happens when the computer is under extreme time pressure, simulating a situation where the robot must make a decision in a fraction of a second. Even when the deadline was tight, the system managed to find a safe path, either by finding a good saved solution or by falling back to a previously verified safe movement if the new calculation took too long.

When the team moved the system to the actual robot hardware, the results were slightly different but still successful. The onboard computer was slower than the powerful workstation used for simulations, which meant the verification check took up a larger portion of the available time. Consequently, the system rejected more saved solutions on the physical robot than it did in the simulation, leading to fewer instances where the robot could skip the heavy calculation. Despite this, the system still provided a significant speed advantage over the standard method when it did find a match, and the robot walked smoothly without falling during the test session. The researchers noted that while the safety check worked exactly as designed, the current sample size of tests was not large enough to prove that the check made the robot significantly safer than it would have been without it. The data showed that the robot was stable in both cases, suggesting that the verification system is a reliable safety net rather than the sole reason the robot stayed upright.

The study concludes that caching, or remembering, past solutions is a viable way to make legged robots faster and more responsive, provided there is a rigorous way to verify those memories. The researchers demonstrated that they could build a system that remembers the past without being trapped by it. By combining a fast lookup method with a strict safety certificate, they created a controller that can adapt to the robot's needs in real time. The work suggests that future robots could carry a growing library of experiences, allowing them to learn from their own movements and react with the speed of a reflex while maintaining the careful planning of a mathematician. This balance between speed and safety is essential for robots that will one day walk alongside humans in complex, unpredictable environments.

Technical Summary: Certified Cached Model Predictive Control for Quadruped Locomotion

Problem Statement
Hierarchical control architectures for legged robots typically employ a low-rate Model Predictive Control (MPC) layer for trajectory planning and a high-rate Whole-Body Controller (WBC) for torque generation. While MPC is standard for ensuring robustness and tracking, its computational cost—specifically the per-cycle Quadratic Program (QP) solve—often limits the achievable update rate on embedded processors (e.g., NVIDIA Orin NX). This bottleneck restricts the closed-loop control frequency, leaving little headroom within typical 5 ms budgets. Existing acceleration methods, such as explicit MPC, suffer from exponential scaling with state dimension; neural approximations lack runtime correctness guarantees; and warm-starting offers diminishing returns when state changes are significant.

Methodology: Certified CacheMPC
The paper proposes Certified CacheMPC, a framework that caches and reuses previously computed contact-force trajectories while guaranteeing primal feasibility and bounded suboptimality through a deterministic, per-query certificate.

Architecture and Caching:
- LSH Indexing: The system uses Locality-Sensitive Hashing (LSH) to index cache entries by a feature vector $\phi \in \mathbb{R}^{18}$ , comprising measured/desired center-of-mass velocities and body-frame foot positions.
- Partitioning: The cache is partitioned by contact mode (the set of feet in contact). This ensures that within a partition, the QP structure (constraint matrices) remains identical, allowing for efficient reuse.
- Retrieval: At query time, the controller retrieves top- $K$ candidates via LSH. These candidates can be raw cached solutions or sensitivity-corrected affine extrapolations ( $\bar{U} = U^\star + K(x - x_c)$ ).
The Per-Query Certificate:
Unlike heuristic caching, every retrieved candidate must pass a rigorous certificate before application. The certificate evaluates two conditions against the current QP's KKT data:
- Primal Feasibility: Checks if the candidate control $\bar{U}$ satisfies the current constraints ( $d \le C\bar{U} \le d$ ) within a numerical tolerance ( $\epsilon_{feas}$ ).
- Suboptimality Bound: Computes a Lagrangian dual-gap quantity $\Gamma(\bar{U})$ . By weak duality, $\Gamma(\bar{U})$ provides a rigorous upper bound on the true suboptimality $\Delta J = J(\bar{U}) - J^\star$ .
- Acceptance Rule: A candidate is accepted only if $\rho_{feas} \le \epsilon_{feas}$ and $\Gamma(\bar{U}) \le \beta(\bar{U})$ , where $\beta$ is a relative/absolute cost budget. If the certificate fails, the system falls back to solving the QP online.
Bounded-Budget Controller Schedule:
The controller enforces a deterministic time budget per tick ( $T_{total} = T_{cache} + T_{solve} + T_{fallback}$ ):
- Attempt certified retrieval within $T_{cache}$ .
- If retrieval fails or time remains, solve the QP within $T_{solve}$ .
- If the deadline is missed, apply a shifted version of the last-certified feasible sequence as a fallback.

Key Contributions

Deterministic Certificate: A per-query QP certificate (Proposition 1) that upper-bounds the true suboptimality of any feasible cached proposal independent of its source (LSH, offline dictionary, or sensitivity correction).
Safety-Independent Retrieval: Proof (Proposition 2) that the safety of the applied control is independent of the retrieval policy; even if the LSH returns an arbitrary or invalid proposal, the certificate ensures only verified controls are applied.
Empirical Validation: A comprehensive evaluation involving 2,038 cold-controller trials in MuJoCo and a first-deploy session on a Unitree Go2 robot with an onboard NVIDIA Orin NX.

Results

Speedup: In simulation, the un-gated cache (no certificate) achieved a 25× median speedup. The certified variants (Cache-Cert, Cache-Full) achieved a 3.4–3.6× median speedup in simulation. On the embedded Orin NX hardware, the un-gated cache achieved an 18.7× median speedup, while the certified Cache-Full configuration was slower than the baseline due to high certificate rejection rates on the hardware (where the dual-gap bound was often violated by the specific QP data).
Locomotion Performance: Across velocity sweeps (0–0.6 m/s), all cache configurations tracked within ±14% of the no-cache baseline in terms of velocity RMSE. No falls occurred in the simulation trials.
Failure-Boundary Safety: In a targeted campaign of 600 trials ( $n=50$ per cell) at three failure-boundary conditions (high lateral push, step traversal), no statistically significant difference in closed-loop stable rates was detected between any cache variant and the no-cache baseline. The certificate's contribution to safety was not resolvable at this sample size.
Hardware Deployment: The simulation-trained cache transferred successfully to the robot. However, the high rejection rate of the certificate on hardware (approx. 71% of LSH hits were rejected) caused the certified cache to be slower than the baseline, highlighting the gap between simulation QP data and on-robot dynamics.

Significance and Claims
The paper claims that Certified CacheMPC successfully bridges the gap between the speed of caching and the safety requirements of legged locomotion. Its primary significance lies in the deterministic, source-independent certificate, which elevates a cached solution from a heuristic guess to a verified local piece of the explicit MPC law.

The authors are modest regarding the safety implications of the certificate in the current evaluation. They state that while the certificate provides a rigorous upper bound on cost suboptimality, its specific contribution to closed-loop safety (preventing falls) was not resolvable with the current sample size ( $n=50$ ) and is masked by the downstream WBC and hardware dynamics. The framework is presented as a viable method to accelerate MPC updates without sacrificing the theoretical guarantees of the underlying optimization, provided the certificate budget is respected. The work establishes a foundation for future research into tighter bounds, formal stability theorems, and online cache refinement.

Technical Summary: Certified Cached Model Predictive Control for Quadruped Locomotion

More like this