Rapidly-exploring random tree

• También llamado: RRT
• Categoría: Planning & manipulation › Motion planning
• Etiquetas: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance

Un planificador de movimiento basado en muestreo que hace crecer un árbol desde el estado de inicio muestreando repetidamente un estado aleatorio y extendiendo hacia él el nodo más cercano del árbol, con lo que explora rápidamente espacios grandes.

Definición

El árbol aleatorio de exploración rápida (RRT) (rapidly-exploring random tree) es un algoritmo basado en muestreo para encontrar un camino factible desde un estado de inicio hasta una región objetivo. Lo introdujo Steven LaValle en 1998. El algoritmo hace crecer un árbol con raíz en el inicio: en cada iteración muestrea un estado aleatorio en el espacio de configuraciones o de estados, encuentra el nodo más cercano del árbol y extiende desde ese nodo una distancia corta hacia la muestra. Si la extensión está libre de colisiones, el nuevo estado se añade al árbol. La búsqueda termina cuando el árbol alcanza la región objetivo, y el camino se reconstruye hacia atrás a través del padre de cada nodo.

La propiedad clave es el sesgo de Voronoi. Los nodos de la frontera del árbol tienen las regiones de Voronoi más grandes, así que son los que tienen más probabilidad de ser los más cercanos a una muestra aleatoria, y el árbol es atraído hacia el espacio inexplorado en lugar de llenar regiones que ya ha cubierto. Esto hace que RRT sea eficaz en espacios de alta dimensión como el espacio articular de un brazo robótico. RRT es probabilísticamente completo: si existe una solución, la probabilidad de encontrarla tiende a uno a medida que crece el número de muestras. Las mejoras habituales incluyen el sesgo hacia el objetivo (goal biasing), en el que una fracción de las muestras se toma en el objetivo, y RRT-Connect, que hace crecer árboles tanto desde el inicio como desde el objetivo e intenta unirlos de forma voraz.

Como el paso de extensión solo necesita una forma de moverse de un estado hacia otro, RRT también aborda la planificación cinodinámica, en la que el robot no puede moverse en línea recta por su espacio de estados. El paso de extensión aplica entonces controles muestreados u optimizados y simula la dinámica hacia adelante, como en el RRT cinodinámico de LaValle y Kuffner, o encadena primitivas de movimiento precalculadas. Esto lo hace útil para vehículos, robots con patas y manipulación rica en contactos, donde la métrica de distancia y el paso de extensión deben diseñarse en torno a la dinámica. Los caminos de RRT suelen ser irregulares y no óptimos, y añadir más muestras no mejora un camino una vez encontrado. RRT\ añade un paso de elección del padre y un paso de recableado que reconecta nodos cercanos siempre que exista una ruta más barata, lo que lo hace asintóticamente óptimo a costa de más cómputo por muestra. Cuando se necesita un camino factible con rapidez, RRT simple o RRT-Connect seguido de atajos y suavizado sigue siendo una opción habitual.

Por qué importa

RRT hizo práctica la planificación de movimiento para robots con muchos grados de libertad y para sistemas con dinámica, y sigue siendo un planificador por defecto en bibliotecas como OMPL y MoveIt. Muchos planificadores posteriores, incluido RRT*, se construyen sobre su estructura.

Aplicaciones clave

• Planificación de movimiento de brazos robóticos en espacios de trabajo abarrotados
• Planificación cinodinámica para coches, drones y robots con patas
• Planificación de manipulación rica en contactos con métricas de distancia personalizadas
• Planificación sobre grafos de primitivas de movimiento para la locomoción
• Exploración de entornos desconocidos

En la práctica

Un equipo que configura MoveIt para un brazo de siete ejes que coge artículos de estanterías usa RRT-Connect de OMPL como planificador por defecto. La comprobación de colisiones usa el modelo del robot y un octree construido a partir de una cámara de profundidad. El equipo fija el límite de tiempo de planificación y el tamaño del paso de extensión en relación con la holgura de las aberturas de las estanterías, y luego posprocesa cada camino con atajos y parametrización temporal para que el brazo se mueva con suavidad. Cuando la planificación tiene dificultades para llegar al fondo de compartimentos estrechos, aumenta el sesgo hacia el objetivo o prueba un planificador que se comporte mejor en pasos estrechos, y para consultas repetidas en una celda estática considera en su lugar un mapa de rutas probabilístico.

Ideas erróneas comunes

• RRT encuentra el camino más corto — encuentra un camino factible; para una buena calidad de camino se necesita RRT* o un posprocesamiento
• RRT garantiza encontrar un camino en un tiempo fijado — es probabilísticamente completo, así que encuentra un camino con una probabilidad que tiende a uno a medida que continúa el muestreo, y los pasos estrechos pueden llevar mucho tiempo
• RRT* siempre es la mejor opción — mejora los caminos con el tiempo, pero tarda más en dar una primera solución; RRT-Connect con suavizado suele preferirse cuando importa la velocidad

Quién debería saberlo

• Ingenieros de planificación de movimiento
• Desarrolladores de manipulación y de robots móviles que usan MoveIt u OMPL
• Ingenieros de planificación de vehículos autónomos y drones
• Estudiantes de robótica

Tecnologías relacionadas

• OMPL
• MoveIt
• RRT-Connect
• RRT cinodinámico (Kinodynamic RRT)
• Informed RRT*
• Atajos de caminos (Path Shortcutting)

Términos relacionados

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

Proyectos relacionados

• 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

Vídeos

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