RRT*

• Detto anche: RRT star, RRT-star, optimal RRT
• Categoria: Planning & manipulation › Motion planning
• Tag: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

Una versione asintoticamente ottima del pianificatore Rapidly-exploring Random Tree che ricollega il proprio albero mentre cresce, così che il percorso restituito continui a migliorare verso quello di costo minimo.

Definizione

RRT\ (si pronuncia «RRT star») è un algoritmo di pianificazione del movimento basato sul campionamento che trova percorsi privi di collisioni e, con un numero sufficiente di campioni, converge verso uno ottimo. È stato introdotto da Sertac Karaman ed Emilio Frazzoli nel 2011 come estensione dell'algoritmo Rapidly-exploring Random Tree (RRT) proposto da Steven LaValle nel 1998.

L'RRT originale fa crescere un albero a partire dalla configurazione di partenza campionando ripetutamente un punto casuale nello spazio delle configurazioni, trovando il nodo più vicino dell'albero ed estendendosi di un breve passo verso il campione se quel movimento è privo di collisioni. RRT trova percorsi ammissibili rapidamente, anche in spazi ad alta dimensione come lo spazio dei giunti di un braccio robotico, ma i suoi percorsi sono di solito frastagliati e lontani dal più breve, e non migliorano con l'aggiunta di altri campioni.

RRT* cambia due cose. Quando si aggiunge un nuovo nodo, esamina tutti i nodi dell'albero entro un raggio di vicinato e si collega a quello che dà il costo minore dalla partenza, non semplicemente a quello più vicino. Poi esegue il rewiring: per ogni vicino, se passare per il nuovo nodo dà un percorso più economico, il genitore di quel vicino viene cambiato. Karaman e Frazzoli hanno dimostrato che, con un raggio di vicinato che si riduce in modo appropriato man mano che l'albero cresce, il costo della soluzione converge all'ottimo quando il numero di campioni tende all'infinito, una proprietà chiamata ottimalità asintotica.

Il prezzo è un calcolo aggiuntivo per campione, quindi RRT è più lento di RRT a trovare una prima soluzione. Varianti come Informed RRT e BIT* concentrano il campionamento per accelerare la convergenza.

Perché è importante

Molti robot non hanno bisogno di un percorso qualsiasi ma di uno buono: più breve, più regolare o più economico in termini di energia. RRT* offre ai pianificatori basati sul campionamento, che scalano a spazi delle configurazioni ad alta dimensione, una via fondata verso la qualità del percorso, ed è una baseline standard nella ricerca e nel software di pianificazione del movimento.

Applicazioni principali

• Pianificazione del movimento priva di collisioni per bracci robotici in spazi di lavoro ingombri
• Pianificazione globale del percorso per robot mobili e droni
• Pianificazione in spazi delle configurazioni ad alta dimensione dove la ricerca su griglia non è praticabile
• Generazione di percorsi di riferimento per l'ottimizzazione della traiettoria

In pratica

I team di robotica di solito arrivano a RRT tramite una libreria di pianificazione invece di scriverlo da sé. La Open Motion Planning Library (OMPL), che MoveIt usa per i bracci robotici, include RRT e diverse sue varianti accanto a RRT, RRT-Connect e PRM. Uno schema comune è eseguire RRT con un budget di tempo fisso, prendere il percorso migliore trovato allo scadere del tempo e poi accorciarlo e renderlo regolare prima di convertirlo in una traiettoria parametrizzata nel tempo. Per robot mobili e droni, i team usano RRT anche su una mappa di occupazione 2D o 3D come pianificatore globale, scegliendo il tempo di pianificazione e la dimensione del passo per bilanciare la qualità del percorso e il tempo di risposta.

Idee sbagliate comuni

• RRT* restituisce il percorso ottimo — è asintoticamente ottimo, quindi il costo del percorso si avvicina all'ottimo solo man mano che il numero di campioni cresce senza limite
• I percorsi di RRT* sono regolari — sono lineari a tratti e di solito richiedono scorciatoie e smoothing prima dell'esecuzione
• RRT* è sempre migliore di RRT — quando serve solo un percorso ammissibile in fretta, RRT semplice o RRT-Connect sono spesso la scelta migliore

Chi dovrebbe saperlo

• Ingegneri di pianificazione del movimento
• Sviluppatori di software per bracci robotici e manipolazione
• Sviluppatori di droni autonomi e robot mobili
• Studenti di robotica che studiano gli algoritmi di pianificazione

Tecnologie correlate

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• Verifica delle collisioni (Collision Checking)

Termini correlati

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

Progetti correlati

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

Video

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB