Planificación de rutas en cualquier ángulo

Algoritmo para encontrar caminos euclidianos más cortos

La ruta encontrada por A* en una cuadrícula octil frente a la ruta más corta entre los nodos de inicio y de destino.

Los algoritmos de planificación de rutas con cualquier ángulo son algoritmos de búsqueda de rutas que buscan una ruta euclidiana más corta entre dos puntos en un mapa de cuadrícula , permitiendo que los giros en la ruta tengan cualquier ángulo. El resultado es una ruta que atraviesa directamente áreas abiertas y tiene relativamente pocos giros. ^[1] Los algoritmos de búsqueda de rutas más tradicionales, como A* , carecen de rendimiento o producen rutas indirectas irregulares.

Fondo

Los mapas del mundo real y de muchos juegos tienen áreas abiertas que se recorren de manera más eficiente de manera directa. Los algoritmos tradicionales no están preparados para resolver estos problemas:

• A* con un gráfico de cuadrícula discreto conectado en 8 direcciones (2D; 26 para el gráfico cúbico triple en 3D) es muy rápido, pero solo observa rutas en incrementos de 45 grados. Este comportamiento proporciona, en promedio, un 8 % más de longitud de ruta en 2D y un 13 % en 3D. ^{[2] : 60, 69} Se puede utilizar un paso rápido de suavizado posterior para enderezar (y, por lo tanto, acortar) la salida irregular, pero no se garantiza que el resultado sea óptimo, ya que no observa todas las rutas posibles. (Más específicamente, no pueden cambiar qué lado de una celda bloqueada se recorre). La ventaja es que se aplicarán todas las optimizaciones de la cuadrícula A*, como la búsqueda de puntos de salto .
• Se puede buscar un gráfico de visibilidad con todos los puntos de la cuadrícula con A* para obtener la solución óptima en el espacio 2D. Sin embargo, el rendimiento es problemático ya que el número de aristas en un gráfico con vértices es . Un gráfico de este tipo no siempre proporciona una solución óptima en el espacio 3D. ^[2] ${\displaystyle V}$ ${\displaystyle O(V^{2})}$

Un algoritmo de planificación de rutas de cualquier ángulo tiene como objetivo producir soluciones óptimas o casi óptimas y requiere menos tiempo que el enfoque básico de gráficos de visibilidad. Los algoritmos rápidos de cualquier ángulo requieren aproximadamente el mismo tiempo para calcularse que una solución basada en cuadrícula.

Definiciones

Camino tenso

Un camino en el que cada cambio de dirección del mismo “envuelve” firmemente algún obstáculo. Para una cuadrícula uniforme, solo los caminos tensos pueden ser óptimos.

De fuente única

Un problema de búsqueda de ruta que busca encontrar la ruta más corta a todas las partes del gráfico, comenzando desde un vértice.

Algoritmos

Basado en A*

Hasta el momento, se han desarrollado cinco algoritmos principales de planificación de rutas de cualquier ángulo que se basan en el algoritmo de búsqueda heurística A* ^{[3] , todos los cuales propagan información a lo largo de los bordes de la cuadrícula:}

• Campo D* ^{[4] [5]} (FD* ^[6] ) y Campo D* 3D ^{[7] [8]} - Algoritmos de búsqueda de rutas dinámicas basados ​​en D* que utilizan interpolación durante cada expansión de vértice y encuentran rutas casi óptimas a través de cuadrículas de costo regulares y no uniformes. Por lo tanto, el Campo D* intenta resolver el problema de la región ponderada ^[9] y el Campo D* 3D el problema tridimensional correspondiente.
  • Campo multi-resolución D* ^[10] – Extensión del Campo D* para cuadrículas multi-resolución.
