RRT*

• También llamado: RRT star, RRT-star, optimal RRT
• Categoría: Planning & manipulation › Motion planning
• Etiquetas: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

Una versión asintóticamente óptima del planificador Rapidly-exploring Random Tree que recablea su árbol a medida que crece, de modo que el camino que devuelve sigue mejorando hacia el de menor coste.

Definición

RRT\ (se pronuncia «RRT star») es un algoritmo de planificación de movimiento basado en muestreo que encuentra caminos libres de colisiones y, con suficientes muestras, converge hacia uno óptimo. Lo presentaron Sertac Karaman y Emilio Frazzoli en 2011 como una extensión del algoritmo Rapidly-exploring Random Tree (RRT), propuesto por Steven LaValle en 1998.

El RRT original hace crecer un árbol desde la configuración de inicio muestreando repetidamente un punto aleatorio del espacio de configuraciones, buscando el nodo más cercano del árbol y extendiéndose un paso corto hacia la muestra si ese movimiento está libre de colisiones. RRT encuentra caminos factibles con rapidez, incluso en espacios de alta dimensión como el espacio articular de un brazo robótico, pero sus caminos suelen ser irregulares y estar lejos del más corto, y no mejoran al añadir más muestras.

RRT* cambia dos cosas. Cuando se añade un nuevo nodo, examina todos los nodos del árbol dentro de un radio de vecindad y se conecta al que da el menor coste desde el inicio, no simplemente al más cercano. Después recablea: para cada vecino, si pasar por el nuevo nodo da un camino más barato, se cambia el padre de ese vecino. Karaman y Frazzoli demostraron que, con un radio de vecindad que se reduce de forma adecuada a medida que crece el árbol, el coste de la solución converge al óptimo cuando el número de muestras tiende a infinito, una propiedad llamada optimalidad asintótica.

El precio es un cálculo adicional por muestra, por lo que RRT tarda más que RRT en encontrar una primera solución. Variantes como Informed RRT y BIT* concentran el muestreo para acelerar la convergencia.

Por qué importa

Muchos robots no necesitan un camino cualquiera, sino uno bueno: más corto, más suave o más barato en energía. RRT* ofrece a los planificadores basados en muestreo, que escalan a espacios de configuraciones de alta dimensión, una vía con fundamento hacia la calidad del camino, y es una referencia estándar en la investigación y el software de planificación de movimiento.

Aplicaciones clave

• Planificación de movimiento libre de colisiones para brazos robóticos en espacios de trabajo abarrotados
• Planificación global de caminos para robots móviles y drones
• Planificación en espacios de configuraciones de alta dimensión donde la búsqueda en cuadrícula no es práctica
• Generación de caminos de referencia para la optimización de trayectorias

En la práctica

Los equipos de robótica suelen llegar a RRT a través de una biblioteca de planificación en lugar de escribirlo ellos mismos. La Open Motion Planning Library (OMPL), que MoveIt usa para brazos robóticos, incluye RRT y varias de sus variantes junto a RRT, RRT-Connect y PRM. Un patrón habitual es ejecutar RRT con un presupuesto de tiempo fijo, tomar el mejor camino encontrado cuando se agota el tiempo y después acortarlo y suavizarlo antes de convertirlo en una trayectoria parametrizada en el tiempo. Para robots móviles y drones, los equipos también usan RRT sobre un mapa de ocupación 2D o 3D como planificador global, eligiendo el tiempo de planificación y el tamaño de paso para equilibrar la calidad del camino y el tiempo de respuesta.

Ideas erróneas comunes

• RRT* devuelve el camino óptimo — es asintóticamente óptimo, así que el coste del camino se acerca al óptimo solo a medida que el número de muestras crece sin límite
• Los caminos de RRT* son suaves — son lineales a trozos y normalmente necesitan atajos y suavizado antes de ejecutarse
• RRT* siempre es mejor que RRT — cuando solo se necesita rápidamente un camino factible, RRT simple o RRT-Connect suelen ser la mejor opción

Quién debería saberlo

• Ingenieros de planificación de movimiento
• Desarrolladores de software para brazos robóticos y manipulación
• Desarrolladores de drones autónomos y robots móviles
• Estudiantes de robótica que estudian algoritmos de planificación

Tecnologías relacionadas

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• Comprobación de colisiones (Collision Checking)

Términos relacionados

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

Proyectos relacionados

• 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

Vídeos

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