BOW: Bayesian Optimization over Windows for Motion Planning in Complex Environments

1. Enunciato del Problema

La pianificazione del movimento per robot mobili in ambienti complessi, affollati e ad alta dimensionalità è un problema di ottimizzazione vincolata impegnativo. Le difficoltà principali includono:

• Vincoli Cinetodinamici: I robot devono rispettare i limiti fisici (velocità, accelerazione, velocità angolare di imbardata) evitando al contempo gli ostacoli.
• Costo Computazionale: La valutazione delle funzioni obiettivo (ad esempio, tempo, energia) e dei vincoli di sicurezza su orizzonti di pianificazione lunghi è computazionalmente costosa, specialmente per sistemi con dinamiche complesse.
• Compromessi: I metodi esistenti spesso faticano a bilanciare ottimalità, sicurezza ed efficienza computazionale. I metodi basati sul campionamento tradizionali (come RRT) possono essere lenti, mentre i metodi basati su griglia o euristici (come DWA) possono mancare di efficienza nel campionamento o rimanere intrappolati in minimi locali.
• Requisiti in Tempo Reale: La pianificazione online richiede di trovare input di controllo fattibili e quasi ottimali entro budget temporali rigorosi (millisecondi) ad ogni passo temporale.

2. Metodologia: Il Pianificatore BOW

Gli autori propongono BOW (Bayesian Optimization over Windows), un algoritmo di pianificazione del movimento scalabile che integra l'Approccio della Finestra Dinamica (DWA) con l'Ottimizzazione Bayesiana Vincolata (CBO).

Concetto Fondamentale

Invece di cercare l'intero spazio di controllo o utilizzare ricerche su griglia fisse, BOW restringe la ricerca a una finestra di pianificazione dinamica ($V_d$) definita dai limiti cinetodinamici attuali del robot (velocità e accelerazioni raggiungibili). All'interno di questa finestra, utilizza l'Ottimizzazione Bayesiana per campionare in modo efficiente gli input di controllo.

Componenti Tecnici Chiave

1. Controllo a Orizzonte Scorrevole (RHC):

   • Il pianificatore opera su un breve orizzonte di previsione ($\Delta$).
   • Assume che un input di controllo costante $u_t$ venga applicato sull'orizzonte per semplificare il calcolo del costo a venire.
   • L'obiettivo è minimizzare una funzione di costo $J$ (distanza dall'obiettivo) soggetta a vincoli di sicurezza $c_k$ (evitamento ostacoli).

2. Modelli Sostitutivi a Processo Gaussiano (GP):

   • Poiché la valutazione del vero costo e dei vincoli tramite simulazione è costosa, BOW modella la funzione obiettivo $J(u)$ e le funzioni di vincolo $c_k(u)$ come Processi Gaussiani.
   • I GP vengono addestrati su un piccolo insieme di campioni iniziali ($p$) all'interno della finestra dinamica.

3. Miglioramento Atteso Vincolato (CEI):

   • Per selezionare il successivo input di controllo, BOW utilizza una funzione di acquisizione modificata chiamata Miglioramento Atteso Vincolato (CEI).
   • Formula: $CEI(u) = EI(u) \times P(\text{fattibile} | u)$
   • $EI(u)$ bilancia esplorazione e sfruttamento per l'obiettivo.
   • $P(\text{fattibile} | u)$ è la probabilità che l'input di controllo soddisfi tutti i vincoli di sicurezza (derivata dal posterior del GP dei vincoli).
   • Ciò permette al pianificatore di ottimizzare simultaneamente le prestazioni e la sicurezza, trattando efficacemente i vincoli come vincoli probabilistici morbidi durante la ricerca.

4. Flusso dell'Algoritmo:

   • Campionare $p$ candidati di controllo dalla finestra dinamica.
   • Valutare costi e vincoli tramite simulazione.
   • Addestrare i GP sui dati.
   • Massimizzare il CEI per trovare il controllo ottimale $u^*_t$.
   • Generare una traiettoria utilizzando il modello di movimento (integrazione RK4) e convalidarla rispetto all'orizzonte completo.
   • Applicare il controllo per un passo $\ell$ (dove $\ell \le \Delta$) e ripetere.

