Parallel Branch Model Predictive Control on GPUs

Technische Zusammenfassung: Paralleles Branch Model Predictive Control auf GPUs

Problemstellung
Branch Model Predictive Control (BMPC) ist ein leistungsfähiger Planungsrahmen für den Umgang mit Unsicherheit in dynamischen Umgebungen, wie etwa beim automatisierten Fahren, indem Trajektorienbäume generiert werden, bei denen die Zweige (Branches) unterschiedlichen Realisierungen von Unsicherheit entsprechen. Die weitverbreitete Anwendung von BMPC wird jedoch durch die erhebliche Rechenlast behindert, die bei der Lösung dieser Probleme entsteht, insbesondere wenn lange Planungshorizonte und zahlreiche prädizierte Szenarien vorliegen. Bestehende Solver haben oft Schwierigkeiten, die inhärente Baumstruktur effizient auszunutzen, oder scheitern an der zeitlichen Parallelisierung, was ihre Eignung für Echtzeitanwendungen einschränkt. Darüber hinaus bleibt die Handhabung allgemeiner stufenweiser Beschränkungen innerhalb eines baumstrukturierten optimalen Kontrollrahmen auf paralleler Hardware eine Herausforderung.

Methodik
Die Autoren schlagen einen GPU-basierten Solver für BMPC vor, der eine Multiple-Shooting-Formulierung mit einer Augmented-Lagrangian-Methode (AL) zur Handhabung von Beschränkungen integriert. Der Kern des Ansatzes basiert auf zwei maßgeschneiderten inneren Linear Quadratic Regulator (LQR) Solvern, die darauf ausgelegt sind, die baum-sparse Struktur auszunutzen:

1. Parallele Baum-LQR-Solver:

   • SLQR (Szenario-Ebene-Parallelisierung): Dieser Solver führt eine modifizierte Riccati-Rekursion von den Blattknoten zur Wurzel aus. Er aggregiert Wertfunktionen von Kindknoten an jeder Stufe, was es ermöglicht, die unabhängigen Minimierungsprobleme an jedem Knoten parallel zu lösen. Dieser Ansatz benötigt weniger GPU-Ressourcen und eignet sich für Szenarien, in denen die Ressourcen begrenzt sind.
   • STLQR (Szenario- & Temporale Parallelisierung): Dieser Solver nutzt den Parallel-Scan-Algorithmus, um sowohl Szenario- als auch temporale Parallelität in den Rückwärts- (Riccati) als auch in den Vorwärts-Durchgängen (Rollout) zu erreichen. Er verwendet Conditional Value Functions (CVFs) und eine baumstrukturierte Kombinationsregel, um Wertfunktionen und affine Steuerungsgesetze in einer Zeitkomplexität von $O(\log N)$ zu berechnen. Diese Methode bietet eine höhere Parallelität, erfordert jedoch mehr GPU-Ressourcen.

2. Beschränkungshandhabung via Augmented Lagrangian:
   Um allgemeine stufenweise Beschränkungen zu adressieren, verwenden die Autoren eine Augmented-Lagrangian-Methode (AL). Der innere Loop nutzt einen iterativen LQR-Ansatz (iLQR), bei dem das beschränkte Problem als unbeschränktes Baum-LQR-Problem unter Verwendung der Powell-Hestenes-Rockafellar (PHR) Straffunktion approximiert wird. Ein linearer Rollout wird verwendet, um optimale Perturbationen zu berechnen, was eine effiziente Parallelisierung auf GPUs ermöglicht. Der äußere Loop aktualisiert Lagrange-Multiplikatoren und Straffunktionsgewichte adaptiv basierend auf den Beschränkungsverletzungen, folgend der BCL-Regel.

3. Implementierung:
   Der Solver wird in JAX implementiert und nutzt dessen automatische Differenzierung sowie den XLA-Compiler zur GPU-Beschleunigung. Das Framework unterstützt sowohl Single-Precision (FP32) als auch Double-Precision (FP64) Arithmetik.

Kernbeiträge
Das Paper skizziert drei primäre Beiträge:

1. Duale parallele Solver: Die Entwicklung zweier paralleler Baum-LQR-Solver (SLQR und STLQR), die unterschiedliche Ebenen der Parallelität bieten und es den Anwendern ermöglichen, die passende Methode basierend auf der Problemgröße und den verfügbaren Rechenressourcen zu wählen.
2. Beschränkter nichtlinearer BMPC-Solver: Die Integration dieser Baum-LQR-Solver in einen Multiple-Shooting-iterativen Solver für nichtlineare BMPC-Probleme, unter Einbeziehung einer Augmented-Lagrangian-Methode für robuste Beschränkungshandhabung und Warmstart-Fähigkeiten.
3. Benchmarking und Open Source: Ein umfassendes Benchmarking des vorgeschlagenen Solvers gegenüber bestehenden iLQR-Solvern (TRAJAX, MPX) und einem hochperformanten CPU-basierten Solver (HPIPM) sowie die Veröffentlichung einer Open-Source-Implementierung.

Numerische Ergebnisse
Die Autoren evaluierten den Solver anhand zweier distinkter Aufgaben: unbeschränkte Baum-LQR-Probleme und beschränkte Trajektorienplanung für ein Unicycle (Einrad-Modell) und ein Quad-Pendel.

• Performance auf Baum-LQR: Die Performance der GPU-basierten Solver hängt stark von der Problemgröße und der Hardware ab. Bei kleinen Problemgrößen (z. B. $Z = 2$ Baum-Pfade) sind die Solver signifikant langsamer als der CPU-basierte HPIPM-Solver, wobei STLQR auf einer NVIDIA RTX 5060 Ti über 5-mal langsamer und SLQR über 20-mal langsamer ist, bedingt durch GPU-Speicherzugriffslatenz und Overhead. Bei großskaligen Instanzen kehrt sich die Performance jedoch um: SLQR kann HPIPM bei großskaligen Instanzen ($Z \ge 128$) auf einer RTX 5060 Ti um bis zu das 2-fache übertreffen. Ähnlich erzielt STLQR auf High-End-GPUs wie der RTX 4090 eine bis zu 1,9-fache Beschleunigung gegenüber HPIPM für moderate bis große Baumgrößen ($Z \ge 16$).
• Beschränkungshandhabung: In den Trajektorienplanungsaufgaben zeigte der vorgeschlagene Solver (ILKRJAX) ein Konvergenzverhalten, das mit dem State-of-the-Art CPU-Solver IPOPT vergleichbar ist, jedoch mit deutlich reduzierter Berechnung pro Iteration (z. B. Reduktion der durchschnittlichen Iterationszeit von 3,80 ms auf 1,87 ms für das Unicycle). Der Solver handhabte alle Testinstanzen erfolgreich, während andere GPU-basierte Solver (TRAJAX, MPX) mit anspruchsvolleren Instanzen zu kämpfen hatten und oft aufgrund von Formulierungsbeschränkungen oder fehlender adaptiver Update-Schemata nicht konvergierten.

Bedeutung und Ansprüche
Das Paper behauptet, dass der vorgeschlagene Ansatz einen gangbaren Weg zu Echtzeit-BMPC für großskalige Probleme bietet, indem die Baumstruktur durch parallele Algorithmen auf GPUs voll ausgeschöpft wird. Die Autoren betonen, dass ihre Methode im Vergleich zu hochperformanten CPU-basierten Solvern speziell bei großskaligen Instanzen, in denen die Baumstruktur effektiv parallelisiert werden kann, eine überlegene Leistung erbringt. Sie räumen jedoch ein, dass der Parallel-Scan-basierte Solver hohe GPU-Ressourcenanforderungen stellt, was die Skalierbarkeit einschränken kann, wenn die Ressourcen gesättigt sind, und dass bei kleinen Problemgrößen CPU-basierte Solver weiterhin besser abschneiden können. Die Arbeit positioniert sich als Schritt zur Ermöglichung von unsicherheitsbewusster Planung für komplexe, reale Anwendungen, indem sie die Recheneffizienz mit der rigorosen Handhabung von Beschränkungen und Unsicherheit abwägt. Als zukünftige Arbeit wird die Implementierung der Methode in CUDA C++ identifiziert, um die Ressourcennutzung weiter zu optimieren und potenziell Mixed-Precision-Arithmetik zur Verbesserung der numerischen Stabilität auf FP32-optimierter Hardware zu untersuchen.