💻 computer science

TurboADMM: A Structure-Exploiting Parallel Solver for Multi-Agent Trajectory Optimization

TurboADMM is a specialized single-machine QP solver that achieves near linear scalability in multi-agent trajectory optimization by co-designing ADMM decomposition for parallel agent subproblems, Riccati warmstarts for temporal initialization, and parametric hotstarts for reusing KKT factorizations across iterations.

Original authors: Yucheng Chen

Published 2026-02-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yucheng Chen

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 the traffic controller for a massive, chaotic city where hundreds of self-driving cars need to swap lanes, avoid each other, and reach their destinations at the exact same time.

This is the problem of Multi-Agent Trajectory Optimization. It's like trying to choreograph a dance for 14 robots in a room the size of a tennis court, where every single robot must avoid bumping into every other robot, all while moving as fast as possible.

The paper introduces a new tool called TurboADMM to solve this. Here is the breakdown of why it's needed and how it works, using simple analogies.

The Problem: The "Monolithic" Traffic Jam

Before TurboADMM, solving this problem was like trying to direct the entire city's traffic from a single, giant control tower using a monolithic (all-in-one) approach.

The Old Way (OSQP, MOSEK): Imagine one super-busy traffic cop trying to calculate the path for every single car simultaneously in one giant brain. As soon as you add more cars, the math explodes. It's like trying to solve a Sudoku puzzle where every number you place affects every other number on the board. By the time the computer figures out the solution for 14 cars, the traffic has already crashed.
The "Structure" Way (HPIPM): Some smarter solvers tried to look for patterns (like knowing cars move in lines). But when the cars get too crowded and interact with everyone (dense coupling), these solvers get confused and crash, just like a traffic cop trying to manage a gridlock by only looking at straight lines.

The Solution: TurboADMM (The Smart Swarm)

TurboADMM changes the game. Instead of one giant brain trying to do everything, it uses a team of specialists working together in three clever ways. Think of it as a high-tech traffic management system with three superpowers:

1. The "Parallel Team" (ADMM Decomposition)

Instead of one cop managing 14 cars, TurboADMM hires 14 different traffic cops.

How it works: Each cop is assigned one car. They all work at the same time (in parallel) on their own computers.
The Catch: They can't just ignore each other. They have to agree on where they will be so they don't crash.
The Magic: They talk to a central "Coordinator" who says, "Okay, Car A, you're too close to Car B. Move your plan slightly." The cops then adjust their individual plans simultaneously. This turns one giant, impossible math problem into 14 smaller, easy ones.

2. The "Crystal Ball" (Riccati Warmstart)

When a traffic cop starts a new task, they usually start with a blank slate (a "cold start"). They have to guess where to go, check if it's safe, guess again, and repeat. This takes forever.

The Turbo Trick: TurboADMM gives every cop a Crystal Ball (a mathematical tool called Riccati recursion).
How it works: Before the cop even starts calculating, the Crystal Ball predicts a "good enough" path based on the physics of the car. It's like giving the cop a head start where they are already 90% of the way to the solution.
Result: Instead of guessing for 100 steps, they only need to make tiny adjustments for 5 steps.

3. The "Shortcut Memory" (QP Hotstart)

In a busy city, the traffic situation changes only slightly from one second to the next. The cars are moving, but the rules are similar.

The Turbo Trick: TurboADMM remembers the math it did a split-second ago.
How it works: If the cop solved a problem at 10:00:01, they don't need to re-calculate the whole thing at 10:00:02. They just reuse the "skeleton" of the previous answer and tweak it.
Result: This saves massive amounts of time, like using a "Copy-Paste" function instead of retyping a whole document.

The Result: Speed and Safety

The paper tested this against the old "giant brain" solvers (OSQP and MOSEK) and the "pattern-finding" solver (HPIPM).

The Scale: They tested with 2 to 14 agents (cars/robots).
The Speed:
- For 14 agents, the old solvers took seconds (too slow for real-time driving).
- TurboADMM did it in milliseconds (fast enough to react instantly).
- It was up to 23 times faster than the best commercial solvers.
The Failure of Others: The "pattern-finding" solver (HPIPM) worked fine for 2 cars but completely gave up when there were 4 or more. TurboADMM handled 14 with ease.

The Bottom Line

TurboADMM is like upgrading from a single, overworked traffic cop trying to manage a riot, to a swarm of smart drones that:

Split the work up so everyone does a little bit.
Use a crystal ball to guess the right answer instantly.
Remember what they just did to save time on the next step.

It allows robots and self-driving cars to coordinate complex maneuvers in real-time, even when the traffic is incredibly dense, making autonomous fleets in warehouses or cities actually possible.

1. Problem Statement

The paper addresses the computational bottleneck in Multi-Agent Trajectory Optimization, specifically for densely coupled systems (e.g., autonomous vehicle fleets in urban environments or warehouse robots).

