Time Optimal Ergodic Search

Autori: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023

Licenze

• Open access
• Articolo: CC BY 4.0

Tutto ciò che segue si basa sull'articolo completo secondo la sua licenza CC BY 4.0; la figura è riportata citando gli autori.

In breve

Minimizza il tempo di ricerca soggetto a un limite superiore γ sulla metrica ergodica: un solo parametro stabilisce quanto deve essere completa la copertura, e l'ottimizzatore sceglie la durata della traiettoria.

Perché è importante

Nei voli di ricerca e soccorso o di rilievo, l'operatore può specificare quanto deve essere accurata una perlustrazione e ottenere la traiettoria più veloce che la soddisfi, invece di indovinare una durata. Vincoli come i limiti di velocità e le barriere contro gli ostacoli rientrano nella stessa ottimizzazione, e i tempi pianificati si sono confermati su un quadricottero reale entro 1,5 s.

Problema

La ricerca ergodica pianifica traiettorie continue che trascorrono in ogni regione un tempo proporzionale alla sua informazione, ma i metodi esistenti fissano in anticipo l'orizzonte di pianificazione, quindi l'utente non può bilanciare la completezza della ricerca e il tempo. Minimizzare il tempo e insieme minimizzare la metrica ergodica è un problema mal posto, perché una traiettoria diventa completamente ergodica solo quando il tempo tende all'infinito.

Soluzione proposta

La metrica ergodica diventa un vincolo di disuguaglianza E ≤ γ all'interno di un problema di tempo minimo, così γ stabilisce quanto grossolana o fine deve essere la copertura e il tempo finale tf è una variabile decisionale. Gli autori dimostrano condizioni di ottimalità locale con il principio del massimo di Pontryagin usando uno 'stato ergodico esteso', e in pratica risolvono il problema per trascrizione diretta su N punti nodali (Δt = tf/N) con un solver personalizzato a Lagrangiana aumentata. Gli ostacoli sono gestiti con vincoli di funzioni barriera di controllo discrete.

Idee chiave

• Trattare l'ergodicità come un limite anziché come un obiettivo rende ben posto il problema di ricerca a tempo minimo; per γ → 0 il tempo ottimo cresce senza limite, in accordo con la teoria ergodica
• Ridurre γ di due ordini di grandezza (da 0,1 a 0,001) su una mappa di informazione a quattro picchi ha circa raddoppiato il tempo ottimo (da 9,86 s a 19,59 s), mentre anche il piano grossolano ha comunque visitato ogni picco
• Lo sforzo di controllo normalizzato sul tempo è più alto nella parte centrale dell'intervallo di γ, dove la traiettoria deve bilanciare copertura e tempo, che a entrambi gli estremi
• Stime iniziali regolari (interpolazione lineare) danno soluzioni coerenti; traiettorie iniziali rumorose o casuali cadono in minimi locali ugualmente ergodici con tempi più lunghi

Risultati principali

• Copertura uniforme con una massa puntiforme 2D: variando γ si ottengono traiettorie di 5-10 s con copertura equivalente a una traiettoria ergodica a orizzonte fisso di 10 s (E = 0,007)
• Mappa di informazione non uniforme: tempi ottimi di 9,86 s con γ = 0,1 e di 19,59 s con γ = 0,001
• Sensibilità con γ = 0,05: variando il tf iniziale da 4 a 8 s si ottiene un tempo ottimo di 4,97 ± 0,23 s; variando il numero di punti nodali N da 50 a 600 si ottiene 5,45 ± 0,39 s
• Ambiente 2D ingombro con funzioni barriera di controllo: tempi ottimi da 7,79 s con γ = 0,2 a 11,85 s con γ = 0,002, con i vincoli di barriera che tengono le traiettorie lontane da ogni ostacolo
• Esperimenti con drone con γ = 0,1, 0,05 e 0,01: i tempi di volo eseguiti sono rimasti entro 1,5 s dai tempi ottimizzati; la traiettoria della Fig. 1 copre l'area ingombra in 13,5 s
• Il solver ha prodotto traiettorie di copertura uniforme anche per un modello non lineare di velivolo 3D tra ostacoli ellissoidali casuali

Limiti

• Gli autori affermano che le soluzioni sono solo localmente ottime, perché la metrica ergodica è fortemente non lineare e non convessa
• Gli autori hanno riscontrato che le condizioni di ottimalità di Pontryagin sono numericamente instabili per orizzonti lunghi, per cui il solver pratico è un metodo a trascrizione diretta
• La pianificazione è offline con ostacoli noti; gli autori indicano come lavoro futuro la pianificazione in tempo reale con ostacoli sconosciuti e incertezza ambientale
• I risultati dipendono dalla traiettoria iniziale e da N; il solver smette di restituire soluzioni per γ molto piccoli, dove il tempo richiesto diventa molto grande
• Gli autori osservano che il costo computazionale cresce con la dimensione dello spazio di esplorazione

Impatto sul settore

Vincitore del RSS 2023 Best Paper Award. Gli autori rilasciano il codice su github.com/ialab-yale/time_optimal_ergodic_search e una pagina di dimostrazione multimediale.

Abstract

I robot in grado di bilanciare il tempo e la completezza della ricerca possono fornire assistenza in situazioni in cui il tempo è critico, come la ricerca e soccorso. I recenti progressi nei metodi di ricerca basati sulla copertura ergodica hanno permesso ai robot di esplorare e perlustrare completamente un'area in un tempo fissato. Tuttavia, l'ottimizzazione del tempo rispetto alla qualità della ricerca ergodica autonoma non è stata ancora dimostrata. In questo articolo studiamo soluzioni al problema della ricerca ergodica a tempo ottimo per una ricerca ed esplorazione robotica rapida e adattiva. Formuliamo il problema come un problema di tempo minimo con un vincolo di disuguaglianza ergodica il cui limite superiore regola e bilancia la granularità della ricerca rispetto al tempo. Le soluzioni del problema sono presentate analiticamente tramite le condizioni di ottimalità di Pontryagin e dimostrate numericamente tramite un approccio di ottimizzazione a trascrizione diretta. Mostriamo l'efficacia dell'approccio nel generare traiettorie di ricerca ergodica a tempo ottimo in simulazione e con esperimenti con droni in un ambiente ingombro. Si mostra che l'evitamento degli ostacoli si integra facilmente nella nostra formulazione, e svolgiamo studi di ablazione che indagano la dipendenza dei parametri dal tempo ottimizzato e la sensibilità della traiettoria per la ricerca.

Link

• arXiv 2305.11643: https://arxiv.org/abs/2305.11643
• PDF: https://arxiv.org/pdf/2305.11643v1
• Codice: https://github.com/ialab-yale/time_optimal_ergodic_search
• Pagina del progetto: https://sites.google.com/view/time-optimal-ergodic-search