cuNRTO: GPU-Accelerated Nonlinear Robust Trajectory Optimization

1. Il Problema

L'ottimizzazione della traiettoria è fondamentale per la pianificazione e il controllo dei sistemi robotici. Tuttavia, i sistemi reali operano in ambienti incerti (disturbi esterni, errori di modellazione). Per garantire la sicurezza, è necessario soddisfare i vincoli (es. evitare ostacoli, limiti degli attuatori) per tutte le possibili realizzazioni di un'incertezza deterministica limitata (insieme limitato), non solo in media.

Questo approccio, noto come Ottimizzazione Robusta Non Lineare (NRTO), trasforma il problema in una forma gestibile tramite riformulazione dei vincoli, generando sottoproblemi di Programmazione Conica di Secondo Ordine (SOCP).

• Sfida principale: I metodi esistenti per risolvere questi sottoproblemi SOCP (come i metodi a punto interno su CPU) diventano computazionalmente proibitivi per sistemi ad alta dimensionalità o con molti vincoli, limitando l'uso in tempo reale.
• Obiettivo: Sviluppare un framework che acceleri drasticamente la risoluzione di questi problemi sfruttando il parallelismo massivo delle GPU.

2. Metodologia

Il paper propone cuNRTO, un framework che implementa due nuove architetture di ottimizzazione su GPU, basate sul framework NRTO originale. L'approccio generale mantiene un ciclo esterno di linearizzazione successiva (SL) eseguito sulla CPU, mentre il ciclo interno di ottimizzazione (che risolve i sottoproblemi SOCP) viene eseguito interamente sulla GPU.

Le due architetture principali sono:

A. NRTO-DR (Douglas-Rachford Splitting)

Questa metodologia risolve i sottoproblemi costosi del ciclo interno NRTO utilizzando il metodo di splitting di Douglas-Rachford (DR).

• Funzionamento: Trasforma il problema SOCP in una forma risolvibile tramite iterazioni DR.
• Vantaggi: Sfrutta proiezioni parallele sui coni di secondo ordine (SOC) e risoluzioni dirette sparse.
• Implementazione GPU: Utilizza kernel CUDA personalizzati per le proiezioni SOC e cuDSS per la fattorizzazione sparsa del sistema KKT (che è costante durante le iterazioni interne), riducendo drasticamente le operazioni matriciali.

B. NRTO-FullADMM (Alternating Direction Method of Multipliers)

Questa è una variante innovativa che riformula ulteriormente il ciclo interno ADMM per massimizzare l'efficienza.

• Innovazione: Sostituisce la struttura nidificata di NRTO-DR integrando direttamente le proiezioni parallele dei blocchi SOCP all'interno degli aggiornamenti ADMM.
• Architettura On-Device: L'intero ciclo ADMM interno viene eseguito sulla GPU, eliminando i colli di bottiglia nel trasferimento dati CPU-GPU.
• Tecniche Chiave:
  • Utilizzo di catene cuBLAS GEMM per gli aggiornamenti dei guadagni di feedback.
  • Proiezioni SOC parallele su tutti i vincoli tramite kernel CUDA.
  • Risoluzione di problemi QP convessi tramite PCG (Preconditioned Conjugate Gradient) con operatori matrice-free per evitare la formazione esplicita di matrici dense.

3. Contributi Chiave

1. Introduzione di NRTO-DR: Un metodo che utilizza lo splitting Douglas-Rachford per risolvere i sottoproblemi SOCP, migliorando le prestazioni rispetto ai metodi a punto interno grazie a proiezioni parallele e risoluzioni sparse.
2. Proposta di NRTO-FullADMM: Una nuova variante che riorganizza il ciclo ADMM per sfruttare al massimo la struttura del problema, eliminando la comunicazione CPU-GPU durante il ciclo interno e integrando le proiezioni SOC direttamente nel flusso di aggiornamento.
3. Implementazione GPU (cuNRTO): Sviluppo di kernel CUDA personalizzati per le proiezioni SOC e ottimizzazione delle catene di algebra lineare. Il framework è stato validato su tre piattaforme robotiche diverse.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su workstation con CPU Intel Xeon e GPU NVIDIA A100, confrontando cuNRTO (NRTO-DR e NRTO-FullADMM) con il baseline NRTO (risolto con MOSEK su CPU).

• Robot Unicycle e Quadricottero:

  • Sono stati testati sweep su orizzonte temporale ($T$), livello di incertezza ($\tau$) e numero di ostacoli.
  • Speedup: NRTO-FullADMM ha mostrato accelerazioni fino a 139.6× rispetto al baseline NRTO nel caso con 5 ostacoli per l'Unicycle (tempo di calcolo ridotto da ~30.000s a ~218s).
  • Per il quadricottero, lo speedup è stato di 66.89× nello stesso scenario.
  • Il tasso di soddisfazione dei vincoli è rimasto al 100% (o molto vicino, >90%) anche con l'aggiunta dell'errore di linearizzazione (NRTO-LE).

• Manipolatore Franka (7-DOF):

  • Sistema ad alta dimensionalità ($n_x=14$, $n_u=7$) con vincoli di collisione e limiti articolari.
  • NRTO-FullADMM ha raggiunto uno speedup di 25.9× (da ~3948s a ~152s) mantenendo la soddisfazione dei vincoli robusti.

• Robustezza: In tutti i casi, le traiettorie generate hanno soddisfatto i vincoli robusti per 2.000 realizzazioni di disturbi (inclusi casi limite e Monte Carlo), confermando l'efficacia della garanzia di sicurezza.

5. Significato e Impatto

Il lavoro di cuNRTO rappresenta un passo significativo verso l'implementazione in tempo reale di strategie di controllo robuste per sistemi robotici complessi e ad alta dimensionalità.

• Superamento dei limiti computazionali: Dimostra che l'accelerazione GPU può rendere fattibili problemi di ottimizzazione robusta che erano precedentemente troppo lenti per l'uso pratico.
• Scalabilità: L'architettura scala efficacemente all'aumentare del numero di vincoli (ostacoli) e della dimensionalità del sistema, sfruttando il parallelismo massivo.
• Sicurezza: Permette di garantire la sicurezza in scenari dinamici e incerti senza sacrificare le prestazioni computazionali, aprendo la strada a robot autonomi più sicuri in ambienti non strutturati.

In sintesi, cuNRTO trasforma un problema di ottimizzazione robusta intrattabile su CPU in un processo efficiente e scalabile su GPU, rendendo possibile il controllo robusto in tempo reale per robot avanzati.