Explorando rápidamente un árbol aleatorio

Algoritmo de búsqueda

Un árbol aleatorio de exploración rápida (RRT) es un algoritmo diseñado para buscar eficientemente 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 del problema no buscadas. 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 cinedinámicas) y se han utilizado ampliamente en la planificación del movimiento robótico autónomo .

Los RRT pueden verse como una técnica para generar trayectorias de bucle abierto para sistemas no lineales con restricciones de estado. Un RRT también puede considerarse como un método de Monte-Carlo para sesgar la búsqueda en las regiones de Voronoi más grandes de un gráfico en un espacio de configuración. Algunas variaciones pueden incluso considerarse fractales estocásticos . ^[3]

Los 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.

Descripción

Un RRT hace crecer un árbol enraizado en la configuración inicial mediante el uso de muestras aleatorias del espacio de búsqueda. A medida que se extrae cada muestra, se intenta una conexión entre ella y el estado más cercano en el árbol. Si la conexión es factible (pasa completamente a través del espacio libre y obedece cualquier restricción), esto da como resultado la adición del 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 . Como las regiones más grandes de Voronoi pertenecen a los estados en la frontera de la búsqueda, esto significa que el árbol se expande preferentemente hacia grandes áreas no buscadas.

La duración de la conexión entre el árbol y un nuevo estado suele estar limitada por un factor de crecimiento. Si la muestra aleatoria está más lejos de su estado más cercano en el árbol de lo que permite este límite, se utiliza un nuevo estado a la distancia máxima desde el árbol a lo largo de la línea hasta la muestra aleatoria en lugar de la muestra aleatoria en sí. Entonces 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 llenar el espacio del RRT al tiempo que limita el tamaño del crecimiento incremental.

El crecimiento del 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 esto para guiar la búsqueda hacia los objetivos del problema de planificación. Esto se logra introduciendo una pequeña probabilidad de muestreo del objetivo en el procedimiento de muestreo estatal. Cuanto mayor sea esta probabilidad, más ávidamente crecerá el árbol hacia la meta.

Algoritmo

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

Construcción de algoritmoRRT Entrada: configuración inicial q init , número de vértices en RRT K , distancia incremental Δq Salida: gráfico RRT G G .init( q init ) para  k = 1 a  K  hacer  q rand ← RAND_CONF() q cerca ← NEAREST_VERTEX( q rand , G ) q nuevo ← NEW_CONF( q cerca , q rand , Δq ) G .add_vertex( q nuevo ) G .add_edge ( q cerca , q nuevo ) regresa  G

• "←" indica asignación . Por ejemplo, " mayor ← artículo " significa que el valor del mayor cambia al valor del artículo .
• " return " finaliza el algoritmo y genera el siguiente valor.

En el algoritmo anterior, " RAND_CONF " toma una configuración aleatoria q _rand en C. Esto puede reemplazarse con una función " RAND_FREE_CONF " que usa muestras en C _free , mientras rechaza aquellas en C _obs usando algún algoritmo de detección de colisiones.

" NEAREST_VERTEX " es una función que recorre todos los vértices v en el gráfico G , calcula la distancia entre q _rand yv usando alguna función de medición , devolviendo así el vértice más cercano.

" NEW_CONF " selecciona una nueva configuración q _nueva moviendo una distancia incremental Δq desde q _cerca en la dirección de q _rand . (Según ^[4] en problemas holonómicos, esto debe omitirse y usarse q _rand en lugar de q _new .)

Variantes y mejoras para la planificación de movimientos.

• RRT-Rope, ^[5] un método para la planificación rápida de rutas casi óptimas utilizando un enfoque de acortamiento determinista, muy eficaz en entornos abiertos y grandes.

• RRT dirigidos por juegos parciales (PDRRT), ^[6] un método que combina RRT con el método de juegos parciales ^[7] para refinar la búsqueda donde es necesaria (por ejemplo, alrededor de obstáculos) para poder planificar más rápido y resolver más movimientos. problemas de planificación que RRT

• Circuito cerrado de exploración rápida aleatoria (CL-RRT), ^[8] una extensión de RRT que muestrea una entrada a un sistema de circuito cerrado estable que consta del vehículo y un controlador.

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

• Exploración rápida del gráfico aleatorio (RRG) y RRT*, ^{[9] [10] [11]} una variante de RRT que converge hacia una solución óptima

• LQR-RRT , ^[12] una variante cinedinámica para dinámicas complejas o subactuadas

• RRT ⁺ , ^[13] 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, ^[14] un método para acelerar la tasa de convergencia de RRT* mediante el uso de optimización de ruta (de manera similar a Theta* ) y muestreo inteligente (sesgando el muestreo hacia los vértices de ruta, que, después de la optimización de ruta, son probablemente estar cerca de obstáculos)

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

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

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

• RRT* informado, ^{[20] [21]} mejora la velocidad de convergencia de RRT* introduciendo una heurística, similar a la forma en que A* mejora el algoritmo de Dijkstra.

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

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

• Theta*-RRT, ^{[25] 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, ^{[26] [27]} extensión de RRT* para entornos dinámicos
• RRT-GPU, ^[28] implementación de RRT tridimensional que utiliza aceleración de hardware

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

• CERRT, ^[30] un planificador de RRT que modela la incertidumbre, que se reduce al explotar los contactos
• MVRRT*, ^[31] Violación mínima RRT*, un algoritmo que encuentra la ruta más corta que minimiza el nivel de inseguridad (el "coste" de las reglas ambientales que han sido violadas, por ejemplo, las leyes de tránsito)

• RRT-Blossom, ^[32] Planificador RRT para entornos altamente restringidos.

• RRV, ^[33] 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, ^[34] utiliza cálculos de distancia simples en el espacio de trabajo para expandir el árbol en lugar de una costosa verificación de colisiones.

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

• RRdT*, ^{[36] [37]} 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, ^{[38] [39]} Método de recableado triangular basado en desigualdad con algoritmo RRT-Connect para acercarlo al óptimo.

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

Ver también

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

Referencias

1. LaValle, Steven M. (octubre de 1998). "Árboles aleatorios de rápida exploración: una nueva herramienta para la planificación de rutas" (PDF) . Informe técnico (TR 98-11). Departamento de Ciencias de la Computación, Universidad Estatal de Iowa.
2. LaValle, Steven M .; Kuffner Jr., James J. (2001). "Planificación cinedinámica aleatoria" (PDF) . La Revista Internacional de Investigación en Robótica . 20 (5): 378–400. doi :10.1177/02783640122067453. S2CID  40479452.
3. http://msl.cs.uiuc.edu/rrt/about.html Archivado el 21 de octubre de 2007 en Wayback Machine Acerca de los RRT, por Steve LaValle
4. Árboles aleatorios de exploración rápida: progreso y perspectivas (2000), por Steven M. Lavalle, James J. Kuffner, Jr. Robótica algorítmica y computacional: nuevas direcciones, http://eprints.kfupm.edu.sa/60786/1 /60786.pdf ^{[ enlace muerto permanente ]}
5. Pequeño, Luis; Desbiens, Alexis Lussier (17 de octubre de 2021). "RRT-Rope: un enfoque de acortamiento determinista para una planificación rápida de rutas casi óptimas en entornos 3D ordenados a gran escala". 2021 Conferencia internacional IEEE sobre sistemas, hombre y cibernética (SMC) . Melbourne, Australia: IEEE. págs. 1111-1118. doi :10.1109/SMC52423.2021.9659071. ISBN 978-1-6654-4207-7. S2CID  252590377.
6. Ranganathan, Ananth; König, Sven . PDRRT: "Integración de la planificación basada en gráficos y en células". En Actas de la Conferencia Internacional IEEE sobre Robots y Sistemas Inteligentes (IROS) , páginas 2799–2808, 2004.
7. Moore, AW; Atkeson, CG, "El algoritmo de juego parcial para el aprendizaje por refuerzo de resolución variable en espacios de estados multidimensionales", Machine Learning , vol. 21, núm. 3, páginas 199–233, 1995.
8. Kuwata, Yoshiaki; Teo, Justino; Fiore, Gastón; Karaman, Sertac; Frazzoli, Emilio; Cómo, Jonathan P. (septiembre de 2009). "Planificación del movimiento en tiempo real con aplicaciones a la conducción urbana autónoma" (PDF) . Transacciones IEEE sobre tecnología de sistemas de control . 17 (5): 1105-1118. CiteSeerX 10.1.1.169.7922 . doi :10.1109/tcst.2008.2012116. hdl :1721.1/52527. S2CID  14526513. Archivado desde el original (PDF) el 12 de junio de 2021 . Consultado el 10 de abril de 2017 . 
9. Karaman, Sertac; Frazzoli, Emilio (3 de mayo de 2010). "Algoritmos basados ​​en muestreo incremental para una planificación óptima del movimiento". arXiv : 1005.0416 [cs.RO].
10. Karaman, Sertac; Frazzoli, Emilio (5 de mayo de 2011). "Algoritmos basados ​​en muestreo para una planificación óptima del movimiento". arXiv : 1105.1186 [cs.RO].
11. OlzhasAdi (26 de enero de 2015). «RRT* Breve explicación» (vídeo) . YouTube . Archivado desde el original el 12 de diciembre de 2021 . Consultado el 3 de agosto de 2016 .
12. Pérez, Alejandro; Platt, Robert; Konidaris, George; Kaelbling, Leslie; Lozano-Pérez, Tomás (mayo de 2012). "LQR-RRT *: planificación de movimiento óptima basada en muestreo con heurísticas de extensión derivadas automáticamente". Conferencia Internacional IEEE 2012 sobre Robótica y Automatización . págs. 2537–2542. doi :10.1109/ICRA.2012.6225177. ISBN 978-1-4673-1405-3. S2CID  1914056.
13. Xanthidis, Marios; Espósito, Joel M.; Rekleítis, Ioannis; O'Kane, Jason M. (1 de diciembre de 2020). "Planificación del movimiento mediante muestreo en subespacios de dimensión progresivamente creciente". Revista de sistemas inteligentes y robóticos . 100 (3): 777–789. doi :10.1007/s10846-020-01217-w. ISSN  1573-0409. S2CID  3622004.
14. Islam, Fahad; Nasir, Jauwairia; Malik, Usman; Ayaz, Yasar; Hasan, Osman; "RRT*-Smart: Implementación de convergencia rápida de RRT* hacia una solución óptima", en Actas de la Conferencia Internacional IEEE sobre Mecatrónica y Automatización (ICMA) , páginas 1651–1656, Chengdu, China, agosto de 2012.
15. Brunner, M.; Bruggemann, B.; Schulz, D.. "Planificación jerárquica del movimiento de terreno accidentado utilizando un método óptimo basado en muestreo", en Int. Conf. sobre Robótica y Automatización (ICRA) , Karlsruhe, Alemania, 2013.
16. Adiyatov, Olzhas; Varol, Huseyin Atakan. "Planificación de movimiento eficiente de la memoria basada en árboles aleatorios de exploración rápida". En Mecatrónica y Automatización (ICMA), Conferencia Internacional IEEE 2013 en , páginas 354–359, 2013. doi :10.1109/ICMA.2013.6617944
17. Adiyatov, Olzhas; Varol, Atakan (2013). "Caja de herramientas MATLAB de algoritmos RRT, RRT* y RRT*FN" . Consultado el 3 de agosto de 2016 .
18. OlzhasAdi (26 de enero de 2015). "Breve explicación de RRT*FN" (vídeo) . YouTube . Archivado desde el original el 12 de diciembre de 2021 . Consultado el 3 de agosto de 2016 .
19. Choudhury, Sanjiban; Scherer, Sebastián; Singh, Sanjiv. "RRT*-AR: Planificación de rutas alternativas basada en muestreo con aplicaciones al aterrizaje autónomo de emergencia de un helicóptero". En Robotics and Automation (ICRA), Conferencia internacional IEEE de 2013 , Karlsruhe, 6 a 10 de mayo de 2013, páginas 3947–3952. doi :10.1109/ICRA.2013.6631133
20. Gammell, Jonathan D.; Srinivasa, Siddhartha S.; Barfoot, Timothy D. (8 de abril de 2014). "RRT informado *: planificación de ruta óptima basada en muestreo enfocada mediante muestreo directo de una heurística elipsoidal admisible". Conferencia internacional IEEE/RSJ 2014 sobre robots y sistemas inteligentes . págs. 2997–3004. arXiv : 1404.2334 . doi :10.1109/IROS.2014.6942976. ISBN 978-1-4799-6934-0. S2CID  12233239.
21. utiasASRL (4 de julio de 2014). «RRT informado*@UTIAS (IROS 2014)» (vídeo) . YouTube . Archivado desde el original el 12 de diciembre de 2021 . Consultado el 3 de agosto de 2016 .
22. Naderi, Kourosh; Rajamäki, Joose; Hämäläinen, Perttu (2015). "RT-RRT*: un algoritmo de planificación de rutas en tiempo real basado en RRT*". En actas de la octava conferencia ACM SIGGRAPH sobre movimiento en juegos (MIG '15). ACM, Nueva York, NY, EE. UU., 113–118. doi :10.1145/2822013.2822036
23. "RRTX: planificación/replanificación del movimiento en tiempo real para entornos con obstáculos impredecibles" (PDF) . Archivado desde el original (PDF) el 19 de mayo de 2017 . Consultado el 2 de marzo de 2018 .
24. Comparación de RRTX, RRT# y RRT* cuando se descubre un acceso directo en un entorno estático
25. Palmieri, Luigi; Koenig, Sven ; Arras, Kai O. "Planificación de movimiento no holonómico basada en RRT utilizando polarización de ruta en cualquier ángulo". En Robótica y Automatización (ICRA), 2016 Actas de la Conferencia Internacional IEEE en , páginas 2775-2781, 2016.
26. RRT* FND: planificación de movimiento en entornos dinámicos
27. Adiyatov, Olzhas; Varol, Huseyin Atakan. "Un novedoso algoritmo basado en RRT para la planificación del movimiento en entornos dinámicos". En Mecatrónica y Automatización (ICMA), Conferencia Internacional IEEE 2017 en , páginas 1416-1421, 2017. doi :10.1109/ICMA.2017.8016024
28. Ford, Christen (12 de junio de 2018). RRT-GPU y Minecraft: hardware acelerado que explora rápidamente árboles aleatorios en tres dimensiones (tesis). doi :10.13140/rg.2.2.15658.11207.
29. Amiryan, Javad; Jamzad, Mansour (2015). Planificación adaptativa del movimiento con campos de potencial artificial utilizando un camino previo. Robótica y Mecatrónica (ICROM), 2015 3ra Conferencia Internacional RSI sobre. págs. 731–736.
30. Sieverling, Arne; Eppner, Clemens; Wolff, Félix; Brock, Oliver (2017). Intercalando movimiento en contacto y en espacio libre para planificar bajo incertidumbre (PDF) . Conferencia internacional IEEE/RSJ 2017 sobre robots y sistemas inteligentes (IROS). págs. 4011–4073.
31. Rusia, Daniela; Frazzoli, Emilio; Karaman, Sertac; Tumova, Jana; Chaudhari, Pratik; Castro, Luis I. Reyes (6 de mayo de 2013). "Algoritmo basado en muestreo incremental para la planificación del movimiento con infracción mínima". arXiv : 1305.1102 [cs.RO].
32. "Maciej Kalisiak - RRT-flor". www.dgp.toronto.edu . Consultado el 18 de enero de 2020 .
33. Tahirovic, Adnan; Ferizbegovic, Mina (mayo de 2018). "Rápidamente explorando Random Vines (RRV) para la planificación del movimiento en espacios de configuración con pasajes estrechos". Conferencia Internacional IEEE 2018 sobre Robótica y Automatización (ICRA) . págs. 7055–7062. doi :10.1109/ICRA.2018.8460186. ISBN 978-1-5386-3081-5. S2CID  52285080.
34. Lacevic, Bakir; Osmankovic, Dinko; Ademovic, Adnan (mayo de 2016). "Burs de espacio C libre: una estructura novedosa para la planificación de rutas". Conferencia Internacional IEEE 2016 sobre Robótica y Automatización (ICRA) . págs. 70–76. doi :10.1109/ICRA.2016.7487117. ISBN 978-1-4673-8026-3. S2CID  15834630.
35. Sintov, Avishai; Shapiro, Amir (2014). "Algoritmo RRT basado en el tiempo para la planificación de encuentros de dos sistemas dinámicos". Conferencia Internacional IEEE 2014 sobre Robótica y Automatización (ICRA) . Conferencia Internacional IEEE sobre Robótica y Automatización (ICRA). págs. 6745–6750. doi :10.1109/ICRA.2014.6907855. ISBN 978-1-4799-3685-4.
36. Lai, estaño; Ramos, Fabio; Francisco, Gilad (2019). "Equilibrio de la exploración global y la explotación de la conectividad local con árboles inconexos aleatorios que se exploran rápidamente". 2019 Congreso Internacional de Robótica y Automatización (ICRA) . Montreal, QC, Canadá: IEEE. págs. 5537–5543. arXiv : 1810.03749 . doi :10.1109/ICRA.2019.8793618. ISBN 978-1-5386-6027-0. S2CID  52945105.
37. Lai, estaño; Moreré, Philippe; Ramos, Fabio; Francis, Gilad (abril de 2020). "Planificación bayesiana basada en muestreo local". Cartas de robótica y automatización IEEE . 5 (2): 1954-1961. arXiv : 1909.03452 . doi :10.1109/LRA.2020.2969145. S2CID  210838739.
38. Kang, Jin-Gu; Lim, Dong Woo; Choi, Yong-Sik; Jang, Woo-Jin; Jung, Jinwoo (6 de enero de 2021). "Algoritmo de conexión RRT mejorado basado en desigualdad triangular para la planificación de rutas de robots". Sensores . 21 (2): 333. doi : 10.3390/s21020333 . ISSN  1424-8220. PMC 7825297 . S2CID  231303809. 
39. Kang, Jin-Gu; Jung, Jinwoo (12 de julio de 2021). "Método de recableado post-triangular para planificación de rutas de robot RRT más cortas". arXiv : 2107.05344 [cs.RO].
40. Strub, Marlin P.; Gammell, Jonathan D. (2 de noviembre de 2021). "AIT * y EIT *: planificación de rutas basada en muestreo bidireccional asimétrico". arXiv : 2111.01877 [cs.RO].

enlaces externos

• Medios relacionados 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 rutas de tiempo mínimo de Dubins
• Implementación de RRT* de Open Motion Planning Library