Learning When to Quit: Meta-Reasoning for Motion Planning

Autori: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

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

Apprende da esecuzioni passate del pianificatore quando fermare un pianificatore del movimento anytime (RRT, PRM, Lazy PRM*) in modo da massimizzare il compromesso tra qualità del percorso e tempo di pianificazione.

Perché è importante

Ogni robot che pianifica con RRT o PRM deve scegliere un budget di tempo di pianificazione, e un tempo fisso o una soglia di qualità fissa spreca tempo oppure qualità del percorso. Il metodo avvolge un pianificatore anytime non modificato, quindi può essere aggiunto sopra pianificatori esistenti in stile OMPL, purché siano disponibili problemi di addestramento della distribuzione di ambienti di destinazione.

Problema

I pianificatori del movimento anytime continuano ad accorciare un percorso quanto più a lungo vengono eseguiti, ma non esiste una relazione ben caratterizzata tra qualità della soluzione e tempo di calcolo, per cui non è chiaro quando smettere di pianificare e iniziare a muoversi. I loro profili di prestazione sono fortemente non lisci, perché percorsi più brevi compaiono a salti improvvisi quando il pianificatore trova una nuova classe di omotopia, il che esclude una semplice estrapolazione online della qualità futura.

Soluzione proposta

Gli autori apprendono una policy di arresto dai profili di prestazione di problemi di pianificazione passati estratti dalla stessa distribuzione, massimizzando un'utilità pesata dall'utente U(q, t) = wq − (1 − w)t. Una variante basata su modello apprende un processo decisionale di Markov su qualità e tempo discretizzati e lo risolve con l'iterazione dei valori; due varianti senza modello (un classificatore feed-forward su caratteristiche progettate a mano e un modello sequence-to-sequence RNN) imitano decisioni di arresto di un oracolo calcolate a posteriori. Una CNN predice la lunghezza del percorso ottimo da un'immagine 2D dell'area di lavoro, così che i profili di problemi di difficoltà diversa possano essere normalizzati e confrontati.

Idee chiave

• I tempi di arresto ottimi possono essere calcolati a posteriori per ogni esecuzione di addestramento, il che trasforma il problema di apprendimento della policy in apprendimento per imitazione supervisionato anziché in apprendimento per rinforzo.
• Normalizzare la qualità del percorso richiede la lunghezza del percorso ottimo, che non è nota; una CNN che la predice da un'immagine 2D dell'area di lavoro rende i profili confrontabili tra problemi, e un normalizzatore scadente (una linea retta dalla partenza all'obiettivo) riduce nettamente l'utilità.
• Caratteristiche di storico più ricche (pendenza, piattezza) rendono il modello di transizione basato su modello molto più accurato, ma il suo costo di stima cresce da secondi a più di un giorno, un caso diretto della maledizione della dimensionalità.
• La RNN apprende le proprie caratteristiche temporali dalla sequenza grezza di utilità e ha dato i risultati buoni più affidabili tra pianificatori e pesi di utilità.

Risultati principali

• Accuratezza del predittore CNN della lunghezza del percorso ottimo su 200 aree di lavoro tenute da parte: 88,21%, 96,23% e 94,25% in tre distribuzioni di ambienti.
• L'uso del normalizzatore CNN ha dato utilità di 0,58, 0,65 e 0,66 in quei tre ambienti, contro 0,63, 0,70 e 0,67 con le lunghezze ottime reali e 0,39, 0,40 e 0,60 con un normalizzatore a linea retta.
• La perdita sui dati tenuti da parte del modello di transizione è scesa da 1,84 (senza caratteristiche) a 0,22 con (t, q) e a 0,10 con (t, q, pendenza), mentre il tempo di stima è salito da 0,41 s a 10,64 s e 11.933,72 s.
• RRT* con w = 0,8: utilità dell'oracolo 0,677, RNN 0,670, basato su modello 0,663, classificatore 0,658, contro 0,634 per il riferimento a qualità fissa e 0,575 per quello a tempo fisso.
• PRM* con w = 0,8: oracolo 0,718, basato su modello 0,702, RNN 0,698, classificatore 0,697, qualità fissa 0,674, tempo fisso 0,662.
• Con w = 0,2 il riferimento a qualità fissa è diventato negativo (−0,283 per RRT, −0,344 per PRM, −0,367 per Lazy PRM*), mentre i metodi appresi sono rimasti positivi.

Limiti

• Il predittore CNN della soluzione ottima riceve un'immagine 2D dell'area di lavoro, il che limita i metodi a problemi con aree di lavoro piane; l'estensione al 3D tramite griglie di voxel o nuvole di punti è suggerita ma non realizzata.
• Si assume che un nuovo problema provenga dalla stessa distribuzione dei problemi di addestramento, e l'addestramento richiede molte esecuzioni lunghe del pianificatore su problemi rappresentativi.
• Aggiungere caratteristiche di storico al metodo basato su modello era computazionalmente impraticabile negli esperimenti più grandi, quindi è stato usato solo (q, q_prev, t).
• Tutta la valutazione è in simulazione con un robot rigido a tre gradi di libertà in aree di lavoro 2D; nessun robot fisico è stato testato.
• È stata studiata solo un'utilità lineare U(q, t) = wq − (1 − w)t.

Impatto sul settore

L'articolo è stato finalista dell'IROS 2021 Best Paper Award on Cognitive Robotics e ha 14 citazioni. Non indica un rilascio di codice o dati.

Abstract

I pianificatori del movimento anytime sono ampiamente usati in robotica. Tuttavia, la relazione tra la qualità della loro soluzione e il tempo di calcolo non è ben compresa e, di conseguenza, non è chiaro come stabilire quando interrompere la pianificazione e iniziare l'esecuzione. In questo articolo affrontiamo il problema di decidere quando fermare la deliberazione con una capacità di calcolo limitata, il cosiddetto meta-ragionamento, per la pianificazione del movimento anytime. Proponiamo metodi di apprendimento basati sui dati, meta-ragionamento basato su modello e senza modello, applicabili a diverse distribuzioni di ambienti e indipendenti dalla scelta del pianificatore del movimento anytime. Come parte del framework, progettiamo un predittore della soluzione ottima basato su una rete neurale convoluzionale che predice la lunghezza del percorso ottimo a partire da una data immagine 2D dell'area di lavoro. Valutiamo empiricamente le prestazioni dei metodi proposti in simulazione, a confronto con metodi di riferimento.

Link

• arXiv 2103.04374: https://arxiv.org/abs/2103.04374
• DOI 10.1109/IROS51168.2021.9636864: https://doi.org/10.1109/IROS51168.2021.9636864
• PDF: https://arxiv.org/pdf/2103.04374v1