Parallel Branch Model Predictive Control on GPUs

Sintesi Tecnica: Controllo Predittivo Modello a Rami Paralleli su GPU

Definizione del Problema
Il Controllo Predittivo Modello a Rami (Branch Model Predictive Control - BMPC) è un potente framework di pianificazione per gestire l'incertezza in ambienti dinamici, come la guida autonoma, generando alberi di traiettorie in cui i rami corrispondono a diverse realizzazioni dell'incertezza. Tuttavia, l'ampia diffusione del BMPC è ostacolata dall'onere computazionale significativo richiesto per risolvere questi problemi, in particolare quando si trattano orizzonti di pianificazione lunghi e numerosi scenari previsti. Gli algoritmi esistenti spesso faticano a sfruttare efficientemente la struttura ad albero intrinseca o non riescono a raggiungere il parallelismo temporale, limitando la loro idoneità per applicazioni in tempo reale. Inoltre, la gestione di vincoli generici per stadio all'interno di un framework di controllo ottimo strutturato ad albero su hardware parallelo rimane una sfida.

Metodologia
Gli autori propongono un solver basato su GPU per il BMPC che integra una formulazione a shooting multiplo con un metodo Lagrangiano aumentato (Augmented Lagrangian - AL) per la gestione dei vincoli. Il nucleo dell'approccio si basa su due solver Linear Quadratic Regulator (LQR) interni progettati appositamente per sfruttare la struttura sparsa ad albero:

1. Solver LQR ad Albero Paralleli:

   • SLQR (Parallelizzazione a Livello di Scenario): Questo solver esegue una ricorsione di Riccati modificata dai nodi foglia verso la radice. Aggrega le funzioni di valore dai nodi figli in ogni stadio, consentendo la risoluzione in parallelo di problemi di minimizzazione indipendenti in ogni nodo. Questo approccio richiede meno risorse GPU ed è adatto per scenari in cui le risorse sono limitate.
   • STLQR (Parallelizzazione di Scenario e Temporale): Questo solver sfrutta l'algoritmo di parallel scan per ottenere sia il parallelismo a livello di scenario che quello temporale sia nelle passate backward (Riccati) che in quelle forward (rollout). Utilizza Funzioni di Valore Condizionate (Conditional Value Functions - CVF) e una regola di combinazione strutturata ad albero per calcolare le funzioni di valore e le leggi di controllo affini in una complessità temporale di $O(\log N)$. Questo metodo offre un parallelismo maggiore ma richiede più risorse GPU.

2. Gestione dei Vincoli tramite Lagrangiana Aumentata:
   Per affrontare i vincoli generici per stadio, gli autori utilizzano un metodo Lagrangiano aumentato (AL). Il ciclo interno utilizza un approccio iterative LQR (iLQR) in cui il problema vincolato viene approssimato come un problema LQR ad albero non vincolato utilizzando la funzione di penalità di Powell-Hestenes-Rockafellar (PHR). Un rollout lineare viene utilizzato per calcolare le perturbazioni ottimali, consentendo un'efficace parallelizzazione su GPU. Il ciclo esterno aggiorna adattivamente i moltiplicatori di Lagrange e i pesi di penalità in base alle violazioni dei vincoli, seguendo la regola BCL.

3. Implementazione:
   Il solver è implementato in JAX, utilizzando la sua differenziazione automatica e il compilatore XLA per l'accelerazione su GPU. Il framework supporta l'aritmetica a singola precisione (FP32) e doppia precisione (FP64).

Contributi Chiave
Il documento delinea tre contributi primari:

1. Dual Parallel Solvers: Lo sviluppo di due solver LQR ad albero paralleli (SLQR e STLQR) che offrono diversi livelli di parallelismo, permettendo agli utenti di selezionare il metodo appropriato in base alla dimensione del problema e alle risorse computazionali disponibili.
2. Solver BMPC Non Lineare Vincolato: L'integrazione di questi solver LQR ad albero in un solver a shooting multiplo per problemi BMPC non lineari, incorporando un metodo Lagrangiano aumentato per una gestione robusta dei vincoli e capacità di warm-starting.
3. Benchmarking e Open Source: Un benchmarking completo del solver proposto rispetto agli esistenti solver iLQR (TRAJAX, MPX) e a un solver ad alte prestazioni basato su CPU (HPIPM), insieme al rilascio di un'implementazione open-source.

Risultati Numerici
Gli autori hanno valutato il solver su due compiti distinti: problemi LQR ad albero non vincolati e pianificazione di traiettoria vincolata per un uniciclo e un pendolo quad-pendulum.

• Performance su Tree LQR: Le prestazioni dei solver basati su GPU dipendono fortemente dalla dimensione del problema e dall'hardware. Su dimensioni di problemi piccole (es. $Z = 2$ percorsi dell'albero), i solver sono significativamente più lenti del solver HPIPM basato su CPU, con STLQR che è oltre 5 volte più lento e SLQR oltre 20 volte più lento su una NVIDIA RTX 5060 Ti a causa della latenza di accesso alla memoria GPU e dell'overhead. Tuttavia, su istanze di grande scala, la performance si inverte: SLQR può superare HPIPM fino a 2 volte su istanze di grande scala ($Z \ge 128$) su RTX 5060 Ti. Allo stesso modo, su GPU di fascia alta come la RTX 4090, STLQR ottiene un'accelerazione fino a 1.9× rispetto a HPIPM per dimensioni dell'albero da medie a grandi ($Z \ge 16$).
• Gestione dei Vincoli: Nei compiti di pianificazione della traiettoria, il solver proposto (ILQRJAX) ha dimostrato un comportamento di convergenza comparabile al solver su CPU all'avanguardia IPOPT, ma con un tempo di calcolo per iterazione significativamente ridotto (ad esempio, riducendo il tempo medio per iterazione da 3.80 ms a 1.87 ms per l'uniciclo). Il solver ha gestito con successo tutti gli casi di test, mentre altri solver basati su GPU (TRAJAX, MPX) hanno incontrato difficoltà con istanze più impegnative, fallendo spesso la convergenza a causa di limitazioni di formulazione o mancanza di schemi di aggiornamento adattivi.

Significatività e Rivendicazioni
Il documento sostiene che l'approccio proposto offre una via percorribile verso il BMPC in tempo reale per problemi su larga scala, sfruttando appieno la struttura ad albero attraverso algoritmi paralleli su GPU. Gli autori sottolineano che il loro metodo raggiunge prestazioni superiori rispetto ai solver su CPU ad alte prestazioni specificamente su istanze di grande scala dove la struttura ad albero può essere efficacementamente parallelizzata. Riconoscono, tuttavia, che il solver basato su parallel scan ha un'elevata richiesta di risorse GPU, il che può limitare la scalabilità se le risorse sono sature, e che per dimensioni del problema piccole, i solver basati su CPU possono ancora superare quelli proposti. Il lavoro si posiziona come un passo verso la resa fattibile della pianificazione consapevole dell'incertezza per applicazioni complesse del mondo reale, bilanciando l'efficienza computazionale con la gestione rigorosa di vincoli e incertezza. Il lavoro futuro è identificato nell'implementazione del metodo in CUDA C++ per ottimizzare ulteriormente l'utilizzo delle risorse e potenzialmente esplorare l'aritmetica a precisione mista per migliorare la stabilità numerica sull'hardware ottimizzato per FP32.