Planificación de rutas desde cualquier ángulo

Camino tenso

Un camino donde cada cambio de dirección se ajusta perfectamente a algún obstáculo. Para una cuadrícula uniforme, solo los caminos ajustados pueden ser óptimos.

Fuente única

Un problema de búsqueda de rutas que busca encontrar el camino más corto a todas las partes del grafo, partiendo de un vértice.

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* ^{[ 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 caminos dinámicos basados ​​en D* que utilizan interpolación durante la expansión de cada vértice y encuentran caminos casi óptimos a través de cuadrículas de costo regulares y no uniformes. Por lo tanto, Campo D* intenta resolver el problema de la región ponderada ^{[ 9 ]} y Campo D* 3D el problema tridimensional correspondiente.
  • Campo D* de multirresolución ^{[ 10 ]} – Extensión del campo D* para cuadrículas de multirresolución.
• Theta* ^{[ 6 ] [ 11 ]} - Utiliza el mismo bucle principal que A*, pero para cada expansión de un vértice${\displaystyle s}$, hay una comprobación de línea de visión entre${\displaystyle padre(s)}$y el sucesor de${\displaystyle s}$,${\displaystyle s'}$. Si hay línea de visión, el camino desde${\displaystyle padre(s)}$a${\displaystyle s'}$se utiliza ya que siempre será al menos tan corto como el camino desde${\displaystyle padre(s)}$a${\displaystyle s}$y${\displaystyle s}$a${\displaystyle s'}$. Este algoritmo funciona solo en cuadrículas de costo uniforme. ^{[ 6 ]} AP Theta* ^{[ 6 ] [ 11 ]} es una optimización de Theta* que utiliza propagación angular para disminuir el costo de realizar cálculos de línea de visión a O (1) .
  • Lazy Theta* ^{[ 12 ]} es otra optimización de Theta* que utiliza evaluación diferida para reducir el número de cálculos de línea de visión, retrasando dichos cálculos para cada nodo desde su exploración hasta su expansión. Es lo suficientemente potente como para funcionar en un espacio 3D.
  • Incremental Phi* ^{[ 13 ]} es una variante incremental y más eficiente de Theta* diseñada para entornos 2D desconocidos. ^{[ 2 ]}
  • Strict Theta* y Recursive Strict Theta* ^{[ 14 ]} mejoran Theta* al restringir el espacio de búsqueda a los caminos Taut introducidos por ANYA. Al igual que Theta*, este es un algoritmo que devuelve caminos casi óptimos.
• 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 caminos de cualquier ángulo por partes.
• ANYA ^{[ 16 ]} - Encuentra trayectorias óptimas en cualquier ángulo restringiendo el espacio de búsqueda a las trayectorias Taut (una trayectoria donde cada cambio de rumbo se ajusta perfectamente a algún obstáculo); considerando un intervalo de puntos como un nodo en lugar de un solo punto. Es 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 y líneas circulares discretas) para representar el frente de onda propagante en la cuadrícula. Para la planificación de trayectorias desde una única fuente en mapas prácticos, se ha demostrado que es más rápido que los métodos basados ​​en búsqueda en grafos. Existen implementaciones óptimas y con aritmética entera.

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

• El rendimiento de un enfoque de grafo de visibilidad puede mejorarse considerablemente mediante un enfoque disperso que solo considera aristas capaces de formar caminos tensos. Se sabe que una versión multinivel llamada ENLSVG es más rápida que ANYA, pero solo puede utilizarse con preprocesamiento. ^{[ 19 ]}
• PolyAnya generaliza ANYA para trabajar en mapas no cuadriculados con obstáculos poligonales. ^{[ 20 ]} Es rápido, no requiere preprocesamiento (a diferencia de ENLSVG) y es óptimo (a diferencia de RRT).
• De forma similar a la solución RRT que se analiza más adelante, a menudo es necesario tener en cuenta también las restricciones de dirección al pilotar un vehículo real. El algoritmo A* híbrido es una extensión de A* que considera dos dimensiones adicionales que representan el estado del vehículo, de modo que las trayectorias sean realmente posibles. Fue creado por Stanford Racing como parte del sistema de navegación de Junior, su vehículo participante en el DARPA Urban Challenge . ^{[ 21 ] Peterit et al. [ 22 ]} ofrecen una explicación más detallada.

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 de movimiento ) y/o se debe considerar el momento (lo que podría duplicar efectivamente 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 a la ruta óptima al encontrar rutas cada vez más cortas:

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

• Hoja de ruta probabilística