Exploración rápida de árboles aleatorios

Visualización de un gráfico RRT después de 45 y 390 iteraciones.

Una animación de un RRT desde la iteración 0 hasta la 10000.

Un árbol aleatorio de exploración rápida (RRT) es un algoritmo diseñado para buscar eficientemente en espacios no convexos de alta dimensión mediante la construcción aleatoria de un árbol que llena el espacio . El árbol se construye incrementalmente a partir de muestras extraídas aleatoriamente del espacio de búsqueda y está inherentemente sesgado para crecer hacia grandes áreas no exploradas del problema. Los RRT fueron desarrollados por Steven M. LaValle y James J. Kuffner Jr. ^{[ 1 ] [ 2 ]} Manejan fácilmente problemas con obstáculos y restricciones diferenciales ( no holonómicas y cinemáticas) y se han utilizado ampliamente en la planificación de movimiento robótico autónomo .

Las RRT pueden considerarse una técnica para generar trayectorias de lazo abierto para sistemas no lineales con restricciones de estado. Una RRT también puede considerarse un método de Montecarlo para sesgar la búsqueda hacia las regiones de Voronoi más grandes de un grafo en un espacio de configuración. Algunas variaciones incluso pueden considerarse fractales estocásticos . ^{[ 3 ]}

Las RRT se pueden utilizar para calcular políticas de control aproximadas para controlar sistemas no lineales de alta dimensión con restricciones de estado y acción.

Un RRT construye un árbol con raíz en la configuración inicial mediante muestras aleatorias del espacio de búsqueda. A medida que se extrae cada muestra, se intenta establecer una conexión entre ella y el estado más cercano en el árbol. Si la conexión es factible (atraviesa completamente el espacio libre y cumple con las restricciones), se añade el nuevo estado al árbol. Con un muestreo uniforme del espacio de búsqueda, la probabilidad de expandir un estado existente es proporcional al tamaño de su región de Voronoi . Dado que las regiones de Voronoi más grandes pertenecen a los estados en la frontera de la búsqueda, esto significa que el árbol se expande preferentemente hacia grandes áreas no exploradas.

La longitud de la conexión entre el árbol y un nuevo estado suele estar limitada por un factor de crecimiento. Si la muestra aleatoria se encuentra a una distancia mayor de su estado más cercano en el árbol que la permitida por este límite, se utiliza un nuevo estado situado a la máxima distancia del árbol a lo largo de la línea que conecta con la muestra aleatoria, en lugar de la propia muestra. De este modo, se puede considerar que las muestras aleatorias controlan la dirección del crecimiento del árbol, mientras que el factor de crecimiento determina su tasa. Esto mantiene el sesgo de llenado del espacio del RRT, al tiempo que limita la magnitud del crecimiento incremental.

El crecimiento de los árboles de decisión aleatorios (RRT) puede verse sesgado al aumentar la probabilidad de muestrear estados de un área específica. La mayoría de las implementaciones prácticas de RRT utilizan este sesgo para guiar la búsqueda hacia los objetivos del problema de planificación. Esto se logra introduciendo una pequeña probabilidad de muestrear el objetivo en el procedimiento de muestreo de estados. Cuanto mayor sea esta probabilidad, más vorazmente crecerá el árbol hacia el objetivo.

Para un espacio de configuración general C , el algoritmo en pseudocódigo es el siguiente:

Construir algoritmo RRT Entrada: Configuración inicial q init , número de vértices en RRT K , distancia incremental Δq. Salida: Grafo RRT G.G.init ( q init ) para k = 1 a K hacer q rand ← RAND_CONF() q near ← NEAREST_VERTEX( q rand , G ) q new ← NEW_CONF( q near , q rand , Δq ) G.add_vertex ( q new ) G.add_edge ( q near , q new ) retornar G

En el algoritmo anterior, " RAND_CONF " selecciona una configuración aleatoria q _rand en C. Esto puede reemplazarse con una función " RAND_FREE_CONF " que utiliza muestras en C _free , mientras rechaza las que se encuentran en C _obs mediante algún algoritmo de detección de colisiones .

" NEAREST_VERTEX " es una función que recorre todos los vértices v en el grafo _G , calcula la distancia entre q y v utilizando alguna función de medición y devuelve el vértice más cercano.

" NEW_CONF " selecciona una nueva configuración q _new moviéndose una distancia incremental Δq desde q _near en la dirección de q _rand . (Según ^{[ 4 ]} , en problemas holonómicos, esto debería omitirse y utilizarse q _rand en lugar de q _new ).

Se ha demostrado que, bajo «condiciones técnicas moderadas», el coste de la mejor ruta en el RRT converge casi con seguridad a un valor no óptimo. ^{[ 5 ]} Por ello, es deseable encontrar variantes del RRT que converjan a un óptimo, como el RRT*. A continuación se presenta una lista de métodos basados ​​en el RRT* (comenzando con el propio RRT*). Sin embargo, no todos los métodos derivados convergen a un óptimo.

• Exploración rápida de grafos aleatorios (RRG) y RRT*, ^{[ 5 ] [ 6 ] [ 7 ]} una variante de RRT que converge hacia una solución óptima

• LQR-RRT , ^{[ 8 ]} una variante cinemática para dinámicas complejas o subactuadas

• RRT ⁺ , ^{[ 9 ]} una familia de planificadores basados ​​en RRT que tienen como objetivo generar soluciones para sistemas de alta dimensión en tiempo real, mediante la búsqueda progresiva en subespacios de menor dimensión.