3. Contributi Chiave

• Efficienza nel Campionamento Migliorata: BOW trova politiche di controllo ottimali con un numero significativamente inferiore di valutazioni (ad esempio, 5–15 campioni) rispetto alle ricerche su griglia o al campionamento casuale, riducendo drasticamente il tempo di calcolo.
• Ottimizzazione Integrata alla Sicurezza: A differenza di metodi che ottimizzano prima e verificano i vincoli successivamente, BOW incorpora i vincoli di sicurezza direttamente nella funzione di acquisizione, garantendo che i controlli selezionati siano probabilisticamente fattibili.
• Scalabilità: Il metodo scala efficacemente a problemi ad alta dimensionalità (testato su UAV a 6 gradi di libertà) e ambienti complessi senza un'esplosione lineare del tempo di calcolo.
• Garanzie Teoriche: Il paper fornisce una prova di convergenza asintotica, dimostrando che all'aumentare del numero di campioni, il controllo selezionato converge alla soluzione ottimale vera all'interno della regione fattibile.
• Open Source: Il pianificatore è rilasciato come pacchetto open source con video di esperimenti nel mondo reale e simulati.

4. Risultati Sperimentali

Il pianificatore BOW è stato valutato sia su Veicoli Terrestri Non Equipaggiati (UGV) che su Veicoli Aerei Non Equipaggiati (UAV) in ambienti simulati e reali.

• Benchmark: Confrontato contro RRT, DWA, MPPI, HRVO e CBF su sei ambienti 2D distinti (inclusi "Bugtrap" e foreste di Poisson) e cinque scenari UAV 3D.
• Metriche di Prestazione:
  • Tempo di Calcolo: BOW ha raggiunto i tempi di pianificazione più rapidi, variando da 10ms a 30ms per orizzonte, con tempi di esecuzione per passo bassi quanto 0,10–0,15 ms. Al contrario, competitor come CBF e MPPI richiedevano da centinaia a migliaia di millisecondi.
  • Completezza: BOW ha mantenuto un tasso di successo del 100% (completezza perfetta) in tutti gli ambienti, mentre competitor come DWA, HRVO e CBF non sono riusciti a trovare soluzioni in scenari complessi specifici (ad esempio, passaggi stretti o ostacoli ad alta densità).
  • Qualità della Traiettoria: BOW ha prodotto lunghezze di traiettoria competitive e fluidità (jerk moderato), superando RRT nella fluidità e MPPI nella coerenza.
  • Efficienza nel Campionamento: Nei confronti visivi, BOW ha identificato controlli ottimali con soli ~15 campioni, mentre DWA richiedeva una ricerca completa su griglia e MPPI richiedeva un campionamento uniforme sia degli spazi fattibili che non fattibili.
• Implementazione nel Mondo Reale: Implementato con successo su un UGV a trazione differenziale e su un UAV quadrotore, dimostrando un robusto evitamento degli ostacoli utilizzando LiDAR a bordo e navigazione in tempo reale in spazi 3D affollati.

5. Significato e Impatto

• Applicabilità Pratica: BOW colma il divario tra ottimalità teorica e fattibilità in tempo reale, rendendolo adatto a dispositivi edge con risorse limitate (ad esempio, Raspberry Pi, Jetson Nano) e ad applicazioni robotiche ad alta velocità.
• Robustezza nell'Incertezza: Utilizzando modelli probabilistici (GP), il pianificatore gestisce l'incertezza nelle dinamiche e nella percezione dell'ambiente meglio delle euristiche deterministiche.
• Direzioni Future: Sebbene BOW eccella come pianificatore locale, gli autori riconoscono limitazioni nella pianificazione globale (ad esempio, rimanere intrappolati in minimi locali in passaggi stretti). Il lavoro futuro mira a integrare BOW con algoritmi di ricerca basati su alberi per risolvere problemi di pianificazione del movimento globale.

In sintesi, il Pianificatore BOW rappresenta un avanzamento significativo nella pianificazione del movimento locale sfruttando l'ottimizzazione bayesiana vincolata per raggiungere una navigazione rapida, sicura ed efficiente nel campionamento in ambienti complessi e dinamici.