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

Titel: TurboADMM: Een structuur-uitbuitende parallelle solver voor multi-agent trajectoptimalisatie

Auteur: Yucheng Chen

1. Het Probleem

Multi-agent trajectoptimalisatie is essentieel voor de coördinatie van autonome voertuigen, robotzwermen en magazijnlogistiek. Het centrale probleem is het realiseren van veilige, optimale trajecten voor een groot aantal agenten binnen een Model Predictive Control (MPC) raamwerk.

• Uitdagingen:
  • Schalingsprobleem: Het aantal variabelen groeit lineair met het aantal agenten, maar het aantal botsingsvermijdende constraints groeit kwadratisch (voor alle-paar interacties).
  • Berekeningslast: Bestaande algemene QP-solvers (zoals OSQP en MOSEK) behandelen het probleem monolithisch (als één groot blok), wat leidt tot kubische schaling en real-time prestaties onmogelijk maakt voor meer dan 6-8 agenten.
  • Beperkingen van bestaande methoden:
    • HPIPM: Gebruikt Riccati-recursie voor tijdsstructuur, maar faalt bij dicht gekoppelde multi-agent problemen (faalt vaak bij 4+ agenten door convergentieproblemen in de interior-point methode).
    • Distributed ADMM: Kan het probleem opsplitsen, maar heeft vaak te veel iteraties nodig en start elke QP-oplossing "koud" (zonder goede initialisatie), wat inefficiënt is.

2. Methodologie: TurboADMM

TurboADMM is een gespecialiseerde QP-solver die draait op één machine (centrale controller) maar gebruikmaakt van gedeeld geheugen parallelisme (OpenMP). De kern van de methode is een synergetisch ontwerp dat drie complementaire structuren combineert om de complexiteit bijna lineair te houden ten opzichte van het aantal agenten.

De drie pijlers zijn:

1. ADMM-decompositie (Agent-niveau):

   • Het globale probleem wordt opgesplitst in lokale subproblemen per agent via de Alternating Direction Method of Multipliers (ADMM).
   • Dit behoudt de block-tridiagonale structuur van de dynamica per agent, zelfs onder dichte koppeling.
   • Agenten kunnen hun lokale QP's parallel oplossen.

2. Riccati Warmstart (Tijdsstructuur):

   • Voor de eerste ADMM-iteratie wordt een hoge-kwaliteit initialisatie gegenereerd.
   • In plaats van een "koud" startpunt (nul), wordt een onbeperkt lineair-quadratisch regelaar (LQR) probleem opgelost via Riccati-recursie.
   • Dit levert een primal-dual startpunt op dat de dynamica exact respecteert en de doelstelling benadert. Dit dient als een "hete start" voor de parametrische QP-solver (qpOASES).

3. Parametrische QP Hotstart (Iteratie-structuur):

   • Voor volgende ADMM-iteraties wordt de hotstart-mechaniek van qpOASES gebruikt.
   • Omdat opeenvolgende ADMM-iteraties zeer vergelijkbare QP-instanties produceren, wordt de QR-factorisatie en de actieve-set-informatie van de vorige iteratie hergebruikt.
   • Dit elimineert de noodzaak voor dure factorisaties bij elke iteratie.

Het werkingsprincipe:
De coördinator zendt consensusvariabelen uit (die botsingsstatus coderen). Elke agent lost zijn lokale QP op:

• Iteratie 1: Gebruikt Riccati warmstart voor een snelle convergentie.
• Iteratie >1: Gebruikt Hotstart om de factorisatie te hergebruiken.
  De coördinator update de dualvariabelen via een gesloten-formule consensus-update.

3. Belangrijkste Bijdragen

• Synergetische Architectuur: De eerste integratie van ADMM-decompositie, Riccati-based warmstart en parametrische hotstart in één solver. Dit creëert een multiplicatief effect op de prestaties.
• Schalbaarheid: Bewijs dat de solver empirisch een bijna lineaire complexiteit ($O(N^{1.2})$) bereikt ten opzichte van het aantal agenten, in tegenstelling tot de super-lineaire schaling ($O(N^{2.5})$) van monolithische solvers.
• Open Source Implementatie: Een C++-bibliotheek die beschikbaar is op GitHub, afhankelijk van qpOASES en OpenMP, gericht op gebruik in MPC-toepassingen.
• Analyse van HPIPM-falen: Een gedetailleerde analyse waarom HPIPM faalt bij dichte koppeling (ill-conditioned KKT-systemen bij interior-point methoden) en hoe ADMM dit omzeilt.

4. Resultaten en Experimenten

De solver is getest op benchmarks voor botsingsvermijding met 2 tot 14 agenten en een horizon van 20 stappen.

• Snelheidswinst:
  • Tegenover OSQP: 6,7x tot 14,8x sneller.
  • Tegenover MOSEK: 13,1x tot 23,1x sneller.
  • Voorbeeld (14 agenten):
    • BaseADMM (zonder warmstart/hotstart): ~14,3 seconden.
    • HotstartADMM (alleen hotstart): ~121 ms.
    • TurboADMM (volledig): 96 ms.
• Robuustheid:
  • HPIPM slaagt voor 2 agenten maar faalt consistent bij 4+ agenten (complementariteitsresiduen > $10^3$).
  • TurboADMM convergeert betrouwbaar tot 14 agenten.
• Ablatie-studie:
  • De Riccati warmstart reduceert het aantal QP-iteraties met een factor 20-40 voor kleine problemen en 200-230 voor grote problemen ten opzichte van een koude start.
  • De hotstart-mechanisme is cruciaal voor het amortiseren van kosten over de vele ADMM-iteraties bij schaalvergroting.
• Kwaliteit:
  • TurboADMM behoudt een hoge oplossingskwaliteit (lage tracking-error), zelfs bij grote aantallen agenten, en presteert beter dan OSQP in nauwkeurigheid terwijl het veel sneller is dan MOSEK.

5. Betekenis en Toekomstperspectief

TurboADMM positioneert zich als een directe concurrent voor algemene single-machine QP-solvers, maar is specifiek geoptimaliseerd voor multi-agent MPC.

• Praktische Impact: Het maakt real-time MPC mogelijk voor 10-20 agenten op standaard hardware (zoals een laptop of onboard computer), wat eerder alleen mogelijk was met gespecialiseerde clusters of door het opofferen van optimaliteit.
• Toekomstig Werk: Uitbreiding naar niet-lineaire dynamica (via SQP/DDP), implementatie op embedded systemen met beperkte resources, en het hanteren van heterogene agent-dynamica. Ook wordt onderzoek gedaan naar adaptieve penalty-schedulering om het aantal buitenste iteraties verder te reduceren.

Conclusie: TurboADMM overbrugt de kloof tussen de theoretische schaalbaarheid van gedistribueerde methoden en de praktische snelheid van centrale solvers, door slim gebruik te maken van de specifieke structuur van het optimalisatieprobleem.