Anytime Motion Planning

Detto anche: anytime planning, anytime planner
Categoria: Planning & manipulation › Motion planning
Tag: motion-planning, sampling-based-planning, optimal-planning, real-time, bounded-computation

Pianificazione del movimento che restituisce rapidamente un percorso valido e poi continua a migliorarlo finché il tempo lo consente, così che una risposta utilizzabile è disponibile ogni volta che il pianificatore viene fermato.

Definizione

Un pianificatore del movimento anytime (anytime motion planner) produce una prima soluzione ammissibile e priva di collisioni il prima possibile e poi impiega il tempo rimanente per migliorarla, di solito riducendo la lunghezza del percorso, il tempo di esecuzione o un altro costo. In ogni momento successivo alla prima soluzione dispone della migliore risposta trovata fino a quel punto, che può essere restituita se viene interrotto. L'idea deriva dalla nozione più ampia di algoritmi anytime nell'intelligenza artificiale, introdotta da Dean e Boddy alla fine degli anni 1980, in cui la qualità della soluzione viene scambiata con il tempo di calcolo e il rapporto tra le due è descritto da un profilo di prestazione.

Nella ricerca su grafi, il comportamento anytime si ottiene di solito eseguendo prima un'euristica pesata e gonfiata e poi stringendo il peso riutilizzando lo sforzo di ricerca precedente, come in Anytime Repairing A (ARA). Nella pianificazione basata sul campionamento, i pianificatori asintoticamente ottimi come RRT e la variante PRM delle roadmap probabilistiche sono anytime per natura: continuano a campionare e a ricollegare dopo la prima soluzione, e il costo del percorso migliore tende all'ottimo man mano che cresce il numero di campioni. Informed RRT e Batch Informed Trees (BIT) accelerano la fase di miglioramento limitando i campioni alla regione che potrebbe ancora contenere un percorso migliore. Un semplice rapidly-exploring random tree** non è anytime in questo senso, perché si ferma appena l'obiettivo è collegato, anche se si possono aggiungere riavvii o post-elaborazione.

Il miglioramento nel tempo è raramente regolare. Il costo scende spesso a gradini, soprattutto quando il pianificatore trova una via attraverso un varco diverso tra gli ostacoli, cioè un percorso in una nuova classe di omotopia, e lunghi tratti possono portare un guadagno quasi nullo. Questo rende la decisione di fermarsi un problema a sé: fermarsi troppo presto spreca qualità, fermarsi troppo tardi spreca tempo che il robot potrebbe passare a muoversi. I budget di tempo fissi sono la prassi comune, mentre i metodi di meta-ragionamento apprendono o stimano quando ulteriore calcolo non vale più la pena.

Perché è importante

I robot hanno raramente una quantità di tempo fissa e nota per pianificare. Un pianificatore anytime fornisce quasi subito una soluzione di ripiego sicura e trasforma ogni tempo avanzato in un movimento migliore, il che si adatta a sistemi che devono agire entro una scadenza ma tengono comunque alla qualità del percorso, all'energia o al tempo ciclo.

Applicazioni principali

Pianificazione del movimento del braccio con budget di tempo per query nelle pipeline di manipolazione
Ripianificazione per robot mobili e veicoli che devono agire su un ciclo di controllo fisso
Pianificazione del percorso per robot aerei, dove percorsi più brevi fanno risparmiare batteria
Ricerca euristica su grafi su griglie e reticoli con riduzione del peso alla maniera di ARA*
Ricerca sul meta-ragionamento per decidere quando smettere di pianificare e iniziare ad agire

In pratica

Un manipolatore mobile pianifica i movimenti del braccio con un pianificatore basato sul campionamento asintoticamente ottimo preso da una libreria come OMPL. Ogni query riceve un budget di tempo: il pianificatore di solito trova un primo percorso all'inizio di quel budget e poi continua ad accorciarlo. Il team registra il costo migliore in funzione del tempo trascorso su molte query registrate e vede che la maggior parte del guadagno arriva presto, con occasionali grandi cali quando un percorso più breve attorno a un ostacolo viene trovato tardi. Invece di spendere sempre l'intero budget, si fermano quando il costo non è migliorato per un intervallo stabilito, oppure usano una regola di arresto appresa, e poi applicano scorciatoie e parametrizzazione temporale al risultato prima di inviarlo al controllore.

Idee sbagliate comuni

Anytime significa che la prima soluzione è quasi ottima — la prima soluzione è spesso lontana dall'ottimo, e la qualità dipende da quanto a lungo gira il pianificatore
Il costo migliora in modo costante nel tempo — di solito scende a gradini irregolari, con lunghi plateau tra l'uno e l'altro
L'ottimalità asintotica garantisce un buon percorso entro il budget di tempo — descrive solo il limite quando il calcolo cresce senza limiti e non dice nulla su una scadenza finita
Usare tutto il budget di tempo è sempre la scelta migliore — il tempo passato a pianificare è tempo non passato a muoversi, quindi fermarsi prima è spesso il compromesso migliore

Chi dovrebbe saperlo

Ingegneri di pianificazione del movimento che configurano pianificatori basati sul campionamento o sulla ricerca
Sviluppatori di manipolazione mobile e navigazione che lavorano con vincoli di tempo reale
Ricercatori di robotica che studiano la pianificazione con calcolo limitato
Studenti che imparano la pianificazione ottima del movimento

Tecnologie correlate

ARA (Anytime Repairing A)
RRT*
Informed RRT*
BIT* (Batch Informed Trees)
OMPL

Termini correlati

Progetti correlati

GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
Dora AI: Dataflow middleware for AI robotics applications, built in Rust
OpenMind OM1: AI-native operating system for robots with modular perception, cognition, and action
Fast DDS: eProsima's high-performance DDS middleware — the default transport under ROS 2