• RRT*-Smart, ^{[ 10 ]} un método para acelerar la tasa de convergencia de RRT* mediante la optimización de rutas (de forma similar a Theta* ) y el muestreo inteligente (sesgando el muestreo hacia los vértices de la ruta que, después de la optimización de la ruta, tienen más probabilidades de estar cerca de obstáculos).

• A*-RRT y A*-RRT*, ^{[ 11 ]} un método de planificación de movimiento de dos fases que utiliza un algoritmo de búsqueda de grafos para buscar una ruta factible inicial en un espacio de baja dimensión (sin considerar el espacio de estados completo) en una primera fase, evitando áreas peligrosas y prefiriendo rutas de bajo riesgo, que luego se utiliza para enfocar la búsqueda RRT* en el espacio continuo de alta dimensión en una segunda fase.

• RRT*FN, ^{[ 12 ] [ 13 ] [ 14 ]} RRT* con un número fijo de nodos, que elimina aleatoriamente un nodo hoja en el árbol en cada iteración

• RRT*-AR, ^{[ 15 ]} planificación de rutas alternativas basada en muestreo

• RRT* informado, ^{[ 16 ] [ 17 ]} mejora la velocidad de convergencia de RRT* mediante la introducción de una heurística , similar a la forma en que A* mejora el algoritmo de Dijkstra.

• RRT* en tiempo real (RT-RRT*), ^{[ 18 ]} una variante de RRT* y RRT* informado que utiliza una estrategia de reconfiguración de árboles en línea que permite que la raíz del árbol se mueva con el agente sin descartar rutas muestreadas previamente, con el fin de obtener planificación de rutas en tiempo real en un entorno dinámico como un juego de computadora.

• RRT ^X y RRT ^# , ^{[ 19 ] [ 20 ]} optimización de RRT* para entornos dinámicos

• Theta*-RRT, ^{[ 21 ]} un método de planificación de movimiento de dos fases similar a A*-RRT* que utiliza una combinación jerárquica de búsqueda de cualquier ángulo con planificación de movimiento RRT para la generación rápida de trayectorias en entornos con restricciones no holonómicas complejas.

• RRT* FND, ^{[ 22 ] [ 23 ]} extensión de RRT* para entornos dinámicos
• RRT-GPU, ^{[ 24 ]} implementación tridimensional de RRT que utiliza aceleración de hardware

• APF-RRT, ^{[ 25 ]} una combinación del planificador RRT con el método de campos potenciales artificiales que simplifica la tarea de replanificación.

• CERRT, ^{[ 26 ]} un planificador RRT modelando la incertidumbre, que se reduce explotando los contactos
• MVRRT*, ^{[ 27 ]} RRT* de mínima violación, un algoritmo que encuentra la ruta más corta que minimiza el nivel de inseguridad (el "costo" de las reglas ambientales que se han violado, por ejemplo, leyes de tránsito)

• RRT-Blossom, ^{[ 28 ]} Planificador RRT para entornos altamente restringidos.

• RRV, ^{[ 29 ]} expande eficientemente el árbol alrededor de obstáculos y a través de pasajes estrechos, utilizando vectores propios dominantes alrededor de los nodos del árbol.

• RBT, ^{[ 30 ]} utiliza cálculos de distancia simples en el espacio de trabajo para expandir el árbol en lugar de una costosa comprobación de colisión.

• TB-RRT, ^{[ 31 ]} Algoritmo RRT basado en el tiempo para la planificación de encuentros de dos sistemas dinámicos.

• RRdT*, ^{[ 32 ] [ 33 ]} un planificador basado en RRT* que utiliza múltiples árboles locales para equilibrar activamente la exploración y explotación del espacio mediante la realización de muestreos locales.

• Tri-RRT-Connect, ^{[ 34 ] [ 35 ]} Método de recableado basado en desigualdad triangular con algoritmo RRT-Connect para acercarlo al óptimo.

• RRT-Rope, ^{[ 36 ]} un método para la planificación de rutas rápidas casi óptimas que utiliza un enfoque de acortamiento determinista, muy eficaz en entornos abiertos y grandes.

• RRT dirigidos por juegos parciales (PDRRT), ^{[ 37 ]} un método que combina RRT con el método de juegos parciales ^{[ 38 ]} para refinar la búsqueda donde sea necesario (por ejemplo, alrededor de obstáculos) para poder planificar más rápido y resolver más problemas de planificación de movimiento que RRT

• El algoritmo CL-RRT (Closed-loop quickly exploring random), ^{[ 39 ]} es una extensión del algoritmo RRT que muestrea una entrada a un sistema estable de bucle cerrado compuesto por el vehículo y un controlador.

• Árboles informados adaptativamente (AIT*) y árboles informados por el esfuerzo (EIT*) ^{[ 40 ]}

• Planificación de rutas desde cualquier ángulo
• Hoja de ruta probabilística
• Árbol que llena el espacio
• Planificación de movimiento
• Algoritmo aleatorio

• Contenido multimedia relacionado con la exploración rápida de árboles aleatorios en Wikimedia Commons.
• Visualizador Java de RRT y RRT* que incluye editor de mapas
• Implementación en C++ de RRT utilizando las rutas de tiempo mínimo de Dubins.
• Implementación de RRT* de la biblioteca de planificación de movimiento abierto