Provably Safe Motion Planning Under Unknown Disturbances

Enunciato del Problema
Questo articolo affronta la sfida della pianificazione del movimento per sistemi robotici soggetti a disturbi casuali con distribuzioni sconosciute. I pianificatori basati sul campionamento tradizionali spesso assumono modelli deterministici o si affidano a forti ipotesi distribuzionali (ad esempio, rumore gaussiano) e a modelli di disturbi limitati. Questi approcci risultano frequentemente in piani eccessivamente conservativi che falliscono in ambienti affollati o richiedono una conoscenza irrealistica della distribuzione del disturbo. Gli autori formulano il problema come la generazione di un piano di movimento per sistemi lineari (o linearizzabili tramite feedback) che soddisfi vincoli probabilistici per l'evitamento delle collisioni e la raggiungibilità dell'obiettivo con alta confidenza, nonostante le distribuzioni dello stato iniziale e del rumore di processo siano sconosciute. Il sistema deve operare entro vincoli di stato e di controllo in spazi di lavoro contenenti ostacoli di forma arbitraria.

Metodologia
L'approccio proposto, denominato WDR-X (Wasserstein Distributionally Robust-X), è un framework di pianificazione del movimento basato sul campionamento che integra la quantificazione dell'incertezza guidata dai dati con una ricerca ad albero. La metodologia procede in due fasi principali:

1. Costruzione del Tubo di Ambiguità (Offline):
   Invece di assumere una specifica distribuzione del rumore, l'algoritmo apprende un tubo di ambiguità di Wasserstein da un insieme di $N$ campioni di traiettoria i.i.d. Questo tubo è una sequenza di insiemi di ambiguità (sfere di Wasserstein) che, con un livello di confidenza definito dall'utente, contiene la vera distribuzione dello stato ad ogni istante temporale.

   • Dinamiche dell'Errore: Gli autori disaccoppiano il problema di pianificazione dalla propagazione dell'incertezza analizzando le dinamiche dell'errore rispetto a una traiettoria di riferimento. Dimostrano che l'insieme di ambiguità per lo stato può essere derivato dall'insieme di ambiguità dell'errore e dallo stato di riferimento.
   • Orizzonte Infinito: A differenza dei metodi precedenti in cui i limiti di ambiguità crescono indefinitamente nel tempo, questo approccio costruisce un tubo di lunghezza temporale infinita con confidenza finita. Ciò viene ottenuto apprendendo insiemi di ambiguità guidati dai dati in istanti temporali specifici e derivando gli insiemi per gli istanti intermedi utilizzando le dinamiche del sistema, risultando in un profilo di raggio "a dente di sega" che rimane limitato.
   • Decomposizione in Dimensionalità Inferiore: Per affrontare la maledizione della dimensionalità, il framework sfrutta tubi di ambiguità a dimensionalità inferiore. Proiettando la distribuzione dello stato su sottospazi rilevanti per vincoli specifici (ad esempio, posizione nello spazio di lavoro per gli ostacoli, sforzo di controllo per i limiti), il metodo riduce significativamente la complessità del campione e il costo computazionale mantenendo le garanzie di sicurezza.

2. Pianificazione Probabilisticamente Completa (Online):
   Il pianificatore fa crescere un albero basato sul campionamento (ad esempio, RRT) sulle traiettorie di riferimento nominali (deterministiche).

   • Verifica di Validità: Ad ogni nodo, l'algoritmo verifica se lo stato soddisfa i vincoli probabilistici. Ciò viene fatto valutando la probabilità di collisione nel caso peggiore sull'insieme di ambiguità appreso.
   • Verificatori Efficienti: L'articolo introduce tre strategie di verifica di validità:
     • Verificatore Esatto: Un algoritmo senza ottimizzazione basato sul trasporto di massa probabilistica che calcola la probabilità esatta di collisione nel caso peggiore per distribuzioni discrete.
     • Verificatore Pigro (Lazy): Un metodo più veloce e più conservativo che utilizza tubi di confidenza (sfere) pre-calcolati, evitando calcoli dettagliati di trasporto di massa.
     • Verificatore basato su Bandit: Un approccio ibrido che seleziona adattivamente tra il verificatore esatto e quello pigro utilizzando un framework a bandit multi-braccio. Questo bilancia efficienza e conservatorismo, specialmente in ambienti complessi come passaggi stretti.