• Theta* ^{[6] [11]} - Utiliza el mismo bucle principal que A*, pero para cada expansión de un vértice , hay una comprobación de línea de visión entre y el sucesor de , . Si hay línea de visión, se utiliza la ruta desde hasta ya que siempre será al menos tan corta como la ruta desde hasta y hasta . Este algoritmo funciona solo en cuadrículas de coste uniforme. ^[6] AP Theta* ^{[6] [11]} es una optimización de Theta* que utiliza la propagación angular para reducir el coste de realizar cálculos de línea de visión a O (1) . ${\displaystyle s}$ ${\displaystyle parent(s)}$ ${\displaystyle s}$ ${\displaystyle s'}$ ${\displaystyle parent(s)}$ ${\displaystyle s'}$ ${\displaystyle parent(s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s'}$
  • Lazy Theta* ^[12] es otra optimización de Theta* que utiliza una evaluación diferida para reducir la cantidad de cálculos de línea de visión al retrasar los cálculos de línea de visión para cada nodo desde el momento en que se explora hasta el momento en que se expande. Es lo suficientemente capaz como para ejecutarse en un espacio 3D.
  • Incremental Phi* ^[13] es una variante incremental y más eficiente de Theta* diseñada para entornos 2D desconocidos. ^[2]
  • Theta* estricto y Theta* estricto recursivo ^[14] mejora Theta* al restringir el espacio de búsqueda a las rutas tensas introducidas por ANYA. Al igual que Theta*, este es un algoritmo que devuelve rutas casi óptimas.
• Bloque A* ^[15] : genera una base de datos de distancias local que contiene todas las rutas posibles en una pequeña sección de la cuadrícula. Hace referencia a esta base de datos para encontrar rápidamente rutas de cualquier ángulo por partes.
• ANYA ^[16] - Encuentra rutas óptimas en cualquier ángulo restringiendo el espacio de búsqueda a las rutas tensas (una ruta en la que cada cambio de dirección en la ruta "envuelve" firmemente algún obstáculo); considerando un intervalo de puntos como un nodo en lugar de un único punto. La técnica óptima en línea más rápida conocida. Este algoritmo está restringido a cuadrículas 2D.
• CWave ^{[17] [18]} - Utiliza primitivas geométricas (arcos circulares y líneas discretas) para representar el frente de onda que se propaga en la cuadrícula. Para la planificación de rutas de una sola fuente en mapas prácticos, se ha demostrado que es más rápido que los métodos basados ​​en búsqueda de gráficos. Existen implementaciones óptimas y aritméticas de números enteros.

También existen algoritmos basados ​​en A* distintos de la familia anterior:

• El rendimiento de un enfoque de gráfico de visibilidad se puede mejorar en gran medida con un enfoque disperso que solo considere los bordes capaces de formar rutas tensas. Se sabe que una versión de varios niveles llamada ENLSVG es más rápida que ANYA, pero solo se puede utilizar con preprocesamiento. ^[19]
• PolyAnya generaliza ANYA para trabajar en mapas sin cuadrícula con obstáculos poligonales. ^[20] Es rápido, no requiere preprocesamiento (a diferencia de ENLSVG) y es óptimo (a diferencia de RRT).
• De manera similar a la solución RRT que se analiza a continuación, a menudo es necesario tener en cuenta también las limitaciones de dirección al pilotar un vehículo real. Hybrid A* es una extensión de A* que considera dos dimensiones adicionales que representan el estado del vehículo, de modo que las rutas sean realmente posibles. Fue creado por Stanford Racing como parte del sistema de navegación para Junior, su propuesta para el DARPA Urban Challenge . ^[21] Peterit et al. han escrito un análisis más detallado. ^[22]

Basado en RRT

Además, para la búsqueda en espacios de búsqueda de alta dimensión, como cuando el espacio de configuración del sistema involucra muchos grados de libertad que deben considerarse (ver Planificación del movimiento ), y/o debe considerarse el momento (lo que podría efectivamente duplicar el número de dimensiones del espacio de búsqueda; este espacio más grande que incluye el momento se conoce como el espacio de fase ), se han desarrollado variantes del árbol aleatorio de exploración rápida (RRT) ^[23] que (casi con seguridad) convergen al camino óptimo al encontrar cada vez más caminos más cortos:

• Gráfico aleatorio de exploración rápida (RRG) y RRT* ^{[24] [25]}
• El RRT* informado ^[26] mejora la velocidad de convergencia del RRT* al introducir una heurística, similar a la forma en que A* mejora el algoritmo de Dijkstra .

Otros algoritmos

• Hoja de ruta probabilística

Aplicaciones

La planificación de rutas en cualquier ángulo es útil para la navegación de robots y los juegos de estrategia en tiempo real en los que se desean rutas más óptimas. Por ejemplo, el híbrido A* se utilizó como propuesta para un concurso de la DARPA. ^[21] Las propiedades de conciencia de dirección de algunos ejemplos también se trasladan a los coches autónomos.

Véase también

• Planificación del movimiento

Referencias

1. Tansel Uras y Sven Koenig. Una comparación empírica de algoritmos de planificación de rutas de cualquier ángulo. Actas del octavo simposio internacional sobre búsqueda combinatoria.
2. A. Nash. Planificación de trayectorias desde cualquier ángulo. Tesis doctoral, Departamento de Ciencias de la Computación, Universidad del Sur de California, Los Ángeles (California), 2012.
3. P. Hart, N. Nilsson y B. Raphael, Una base formal para la determinación heurística de trayectorias de costo mínimo, IEEE Trans. Syst. Science and Cybernetics , SSC-4(2), 100-107, 1968.
4. D. Ferguson y A. Stentz. Campo D*: un planificador y replanificador de rutas basado en interpolación. Actas del Simposio Internacional sobre Investigación Robótica , 2005.
5. David Ferguson y Anthony (Tony) Stentz, "El algoritmo Field D* para mejorar la planificación y replanificación de rutas en entornos de costos uniformes y no uniformes", informe técnico CMU-RI-TR-05-19, Instituto de Robótica, Universidad Carnegie Mellon, junio de 2005
6. A. Nash, K. Daniel, S. Koenig y A. Felner. Theta*: Planificación de trayectorias con cualquier ángulo en cuadrículas. En Actas de la Conferencia AAAI sobre Inteligencia Artificial , páginas 1177–1183, 2007.
7. Carsten, Joseph; Ferguson, Dave; Stentz, Anthony (9–15 de octubre de 2006). "3D Field D*: Improved Path Planning and Replanning in Three Dimensions" (PDF) . Robots y sistemas inteligentes, Conferencia internacional IEEE/RSJ de 2006 sobre . Actas de la Conferencia internacional IEEE/RSJ de 2006 sobre robots y sistemas inteligentes. Pekín, China: IEEE . págs. 3381–3386. doi :10.1109/IROS.2006.282516 . Consultado el 7 de noviembre de 2014 .
8. Carsten, J.; Ferguson, D.; Stentz, A. (2006). "Campo 3D D: Planificación y replanificación de rutas mejoradas en tres dimensiones". Conferencia internacional IEEE/RSJ de 2006 sobre robots y sistemas inteligentes . pág. 3381. CiteSeerX 10.1.1.188.150 . doi :10.1109/IROS.2006.282516. ISBN .  978-1-4244-0258-8.S2CID 1845942  .
9. Mitchell, JSB; Papadimitriou, CH (1991). "El problema de la región ponderada: Encontrar los caminos más cortos a través de una subdivisión planar ponderada". Revista de la ACM . 38 : 18–73. doi :10.1145/102782.102784. hdl : 1813/8768 . S2CID  12673773.
10. Dave Ferguson y Anthony Stentz. Campo D* de resolución múltiple. Actas de la Conferencia Internacional sobre Inteligencia, 2006.
11. Daniel, K.; Nash, A.; Koenig, S.; Felner, A. (2010). "Theta*: Planificación de rutas de cualquier ángulo en cuadrículas" (PDF) . Revista de investigación en inteligencia artificial . 39 : 533–579. doi : 10.1613/jair.2994 .
12. Nash, A.; Koenig, S.; Tovey, C. (2010). "Lazy Theta*: Planificación de rutas de cualquier ángulo y análisis de longitud de ruta en 3D" (PDF) . Actas de la Conferencia AAAI sobre Inteligencia Artificial . 24 : 147–154. doi :10.1609/aaai.v24i1.7566. S2CID  3754577.
13. Nash, A.; Koenig, S.; Likhachev, M. (2009). "Incremental Phi*: Incremental Any-Angle Path Planning on Grids" (PDF) . Actas de la Conferencia Conjunta Internacional sobre Inteligencia Artificial (IJCAI) : 1824–1830.
14. Shunhao Oh, Hon Wai Leong, 2016. Theta estricta*: planificación de trayectorias de movimiento más cortas utilizando trayectorias tensas. En las Actas de la vigésimo sexta conferencia internacional sobre planificación y programación automatizadas. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049
15. P. Yap, N. Burch, R. Holte y J. Schaeffer, Bloque A*: Búsqueda basada en bases de datos con aplicaciones en planificación de rutas desde cualquier ángulo. Actas de la vigésimo quinta conferencia de la AAAI sobre inteligencia artificial, 2011.
16. Daniel Harabor y Alban Grastien. Un algoritmo óptimo de búsqueda de rutas en cualquier ángulo. Actas de la vigésimo tercera conferencia internacional sobre planificación y programación automatizadas.
17. Sinyukov, Dmitry A.; Padir, Taskin (mayo-junio de 2017). "CWave: Planificación de rutas de alto rendimiento de fuente única y cualquier ángulo en una cuadrícula". Actas de la Conferencia Internacional IEEE de 2017 sobre Robótica y Automatización (ICRA) . Conferencia Internacional IEEE de 2017 sobre Robótica y Automatización (ICRA). Singapur: IEEE . págs. 6190–6197. doi :10.1109/ICRA.2017.7989733.
18. Sinyukov, Dmitry A.; Padir, Taskin (2020). "CWave: teoría y práctica de un algoritmo rápido de planificación de rutas de cualquier ángulo y con una sola fuente". Robotica . 38 (2). Cambridge University Press: 207–234. doi :10.1017/S0263574719000560. S2CID  182189674.
19. Oh, Shunhao; Leong, Hon Wai (5 de junio de 2017). "Gráficos de visibilidad dispersa de nivel N de borde: búsqueda de rutas rápida y óptima en cualquier ángulo mediante rutas tensas jerárquicas". Décimo simposio anual sobre búsqueda combinatoria . arXiv : 1702.01524 .
20. Cui, Michael; Harabor, Daniel D.; Grastien, Alban (2017). "Búsqueda de rutas sin compromisos en una malla de navegación". Actas de la vigésimo sexta conferencia conjunta internacional sobre inteligencia artificial : 496–502.
21. Junior: La entrada de Stanford en el desafío urbano
22. Petereit, Janko; Emter, Thomas; Frey, Christian W.; Kopfstedt, Thomas; Beutel, Andreas (mayo de 2012). "Aplicación de Hybrid A* a un robot móvil autónomo para la planificación de rutas en entornos exteriores no estructurados". ROBOTIK 2012; 7.ª Conferencia alemana sobre robótica : 1–6.
23. LaValle, Steven M. (octubre de 1998). "Árboles aleatorios de exploración rápida: una nueva herramienta para la planificación de rutas" (PDF) . Informe técnico (TR 98–11).
24. Karaman, Sertac; Frazzoli, Emilio (3 de mayo de 2010). "Algoritmos basados ​​en muestreo incremental para la planificación óptima del movimiento". arXiv : 1005.0416 [cs.RO].
25. Karaman, Sertac; Frazzoli, Emilio (5 de mayo de 2011). "Algoritmos basados ​​en muestreo para la planificación óptima del movimiento". arXiv : 1105.1186 [cs.RO].
26. Gammell, Jonathan D.; Srinivasa, Siddhartha S.; Barfoot, Timothy D. (2014). "RRT informado*: planificación de rutas basada en muestreo óptimo enfocada a través del muestreo directo de una heurística elipsoidal admisible". Conferencia internacional IEEE/RSJ de 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.

Enlaces externos

• Lazy Theta*: planificación de rutas más rápida desde cualquier ángulo
• A. Nash y S. Koenig. Planificación de rutas desde cualquier ángulo. Revista de Inteligencia Artificial , 34, (4), 85-107, 2013.
• Búsqueda de rutas en cualquier ángulo, código de demostración de código abierto de Shunhao Oh