Cualquier ángulo de planificación de ruta algoritmos son un subconjunto de pathfinding algoritmos de esa búsqueda de un camino entre dos puntos en el espacio y permitir que los giros de la ruta de acceso que tengan cualquier ángulo. El resultado es un camino que va directamente hacia la meta y tiene relativamente pocos giros. [1] Otros algoritmos de búsqueda de rutas , como A *, restringen las rutas a una cuadrícula, lo que produce rutas irregulares e indirectas.
Fondo
Los mapas del mundo real y muchos de los juegos tienen áreas abiertas que se atraviesan de manera más eficiente de manera directa. Los algoritmos tradicionales están mal equipados para resolver estos problemas:
- Un * con un gráfico de cuadrícula discreto conectado a 8 es muy rápido, pero solo mira las rutas en incrementos de 45 grados. Se puede usar un paso de post-suavizado rápido para enderezar (así acortar) la salida irregular, pero no se garantiza que el resultado sea óptimo ya que no analiza todas las rutas posibles. (Más específicamente, no pueden cambiar qué lado de una celda bloqueada se atraviesa). 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. Sin embargo, el rendimiento es problemático ya que el número de aristas en un gráfico con vértices es .
Un algoritmo de planificación de trayectoria en cualquier ángulo tiene como objetivo producir soluciones óptimas o casi óptimas con menos tiempo que el enfoque de gráfico de visibilidad básico. Los algoritmos rápidos de cualquier ángulo toman aproximadamente el mismo tiempo que una solución basada en cuadrículas para calcular.
Definiciones
- Camino tenso
- Un camino donde cada cambio de rumbo en el camino “envuelve” con fuerza algún obstáculo. Para una cuadrícula uniforme, solo los caminos tensos pueden ser óptimos.
- Única fuente
- 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 ahora, se han desarrollado cinco algoritmos principales de planificación de trayectorias en cualquier ángulo que se basan en el algoritmo de búsqueda heurística A * [2] , todos los cuales propagan información a lo largo de los bordes de la cuadrícula:
- El campo D * [3] [4] (FD * [5] ) y 3D Campo D * [6] [7] - algoritmos pathfinding dinámico basado en D * que el uso de interpolación durante cada expansión vértice y encontrar casi óptimas caminos a través de ordinario , cuadrículas de costos no uniformes. Por tanto, el campo D * intenta resolver el problema de la región ponderada [8] y el campo 3D D * el problema tridimensional correspondiente.
- Campo D * de resolución múltiple [9] : ampliación del campo D * para cuadrículas de resolución múltiple.
- Theta * [5] [10] : usa el mismo bucle principal que A *, pero para cada expansión de un vértice, hay una verificación de la línea de visión entre y el sucesor de , . Si hay línea de visión, el camino desde a se utiliza ya que siempre será al menos tan corto como el camino desde a y a . Este algoritmo funciona solo en cuadrículas de costo uniforme. [5] AP Theta * [5] [10] es una optimización de Theta * que usa la propagación del ángulo para disminuir el costo de realizar cálculos de línea de visión a O (1) , y Lazy Theta * [11] es otro optimización de Theta * que utiliza la evaluación diferida para reducir el número de cálculos de línea de visión retrasando los cálculos de línea de visión para cada nodo desde que se explora hasta que se expande. Incremental Phi * [12] es una variante incremental y más eficiente de Theta * diseñada para entornos 2D desconocidos. [13]
- Strict Theta * y Recursive Strict Theta * [14] mejora Theta * al restringir el espacio de búsqueda a Taut Paths introducidos por ANYA. Al igual que Theta *, este es un algoritmo que devuelve rutas casi óptimas.
- Bloque A * [15] : genera una base de datos de distancia local que contiene todos los caminos posibles en una pequeña sección de la cuadrícula. Hace referencia a esta base de datos para encontrar rápidamente trayectorias en cualquier ángulo por partes.
- ANYA [16] - Encuentra rutas óptimas en cualquier ángulo al restringir el espacio de búsqueda a las rutas Tensadas (una ruta donde cada cambio de rumbo en la ruta “envuelve” firmemente algún obstáculo); mirando un intervalo de puntos como un nodo en lugar de un solo punto. La técnica óptima online más rápida conocida.
- CWave [17] [18] : utiliza primitivas geométricas (líneas y arcos circulares discretos) 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 demuestra que es más rápido que los métodos basados en la búsqueda de gráficos. Hay implementaciones óptimas y aritméticas enteras.
También hay un algoritmo basado en A * distinto de la familia anterior:
- El rendimiento de un enfoque de gráfico de visibilidad se puede mejorar en gran medida mediante un enfoque disperso que solo considera los bordes capaces de formar trayectorias 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]
- De manera similar a la solución RRT que se analiza a continuación, a menudo también es necesario tener en cuenta las limitaciones de la 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, por lo que las rutas son realmente posibles. Fue creado por Stanford Racing como parte del sistema de navegación para Junior, su entrada al DARPA Urban Challenge . [20] Peterit, et al. Han escrito una discusión más detallada. [21]
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 implica muchos grados de libertad que deben tenerse en cuenta (ver Planificación de movimiento ), y / o es necesario considerar el impulso (que podría efectivamente duplicar el número de dimensiones del espacio de búsqueda; este espacio más grande que incluye el impulso se conoce como el espacio de fase ), se han desarrollado variantes del árbol aleatorio de exploración rápida (RRT) [22] que (casi con seguridad) convergen hacia la ruta óptima encontrar caminos cada vez más cortos:
- Gráfico aleatorio de exploración rápida (RRG) y RRT * [23] [24]
- RRT informado * [25] 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 .
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 donde se desean rutas más óptimas. El híbrido A *, por ejemplo, se utilizó como entrada a un desafío DARPA. [20] Las propiedades de reconocimiento de la dirección de algunos ejemplos también se traducen en vehículos autónomos.
Ver también
- Planificación de movimiento
Referencias
- ^ Tansel Uras y Sven Koenig. Una comparación empírica de algoritmos de planificación de trayectorias en cualquier ángulo . Actas del Octavo Simposio Internacional sobre Búsqueda Combinatoria.
- ^ P. Hart, N. Nilsson y B. Raphael, Una base formal para la determinación heurística de rutas de costo mínimo , IEEE Trans. Syst. Ciencia y cibernética , SSC-4 (2), 100-107, 1968.
- ^ D. Ferguson y A. Stentz. Campo D *: un planificador y replanificador de rutas basado en interpolación . Actas del Simposio Internacional sobre Investigación en Robótica , 2005.
- ^ 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 ", tecnología. informe CMU-RI-TR-05-19, Instituto de Robótica, Universidad Carnegie Mellon, junio de 2005
- ^ a b c d A. Nash, K. Daniel, S. Koenig y A. Felner. Theta *: Planificación de rutas en cualquier ángulo en cuadrículas . En Actas de la Conferencia AAAI sobre Inteligencia Artificial , páginas 1177–1183, 2007.
- ^ Carsten, Joseph; Ferguson, Dave; Stentz, Anthony (9 al 15 de octubre de 2006). "3D Field D *: planificación de ruta mejorada y replanificación en tres dimensiones" (PDF) . Robots y sistemas inteligentes, 2006 Conferencia internacional IEEE / RSJ 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 .
- ^ Carsten, J .; Ferguson, D .; Stentz, A. (2006). "3D campo D: planificación de ruta mejorada y replanificación en tres dimensiones". 2006 Conferencia Internacional IEEE / RSJ sobre Robots y Sistemas Inteligentes . pag. 3381. CiteSeerX 10.1.1.188.150 . doi : 10.1109 / IROS.2006.282516 . ISBN 978-1-4244-0258-8.
- ^ Mitchell, JSB; Papadimitriou, CH (1991). "El problema de la región ponderada: encontrar caminos más cortos a través de una subdivisión plana ponderada". Revista de la ACM . 38 : 18–73. doi : 10.1145 / 102782.102784 . hdl : 1813/8768 .
- ^ Dave Ferguson y Anthony Stentz. Campo D * de resolución múltiple . Actas de la Conferencia Internacional sobre Inteligencia, 2006.
- ^ a b Daniel, K .; Nash, A .; Koenig, S .; Felner, A. (2010). "Theta *: Planificación de rutas en cualquier ángulo en cuadrículas" (PDF) . Revista de Investigación en Inteligencia Artificial . 39 : 533–579. doi : 10.1613 / jair.2994 .
- ^ Nash, A .; Koenig, S .; Tovey, C. (2010). "Lazy Theta *: planificación de ruta de cualquier ángulo y análisis de longitud de ruta en 3D" (PDF) . Actas de la Conferencia AAAI sobre Inteligencia Artificial (AAAI) .
- ^ Nash, A .; Koenig, S .; Likhachev, M. (2009). "Incremental Phi *: Planificación incremental de ruta de cualquier ángulo en cuadrículas" (PDF) . Actas de la Conferencia Internacional Conjunta sobre Inteligencia Artificial (IJCAI) : 1824–1830.
- ^ A. Nash. Planificación de trayectoria en cualquier ángulo . Tesis doctoral, Departamento de Ciencias de la Computación, Universidad del Sur de California, Los Ángeles (California), 2012.
- ^ Shunhao Oh, Hon Wai Leong, 2016. Strict Theta *: Planificación de trayectorias de movimiento más cortas mediante trayectorias tensas. En Actas de la XXVI Conferencia Internacional sobre Planificación y Programación Automatizados. https://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13049
- ^ P. Yap, N. Burch, R. Holte y J. Schaeffer, Bloque A *: búsqueda basada en bases de datos con aplicaciones en la planificación de rutas en cualquier ángulo . Actas de la XXV Conferencia AAAI sobre Inteligencia Artificial, 2011.
- ^ Daniel Harabor y Alban Grastien. Un algoritmo óptimo de búsqueda de caminos en cualquier ángulo . Actas de la Vigésima Tercera Conferencia Internacional sobre Planificación y Programación Automatizados.
- ^ Sinyukov, Dmitry A .; Padir, Taskin (mayo-junio de 2017). "CWave: planificación de ruta de cualquier ángulo de fuente única de alto rendimiento en una cuadrícula". Actas de la Conferencia Internacional IEEE 2017 sobre Robótica y Automatización (ICRA) . 2017 IEEE International Conference on Robotics and Automation (ICRA). Singapur: IEEE . págs. 6190–6197. doi : 10.1109 / ICRA.2017.7989733 .
- ^ Sinyukov, Dmitry A .; Padir, Taskin (2020). "CWave: teoría y práctica de un algoritmo de planificación de ruta de cualquier ángulo de fuente única rápida". Robotica . Prensa de la Universidad de Cambridge. 38 (2): 207–234. doi : 10.1017 / S0263574719000560 .
- ^ Oh, Shunhao; Leong, Hon Wai (5 de junio de 2017). "Gráficos de visibilidad dispersa de nivel N de borde: búsqueda de caminos rápida y óptima en cualquier ángulo utilizando caminos jerárquicos tensos" . Décimo Simposio Anual de Búsqueda Combinatoria .
- ^ a b Junior: La entrada de Stanford en el Urban Challenge
- ^ 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º Congreso Alemán de Robótica : 1–6.
- ^ 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 (TR 98-11).
- ^ 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 ].
- ^ 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 ].
- ^ Gammell, Jonathan D .; Srinivasa, Siddhartha S .; Barfoot, Timothy D. (2014). "RRT informado *: planificación de ruta basada en muestreo óptimo 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.
enlaces externos
- Lazy Theta *: planificación de ruta más rápida en cualquier ángulo
- A. Nash y S. Koenig. Planificación de trayectoria en cualquier ángulo . Revista de inteligencia artificial , 34, (4), 85-107, 2013.
- Any Angle Pathfinding , el código de demostración de código abierto de Shunhao Oh