Contributi Chiave
L'articolo apporta i seguenti contributi specifici:

• Algoritmo: Un algoritmo di pianificazione del movimento basato sul campionamento per sistemi lineari con disturbi additivi sconosciuti che utilizza dati di osservazione delle traiettorie.
• Garanzie Teoriche: Dimostrazioni di correttezza e completezza probabilistica per il pianificatore sotto ipotesi rilassate riguardanti le distribuzioni dei disturbi.
• Propagazione dell'Ambiguità: Nuovi risultati teorici sulla propagazione dell'ambiguità distribuzionale, che mostrano specificamente che la propagazione dell'ambiguità si disaccoppia dalla pianificazione per sistemi lineari, consentendo un singolo tubo appreso offline.
• Limiti più Stringenti: Una caratterizzazione più stringente della dimensione degli insiemi di ambiguità guidati dai dati definiti dalla distanza di Wasserstein 1 rispetto alla letteratura esistente, utilizzando disuguaglianze di McDiarmid unilaterali e informazioni sui momenti.
• Verifica di Validità: Tre metodi di verifica di validità che bilanciano efficienza e conservatorismo, tutti meno conservativi del lavoro esistente, unificati da uno schema a bandit multi-braccio che seleziona adattivamente il verificatore appropriato.
• Riduzione della Dimensionalità: Una formalizzazione dell'uso di molteplici tubi di ambiguità a dimensionalità inferiore per ridurre i requisiti di dati e computazionali senza sacrificare la sicurezza.

Risultati Sperimentali
Gli autori hanno valutato l'approccio su due sistemi: un sistema lineare a 4 dimensioni e un sistema drone a 8 dimensioni che naviga in spazi di lavoro 2D.

• Linee di Base: Il metodo è stato confrontato con approcci distribuzionalmente robusti basati sui momenti (TS e Risk-Assigned) e con altre varianti basate su Wasserstein (Particle, Confidence, Hybrid).
• Prestazioni:
  • In ambienti affollati e con passaggi stretti, il proposto Bandit-WDR-RRT ha superato significativamente le linee di base basate sui momenti, che non sono riuscite a trovare percorsi a causa di un eccessivo conservatorismo. Ad esempio, in un passaggio stretto con rumore non gaussiano, le linee di base hanno raggiunto tassi di successo dello 0–9%, mentre Bandit-WDR-RRT ha raggiunto fino al 100%.
  • Il verificatore basato su bandit ha dimostrato il miglior equilibrio, eguagliando o superando i tassi di successo di altre varianti mentre era 1,5–3 volte più veloce dell'approccio ibrido.
  • L'approccio a dimensionalità inferiore ha consentito con successo la pianificazione per il sistema drone a 8 dimensioni apprendendo tubi separati per i vincoli di posizione e di controllo, dimostrando la scalabilità.
• Sicurezza: Le simulazioni Monte Carlo hanno confermato che i piani generati hanno raggiunto tassi di successo del 99–100% nell'evitare collisioni, validando la correttezza dei vincoli del tubo di ambiguità.

Significato
L'articolo afferma che il suo significato principale risiede nel fornire un framework di pianificazione del movimento provabilmente sicuro e scalabile per sistemi con distribuzioni di disturbo sconosciute. Sfruttando gli insiemi di ambiguità di Wasserstein e l'apprendimento guidato dai dati, l'approccio evita le sovrapprossimazioni geometriche intrinseche nei metodi basati sui momenti e le ipotesi distribuzionali dei metodi basati sulla gaussiana. La capacità di gestire ostacoli di forma arbitraria e vincoli non convessi senza sacrificare la completezza probabilistica rende il metodo adatto per complesse applicazioni robotiche reali in cui la sicurezza è critica e i modelli di disturbo sono incerti. L'introduzione del verificatore di validità basato su bandit migliora ulteriormente l'utilità pratica gestendo dinamicamente il compromesso tra velocità computazionale e conservatorismo della soluzione.