Rapidly-exploring random tree

• Detto anche: RRT
• Categoria: Planning & manipulation › Motion planning
• Tag: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

Un pianificatore del movimento basato sul campionamento che fa crescere un albero dallo stato di partenza campionando ripetutamente uno stato casuale ed estendendo verso di esso il nodo più vicino dell'albero, esplorando rapidamente spazi ampi.

Definizione

Il Rapidly-exploring random tree (RRT) è un algoritmo basato sul campionamento per trovare un percorso ammissibile da uno stato di partenza a una regione obiettivo. È stato introdotto da Steven LaValle nel 1998. L'algoritmo fa crescere un albero con radice nella partenza: a ogni iterazione campiona uno stato casuale nello spazio delle configurazioni o degli stati, trova il nodo più vicino dell'albero ed estende da quel nodo un breve tratto verso il campione. Se l'estensione è priva di collisioni, il nuovo stato viene aggiunto all'albero. La ricerca termina quando l'albero raggiunge la regione obiettivo, e il percorso si ricostruisce risalendo attraverso il genitore di ciascun nodo.

La proprietà chiave è il bias di Voronoi. I nodi sulla frontiera dell'albero hanno le regioni di Voronoi più grandi, quindi sono quelli con la maggiore probabilità di essere i più vicini a un campione casuale, e l'albero viene attratto verso lo spazio inesplorato invece di riempire regioni che ha già coperto. Questo rende RRT efficace in spazi ad alta dimensione come lo spazio dei giunti di un braccio robotico. RRT è probabilisticamente completo: se una soluzione esiste, la probabilità di trovarla tende a uno al crescere del numero di campioni. I miglioramenti comuni comprendono il goal biasing, in cui una frazione dei campioni viene presa sull'obiettivo, e RRT-Connect, che fa crescere alberi sia dalla partenza sia dall'obiettivo e cerca di unirli in modo greedy.

Poiché il passo di estensione richiede solo un modo per muoversi da uno stato verso un altro, RRT gestisce anche la pianificazione cinodinamica, in cui il robot non può muoversi in linea retta nel suo spazio degli stati. Il passo di estensione applica allora controlli campionati o ottimizzati e simula la dinamica in avanti, come nell'RRT cinodinamico di LaValle e Kuffner, oppure concatena primitive di movimento precalcolate. Ciò lo rende utile per veicoli, robot con gambe e manipolazione ricca di contatti, dove la metrica di distanza e il passo di estensione devono essere progettati attorno alla dinamica. I percorsi di RRT sono di solito frastagliati e non ottimi, e aggiungere altri campioni non migliora un percorso una volta trovato. RRT\ aggiunge un passo di scelta del genitore e un passo di ricollegamento (rewiring) che riconnette i nodi vicini ogni volta che esiste un percorso meno costoso, il che lo rende asintoticamente ottimo al prezzo di più calcolo per campione. Quando serve rapidamente un percorso ammissibile, RRT semplice o RRT-Connect seguito da shortcutting e smoothing resta una scelta comune.

Perché è importante

RRT ha reso pratica la pianificazione del movimento per robot con molti gradi di libertà e per sistemi con dinamica, e resta un pianificatore predefinito in librerie come OMPL e MoveIt. Molti pianificatori successivi, compreso RRT*, sono costruiti sulla sua struttura.

Applicazioni principali

• Pianificazione del movimento di manipolatori in spazi di lavoro ingombri
• Pianificazione cinodinamica per auto, droni e robot con gambe
• Pianificazione della manipolazione ricca di contatti con metriche di distanza personalizzate
• Pianificazione su grafi di primitive di movimento per la locomozione
• Esplorazione di ambienti sconosciuti

In pratica

Un team che configura MoveIt per un braccio a sette assi che preleva articoli dagli scaffali usa RRT-Connect di OMPL come pianificatore predefinito. Il controllo delle collisioni usa il modello del robot e un octree costruito da una telecamera di profondità. Il team imposta il limite di tempo di pianificazione e la dimensione del passo di estensione in rapporto allo spazio libero delle aperture degli scaffali, poi post-elabora ogni percorso con shortcutting e parametrizzazione temporale perché il braccio si muova in modo fluido. Quando la pianificazione fatica a raggiungere il fondo di vani stretti, aumenta il goal biasing o prova un pianificatore che si comporta meglio nei passaggi stretti, e per interrogazioni ripetute in una cella statica valuta invece una roadmap probabilistica.

Idee sbagliate comuni

• RRT trova il percorso più breve — trova un percorso ammissibile; per una buona qualità del percorso servono RRT* o una post-elaborazione
• RRT garantisce di trovare un percorso entro un tempo stabilito — è probabilisticamente completo, quindi trova un percorso con probabilità che tende a uno man mano che il campionamento prosegue, e i passaggi stretti possono richiedere molto tempo
• RRT* è sempre la scelta migliore — migliora i percorsi nel tempo ma è più lento ad arrivare a una prima soluzione; RRT-Connect con smoothing è spesso preferito quando conta la velocità

Chi dovrebbe saperlo

• Ingegneri di pianificazione del movimento
• Sviluppatori di manipolazione e di robot mobili che usano MoveIt od OMPL
• Ingegneri di pianificazione per veicoli autonomi e droni
• Studenti di robotica

Tecnologie correlate

• OMPL
• MoveIt
• RRT-Connect
• RRT cinodinamico (Kinodynamic RRT)
• Informed RRT*
• Accorciamento del percorso (Path Shortcutting)

Termini correlati

• Configuration Space
• Motion Planning
• Obstacle Avoidance
• RRT*
• Probabilistic Roadmap
• Motion Primitive

Progetti correlati

• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
• OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
• MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
• PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
• mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms

Video

• Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering