De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Parte de una serie sobre
Estructuras de datos probabilísticas
Árboles aleatorios
Relacionados
Una animación de un RRT a partir de la iteración 0 a 10000

Un árbol aleatorio de exploración rápida (RRT) es un algoritmo diseñado para buscar de manera eficiente espacios no convexos y de alta dimensión mediante la construcción aleatoria de un árbol que llena el espacio . El árbol se construye de forma incremental a partir de muestras extraídas al azar del espacio de búsqueda y está intrínsecamente sesgado para crecer hacia áreas grandes del problema sin buscar. 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 cinodiná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 se puede considerar 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]

Descripción [ editar ]

Una 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 establecer una conexión entre ella y el estado más cercano del á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 longitud 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í. Las muestras aleatorias pueden entonces verse como que controlan la dirección del crecimiento del árbol, mientras que el factor de crecimiento determina su tasa. Esto mantiene el sesgo de llenado de espacio del RRT al tiempo que limita el tamaño del crecimiento incremental.

El crecimiento de RRT puede estar sesgado aumentando la probabilidad de muestrear estados de un área específica. La mayoría de las implementaciones prácticas de RRT hacen uso de esto para guiar la búsqueda hacia los objetivos del problema de planificación. Esto se logra introduciendo una pequeña probabilidad de muestreo de la meta en el procedimiento de muestreo estatal. Cuanto mayor sea esta probabilidad, más ávidamente crecerá el árbol hacia la meta.

Algoritmo [ editar ]

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

Algoritmo BuildRRT 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 ) for  k = 1 to  K  do  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 cerca , q nuevo ) return  G
  • "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
  • " return " termina el algoritmo y genera el siguiente valor.

En el algoritmo anterior, " RAND_CONF " agarra un azar configuración q rand en C . Esto puede ser reemplazado por una función " RAND_FREE_CONF " que usa muestras en C libre , mientras que rechaza las de C obs usando algún algoritmo de detección de colisiones.

" NEAREST_VERTEX " es una función que se ejecuta a través de todos los vértices v en el gráfico G , calcula la distancia entre q rand y v usando alguna función de medición volviendo así el vértice más próximo.

" NEW_CONF " selecciona una nueva configuración q new moviendo una distancia incremental Δq desde q cerca en la dirección de q rand . (De acuerdo con [4] en problemas holonómicos, esto debe omitirse y se debe usar q rand en lugar de q nuevo ).

Variantes y mejoras para la planificación del movimiento.[ editar ]

  • RRT dirigidos por parti-juego (PDRRT), [5] un método que combina RRT con el método de parti-juego [6] para refinar la búsqueda donde se necesita (por ejemplo, alrededor de obstáculos) para poder planificar más rápido y resolver más movimiento problemas de planificación que RRT
  • Aleatorio de exploración rápida de circuito cerrado (CL-RRT), [7] 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, en "condiciones técnicas moderadas", el coste de la mejor ruta en el RRT converge casi con seguridad a un valor no óptimo. [8] Por esa razón, es deseable encontrar variantes del RRT que converjan a un óptimo, como RRT *. A continuación se muestra una lista de métodos basados ​​en RRT * (comenzando con RRT *). Sin embargo, no todos los métodos derivados convergen a un óptimo.

  • Gráfico aleatorio de exploración rápida (RRG) y RRT *, [8] [9] [10] una variante de RRT que converge hacia una solución óptima
  • RRT * -Smart, [11] un método para acelerar la tasa de convergencia de RRT * mediante el uso de la optimización de la ruta (de manera 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, es probable estar cerca de los obstáculos)
  • A * -RRT y A * -RRT *, [12] 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 inicial factible en un espacio de baja dimensión (sin considerar el espacio de estado completo) en un 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, [13] [14] [15] RRT * con un número fijo de nodos, que elimina aleatoriamente un nodo hoja en el árbol en cada iteración
  • RRT * -AR, [16] planificación de rutas alternativas basada en muestreo
  • RRT * informado, [17] [18] mejora la velocidad de convergencia de RRT * al introducir una heurística, similar a la forma en que A * mejora el algoritmo de Dijkstra
  • RRT en tiempo real * (RT-RRT *), [19] una variante de RRT * y RRT informado * que utiliza una estrategia de recableado de árboles en línea que permite que la raíz del árbol se mueva con el agente sin descartar las 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 # , [20] [21] optimización de RRT * para entornos dinámicos
  • Theta * -RRT, [22] 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 en cualquier ángulo con planificación de movimiento RRT para la generación rápida de trayectorias en entornos con restricciones complejas no holonómicas
  • RRT * FND, [23] extensión de RRT * para entornos dinámicos
  • RRT-GPU, [24] implementación RRT tridimensional que utiliza aceleración de hardware
  • APF-RRT, [25] una combinación del planificador RRT con el método de campos de potencial artificial que simplifican la tarea de replanificación
  • CERRT, [26] un planificador de RRT que modela la incertidumbre, que se reduce al explotar contactos
  • MVRRT *, [27] Violación mínima RRT *, un algoritmo que encuentra la ruta más corta que minimiza el nivel de inseguridad (el "costo" de las reglas ambientales que han sido violadas, por ejemplo, leyes de tránsito)
  • RRT-Blossom, [28] Planificador RRT para entornos muy restringidos.
  • TB-RRT, [29] Algoritmo de RRT basado en el tiempo para la planificación de encuentros de dos sistemas dinámicos.
  • RRdT *, [30] un planificador basado en RRT * que utiliza múltiples árboles locales para equilibrar activamente la exploración y explotación del espacio realizando un muestreo local.

