💻 computer science

Hippo: High-performance Interior-Point and Projection-based Solver for Generic Constrained Trajectory Optimization

The paper introduces Hippo, a high-performance solver that combines interior-point methods with adaptive barrier updates and projection techniques to efficiently and robustly handle complex inequality and equality constraints in robotic trajectory optimization, outperforming existing state-of-the-art solvers in tasks like locomotion and manipulation.

Original authors: Haizhou Zhao, Ludovic Righetti, Majid Khadiv

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haizhou Zhao, Ludovic Righetti, Majid Khadiv

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 you are trying to teach a robot dog how to walk across a rocky field, or a robotic arm how to pick up a delicate vase without dropping it. To do this, you need to calculate the perfect path for the robot to take. This is called Trajectory Optimization.

Think of the robot's path as a long, winding road. The goal is to find the smoothest, fastest, and safest route from Point A to Point B, while obeying strict traffic laws (constraints):

Hard Constraints: "You cannot drive through the wall" or "Your foot must stay flat on the ground."
Inequality Constraints: "Don't go faster than 10 mph" or "Keep your balance within this range."

The Problem: The Old Navigators

For a long time, the "GPS" systems used by robots (existing solvers) had two main problems:

They were slow: Calculating the route took too long, like a GPS that takes 10 minutes to tell you to turn left.
They got stuck: If the road got bumpy or the rules were complex, the old GPS would often get confused, give up, or lead the robot into a wall (local minima).

The Solution: Enter "Hippo"

The authors of this paper introduced a new solver named Hippo. Think of Hippo as a super-smart, ultra-fast navigation system designed specifically for the chaotic, bumpy roads of robotics.

Here is how Hippo works, using simple analogies:

1. The "Interior-Point" Method: The Bubble Walker

Imagine you are walking through a crowded room full of furniture (the constraints).

Old methods might try to walk right up against the furniture. If you miscalculate, you bump into a chair and get stuck.
Hippo's method (Interior-Point) keeps you inside a giant, invisible bubble. It guides you toward the goal while ensuring you never touch the walls of the bubble. As you get closer to the goal, the bubble slowly shrinks, gently nudging you to the exact perfect path without ever crashing. This prevents the robot from getting stuck in "dead ends."

2. The "Projection" Method: The Elastic Band

Sometimes, the robot needs to hit a specific target exactly (like a hand grabbing a specific spot).

Imagine the robot's path is a rubber band. If the path drifts off the perfect line, Projection acts like a strong elastic band that instantly snaps the path back onto the correct line.
Hippo is unique because it can switch between the "Bubble" (for general rules) and the "Elastic Band" (for exact targets) instantly, depending on what the problem needs.

3. The "Parallel" Superpower: The Assembly Line

Old solvers often calculate the path step-by-step, like a single person walking a long hallway, checking every door one by one.

Hippo breaks the hallway into sections and sends a team of workers to check all doors at the same time. This is called parallelization. It's like having 10 people calculate the route simultaneously instead of one, making the process incredibly fast.

Why is Hippo Better? (The Race Results)

The paper tested Hippo against other top-tier solvers (like acados, aligator, and fatrop) in two tough scenarios:

The UR5 Arm Test: A robotic arm trying to reach random targets in 3D space.
- Result: Hippo solved more problems than the others and did it faster. It didn't get confused by the complex math of "rank-deficient" constraints (which is just a fancy way of saying "confusing, overlapping rules").
The Go2 Robot Dog Test: A quadruped robot trying to walk and hop over obstacles.
- Result: When the terrain got very hard (large jumps, slippery surfaces), the other solvers often gave up or crashed. Hippo kept going, finding a solution almost every time.

The Secret Sauce: "Globalization"

One of the biggest reasons Hippo wins is its Globalization strategy.

Imagine you are hiking and you take a step that looks good but leads you into a swamp.
Old solvers might keep walking into the swamp, thinking, "I'm close to the solution!"
Hippo has a safety net. If it realizes a step is leading to a dead end, it says, "Wait, that's a bad idea," and takes a smaller, safer step back. It's less likely to get trapped in a local minimum (a small valley that looks like the bottom of the mountain but isn't).

Summary

Hippo is a new, high-performance tool for robot motion planning.