The Challenge: As the number of agents ( $N$ ) increases, the problem dimension scales linearly, but the collision avoidance constraints scale quadratically ( $O(N^2)$ ).
Limitations of Existing Solvers:
- General-purpose solvers (OSQP, MOSEK): Treat the problem as a monolithic Quadratic Program (QP). They fail to exploit the decomposable structure, leading to cubic scaling ( $O(N^3)$ ) and inability to solve problems with $>6-8$ agents in real-time.
- Structure-exploiting solvers (HPIPM): Leverage temporal structure via Riccati recursion but struggle with dense pairwise coupling constraints, often failing to converge for $N \ge 4$ agents due to ill-conditioned KKT systems.
- Distributed ADMM methods: While they decompose the problem, traditional implementations suffer from slow convergence and high per-iteration costs due to "cold-starting" QP subproblems.

2. Methodology: TurboADMM

The authors propose TurboADMM, a specialized single-machine solver that achieves near-linear complexity in agent count by synergistically co-designing three complementary components:

A. ADMM Decomposition (Agent-Level Parallelism)

The global optimization problem is decomposed into per-agent subproblems using the Alternating Direction Method of Multipliers (ADMM).
Consensus Variables: Collision avoidance is handled via consensus variables ( $z_{ij,t}$ ) representing agreed-upon relative positions between agent pairs.
Parallelization: Each agent solves its local QP independently. This allows for massive parallelization on multi-core CPUs using OpenMP, preserving the block-diagonal structure of the dynamics while handling dense coupling through dual variable updates.

B. Riccati Warmstart (Temporal Structure Exploitation)

The Innovation: Instead of initializing the first ADMM iteration with a trivial "cold start" (e.g., zero variables), TurboADMM uses Riccati recursion to compute a high-quality primal-dual initialization.
Mechanism: It temporarily ignores inequality constraints to solve an unconstrained affine Linear Quadratic Regulator (LQR) problem. This provides a trajectory-consistent starting point that satisfies dynamics exactly.
Benefit: This "warm start" significantly reduces the number of active-set iterations required by the QP solver in the first ADMM step, which is typically the most expensive.

C. Parametric QP Hotstart (Iteration Similarity)

Mechanism: The solver leverages qpOASES, a parametric QP solver capable of "hotstarting."
Strategy: Since consecutive ADMM iterations produce similar QP instances (as consensus variables gradually converge), qpOASES reuses the QR factorization and active set information from the previous iteration.
Benefit: This drastically reduces the computational cost of subsequent ADMM iterations, amortizing the factorization cost across the optimization process.

The Synergy:

Riccati Warmstart makes the first ADMM iteration efficient by providing a smart initialization.
qpOASES Hotstart makes subsequent ADMM iterations efficient by reusing matrix factorizations.
ADMM Decomposition enables parallel execution across agents.

3. Key Contributions

Synergistic Solver Architecture: The first integration of Riccati-based warmstarts directly into the first ADMM iteration, combined with parametric hotstarting, specifically for densely coupled multi-agent MPC.
Near-Linear Scalability: Demonstrated empirical scaling of approximately $O(N^{1.2})$ , a significant improvement over the $O(N^{2.5})$ to $O(N^3)$ scaling of monolithic solvers.
Open-Source Implementation: A lightweight C++ library (requiring only qpOASES and OpenMP) released on GitHub, designed for standard multi-core hardware rather than distributed clusters.

4. Experimental Results

Experiments were conducted on multi-agent collision avoidance benchmarks (2 to 14 agents, 20-step horizon) on an Intel Core i7-155H CPU.

Speedup vs. State-of-the-Art:
- vs. OSQP: 6.7× to 14.8× speedup.
- vs. MOSEK: 13.1× to 23.1× speedup.
- vs. HPIPM: HPIPM failed to converge for 4+ agents, while TurboADMM succeeded.
Ablation Study (Impact of Components):
- BaseADMM (Cold Start): 14.3 seconds for 14 agents.
- HotstartADMM (qpOASES Hotstart only): Reduced to 121ms.
- TurboADMM (Riccati + Hotstart): Reduced to 96ms.
- Insight: The combination yields multiplicative gains; neither component alone achieves the full performance.
Solution Quality:
- TurboADMM maintained high solution fidelity. For small scales (2-4 agents), it achieved ~10× lower tracking error than OSQP/MOSEK due to better initialization.
- For large scales (14 agents), it balanced speed and accuracy better than commercial solvers, which were too slow to be practical.
HPIPM Failure Analysis: The paper details that HPIPM fails on dense coupling because the perturbed KKT system becomes ill-conditioned, causing line search failures. TurboADMM avoids this by preserving block-tridiagonal structure at the agent level.

5. Significance

Real-Time Feasibility: TurboADMM enables real-time Model Predictive Control (MPC) for 10–20 agents at control rates of 10–204 Hz on standard hardware, a regime previously inaccessible to centralized solvers.
Paradigm Shift: It challenges the notion that multi-agent problems must be solved either via slow monolithic solvers or physically distributed clusters. It proves that algorithmic decomposition (ADMM) combined with smart initialization (Riccati) and factorization reuse (Hotstart) can solve dense coupling problems efficiently on a single machine.
Practical Application: The open-source nature and reliance on standard libraries make it immediately deployable for robotics research and industrial applications (e.g., warehouse automation, autonomous traffic management).

In summary, TurboADMM bridges the gap between theoretical optimality and computational tractability in multi-agent systems by systematically exploiting temporal dynamics, agent decomposition, and iteration similarity.