Ver también [ editar ]

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

Referencias [ editar ]

  1. ^ LaValle, Steven M. (octubre de 1998). "Exploración rápida de árboles aleatorios: una nueva herramienta para la planificación de rutas" (PDF) . Informe técnico . Departamento de Ciencias de la Computación, Universidad Estatal de Iowa (TR 98-11).
  2. ^ LaValle, Steven M .; Kuffner Jr., James J. (2001). "Planificación cinodinámica aleatoria" (PDF) . Revista Internacional de Investigación en Robótica (IJRR) . 20 (5): 378–400. doi : 10.1177 / 02783640122067453 . S2CID 40479452 .  
  3. ^ http://msl.cs.uiuc.edu/rrt/about.html 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. ^ Ranganathan, Ananth; Koenig, Sven . PDRRT: " Integración de la planificación basada en gráficos y basada en células ". En Actas de la Conferencia Internacional IEEE sobre Robots y Sistemas Inteligentes (IROS) , páginas 2799–2808, 2004.
  6. ^ Moore, AW; Atkeson, CG, " El algoritmo de parti-juego para el aprendizaje por refuerzo de resolución variable en espacios de estados multidimensionales ", Machine Learning , vol. 21, no. 3, páginas 199–233, 1995.
  7. ^ Kuwata, Yoshiaki; Teo, Justin; Fiore, Gaston; Karaman, Sertac; Frazzoli, Emilio; How, Jonathan P. (septiembre de 2009). "Planificación de 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 . Consultado el 10 de abril de 2017 .    CS1 maint: parámetro desalentado ( enlace )
  8. ^ a b 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 ].
  9. ^ 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 ].
  10. ^ OlzhasAdi (26 de enero de 2015). "RRT * Breve explicación" (video) . YouTube . Consultado el 3 de agosto de 2016 . CS1 maint: parámetro desalentado ( enlace )
  11. ^ 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.
  12. ^ Brunner, M .; Bruggemann, B .; Schulz, D .. " Planificación jerárquica del movimiento del terreno accidentado utilizando un método óptimo basado en el muestreo ", en Int. Conf. sobre Robótica y Automatización (ICRA) , Karlsruhe, Alemania, 2013.
  13. ^ Adiyatov, Olzhas; Varol, Huseyin Atakan. "Planificación de movimiento eficiente de memoria basada en árbol aleatorio 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
  14. ^ Adiyatov, Olzhas; Varol, Atakan (2013). "MATLAB Toolbox de algoritmos RRT, RRT * y RRT * FN" . Consultado el 3 de agosto de 2016 . CS1 maint: parámetro desalentado ( enlace )
  15. ^ OlzhasAdi (26 de enero de 2015). "RRT * FN Breve explicación" (video) . YouTube . Consultado el 3 de agosto de 2016 . CS1 maint: parámetro desalentado ( enlace )
  16. ^ Choudhury, Sanjiban; Scherer, Sebastián; Singh, Sanjiv. " RRT * -AR: Planificación de rutas alternativas por muestreo con aplicaciones al aterrizaje autónomo de emergencia de un helicóptero ". En Robótica y Automatización (ICRA), Conferencia Internacional IEEE 2013 , Karlsruhe, 6-10 de mayo de 2013, páginas 3947-3952. doi : 10.1109 / ICRA.2013.6631133
  17. ^ 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 a través del muestreo directo de una heurística elipsoidal admisible . 2014 IEEE / RSJ International Conference on Intelligent Robots and Systems . págs. 2997–3004. arXiv : 1404.2334 . doi : 10.1109 / IROS.2014.6942976 . ISBN 978-1-4799-6934-0. S2CID  12233239 .
  18. ^ utiasASRL (4 de julio de 2014). "RRT informado * @ UTIAS (IROS 2014)" (video) . YouTube . Consultado el 3 de agosto de 2016 . CS1 maint: parámetro desalentado ( enlace )
  19. ^ 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 8ª Conferencia ACM SIGGRAPH sobre Movimiento en Juegos (MIG '15). ACM, Nueva York, NY, EE. UU., 113–118. DOI = https://dx.doi.org/10.1145/2822013.2822036
  20. ^ RRT X : Planificación / replanificación de movimiento en tiempo real para entornos con obstáculos impredecibles
  21. ^ Comparación de RRTX, RRT # y RRT * cuando se descubre un acceso directo en un entorno estático
  22. ^ Palmieri, Luigi; Koenig, Sven ; Arras, Kai O. " Planificación de movimiento no holonómico basada en RRT usando polarización de ruta de cualquier ángulo ". En Robotics and Automation (ICRA), Actas de la Conferencia Internacional IEEE de 2016 en , páginas 2775-2781, 2016.
  23. ^ RRT * FND: planificación de movimiento en entornos dinámicos
  24. ↑ Ford, Christen (12 de junio de 2018). RRT-GPU y Minecraft: Hardware acelerado Exploración rápida de árboles aleatorios en tres dimensiones (Tesis). doi : 10.13140 / rg.2.2.15658.11207 .
  25. ^ Amiryan, Javad; Jamzad, Mansour (2015). Planificación de movimiento adaptativo con campos de potencial artificial utilizando una ruta previa . Robótica y Mecatrónica (ICROM), 2015 3ª Conferencia Internacional RSI sobre. págs. 731–736.
  26. ^ Sieverling, Arne; Eppner, Clemens; Wolff, Felix; Brock, Oliver (2017). Movimiento entrelazado en contacto y en espacio libre para planificar bajo incertidumbre (PDF) . 2017 IEEE / RSJ International Conference on Intelligent Robots and Systems (IROS). págs. 4011–4073.
  27. ^ Rus, Daniela; Frazzoli, Emilio; Karaman, Sertac; Tumova, Jana; Chaudhari, Pratik; Castro, Luis I. Reyes (6 de mayo de 2013). "Algoritmo basado en muestreo incremental para planificación de movimiento de violación mínima". arXiv : 1305.1102 [ cs.RO ].
  28. ^ "Maciej Kalisiak - RRT-flor" . www.dgp.toronto.edu . Consultado el 18 de enero de 2020 .
  29. ^ 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 sobre Robótica y Automatización (ICRA). doi : 10.1109 / ICRA.2014.6907855 .
  30. ^ Lai, Tin; Ramos, Fabio; Francis, Gilad (2019). "Equilibrio de exploración global y explotación de conectividad local con árboles desarticulados aleatorios de exploración rápida" . 2019 Congreso Internacional de Robótica y Automatización (ICRA) . Montreal, QC, Canadá: IEEE: 5537–5543. arXiv : 1810.03749 . doi : 10.1109 / ICRA.2019.8793618 . ISBN 978-1-5386-6027-0.

Enlaces externos [ editar ]

  • Medios relacionados con la exploración rápida de árboles aleatorios en Wikimedia Commons
  • Visualizador Java de RRT y RRT * incluido editor de mapas
  • Implementación en C ++ de RRT usando rutas de tiempo mínimo de Dubins