It's Fast: It uses parallel processing to calculate paths quickly.
It's Robust: It uses a "bubble" strategy to avoid getting stuck in bad solutions.
It's Flexible: It can handle both soft rules (don't go too fast) and hard rules (don't hit the wall) seamlessly.

In short, if you want a robot to move smoothly, quickly, and reliably through a complex world, Hippo is the new GPS that ensures it gets there without crashing.

1. Problem Statement

Trajectory optimization is fundamental to model-based robotic control and motion planning (e.g., locomotion, manipulation). However, existing solvers face significant limitations when handling complex, large-scale Optimal Control Problems (OCPs) with hard constraints:

Inefficiency: Sequential Quadratic Programming (SQP) and Differential Dynamic Programming (DDP) based solvers often suffer from slow computation and poor convergence on difficult tasks.
Constraint Handling:
- Augmented Lagrangian Methods (ALM): Prone to getting trapped in local minima and require difficult-to-tune penalty parameter schedules. They struggle with inequality constraints due to explicit active-set detection.
- Interior Point Methods (IPM): While offering polynomial convergence, standard implementations can be sensitive to initial barrier parameters or computationally expensive due to inner-loop requirements for exact subproblem minimization.
Scalability: Many solvers fail to exploit the temporal sparsity of OCPs effectively or lack robust parallelization, making them unsuitable for data generation in behavior cloning or Task and Motion Planning (TAMP).

2. Methodology: The Hippo Solver

The authors propose Hippo, a solver combining Regularized Interior Point Methods (IPM) with Projection-based SQP. It is designed to handle generic OCPs, including implicit dynamics and cross-timestep constraints.

A. Core Algorithm: Projection-Based Riccati Recursion

Hippo solves the equality-constrained subproblems using a projection-based Riccati recursion:

Null-Space Projection: Instead of solving the full KKT system directly, the method projects the problem into the null-space of the equality constraints (dynamics and other equalities).
Factorization: It utilizes a null-space basis derived from the dynamics Jacobian ( $f_y$ ) to decouple the primal variables. This allows for efficient backward recursion (computing value function derivatives) and forward rollout.
Handling Rank Deficiency: The solver uses full pivoting LU factorization (via Eigen) to handle rank-deficient constraint Jacobians (common in contact dynamics), ensuring robustness where standard Cholesky factorization might fail.

B. Constraint Handling Strategies

Inequality Constraints (IPM):
- Hippo converts inequalities to slack variables and uses a Primal-Dual IPM.
- Regularization: A regularization parameter ( $\rho$ ) is introduced to prevent the Hessian from becoming ill-conditioned as slack variables approach zero. This ensures bounded modifications to the Jacobian and Hessian.
- Adaptive Barrier Strategy: Implements the Mehrotra Predictor-Corrector (MP-C) scheme with a safeguard on trial complementarity residuals to adaptively update the barrier parameter ( $\mu$ ).
- Parallelism: The solution is split into a sequential $\xi$ -step (primal/dual for equality constraints) and a parallel $(\nu, t)$ -step (for inequality multipliers and slacks), preserving sparsity and enabling parallel computation across time steps.
Equality Constraints:
- Primary Method: Handled via projection (as described above) for efficiency.
- Fallback Method: For potentially rank-deficient equality constraints, Hippo can transform them into box-constrained inequalities (similar to acados) and solve them via IPM to ensure feasibility.

C. Globalization and Refinement

Line Search: Uses a fixed-size backtracking line search with step-size bounds to ensure positivity of slack variables and multipliers.
Iterative Refinement: When close to convergence, the solver can perform iterative refinement to reduce stationarity residuals, improving accuracy without full re-factorization.
Re-initialization: If the solver stalls at a local infeasible point, it can reset the barrier parameter and re-initialize slacks to escape.

3. Key Contributions

Novel Solver Architecture: A minimalistic yet powerful implementation of regularized IPM combined with projection-based SQP, capable of handling implicit dynamics and generic constraints.
Robustness to Rank Deficiency: The use of null-space projection with robust factorization techniques allows the solver to handle difficult contact dynamics and rank-deficient constraints where other solvers fail.
Efficient Parallelization: By splitting the KKT system solution, Hippo achieves parallel computation of inequality constraint updates across time steps, significantly speeding up the process compared to sequential IPM implementations.
Minimal Tuning: The solver requires very few hand-tuned parameters, relying on systematic adaptive strategies (MP-C) rather than manual penalty scheduling.

4. Experimental Results

The authors benchmarked Hippo against state-of-the-art solvers: fatrop, acados, aligator, and mim solver.

A. UR5 Random Reaching Benchmark

Task: 100 random SE(3) reaching tasks with hard terminal constraints.
Results:
- Hippo(i) (using IPM for equality constraints) solved 65/100 problems, outperforming fatrop (56/100) and acados (36/81).
- acados struggled with local infeasible minima due to its reliance on penalized slacks.
- aligator and mim solver solved similar numbers of problems but required significantly more iterations and time.
- Speed: Hippo achieved faster wall-clock times per QP iteration due to fewer outer iterations, despite not using the highly optimized BLASFEO library like fatrop or acados.

B. Go2 Quadruped Locomotion Benchmark

Task: 2-step locomotion with trot and hopping gaits, testing both "simple" (small moves) and "hard" (large moves) scenarios with full or reduced constraints.
Results:
- Success Rate: Hippo and Hippo(i) solved nearly 100% of the "Full" constraint settings (including difficult hopping), whereas aligator and mim solver failed completely on full settings.
- Robustness: fatrop solved all tests but was significantly slower (approx. 10x slower wall time) due to lack of parallelism in its solver core.
- Convergence: Hippo demonstrated superior convergence on "Full" settings where reduced formulations (penalty-based) led to degeneracy. acados failed completely on reduced hopping tests.

5. Significance and Impact

Reliability for TAMP: Hippo provides a robust alternative for optimization-driven Task and Motion Planning (TAMP) and behavior cloning, where generating high-quality, feasible trajectories for complex, constrained tasks is critical.
Bridging the Gap: It successfully bridges the gap between the robustness of general NLP solvers (like IPOPT) and the speed of specialized OCP solvers, while adding the ability to handle hard constraints without the instability of ALM.
Future Potential: The framework is open to further integration of advanced globalization strategies (e.g., feasibility restoration phases) to further enhance robustness in extreme scenarios.

In summary, Hippo represents a significant step forward in trajectory optimization by offering a solver that is both computationally efficient (via parallelization and projection) and highly robust (via regularized IPM), making it suitable for the most challenging robotic control problems.