Algoritmos de búsqueda de rutas para mapas continuos (por ejemplo, polígonos)
Trato de investigar diferentes algoritmos para un camino corto entre dos puntos en un plano con obstáculos poligonales. La gran mayoría de los algoritmos que encontré usan mapas discretos (mapa de cuadrícula, gráfico de visibilidad, hoja de ruta de Voronoi, etc.). Algunos libros (como "Elements of Robotics" de Ben-Ari o "Introduction to Autonomous Robots" de Nikolaus Correll) mencionan mapas continuos (por ejemplo, datos de polígonos sin procesar), pero no explican los algoritmos correspondientes. Reclaman ventajas de memoria o eficiencia para pocos y sencillos obstáculos, lo que me puede resultar muy interesante.
Creo que debería haber un enfoque inteligente que utilice el cálculo geométrico (por ejemplo, detección de intersecciones) y algún paradigma algorítmico (por ejemplo, bifurcación y límite de menor costo), pero no quiero reinventar mal la rueda.
¿Hay recursos para algunos algoritmos de ruta corta (est) que usan mapas continuos o palabras clave útiles para buscar?
Como se sugirió, trato de especificar algunos de los términos que utilicé:
Los mapas continuos (ver Fig. ) se refieren al almacenamiento de valores numéricos reales (continuos) de formas geométricas. Obstáculo/Triángulo I. se almacenaría como: A = (3,2), B=(7,5), C=(7,2).
Los mapas discretos (ver Fig. ) se refieren a la subdivisión en fragmentos (discretización, por ejemplo, como en un mapa de cuadrícula). Obstáculo/Triángulo I. ahora se almacenaría como índices de celda: (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) la búsqueda de rutas en mapas discretos a menudo se logra mediante algoritmos basados en gráficos como Dijkstra o A*.
El cálculo geométrico es solo un término vago que uso para las operaciones de geometría computacional que esperaría en un algoritmo de búsqueda de rutas para mapas continuos. (por ejemplo, traslación, distancia perpendicular, detección de intersección)
Respuestas
Para los "mapas continuos" como los llamaste, solo usa Dijkstra en todos tus vértices. La única diferencia es que debe verificar el recorte al calcular la distancia entre los nodos.
Otro término, que se usa con más frecuencia, para mi problema parece ser Euclidean Shortest Path(s) . La distinción entre algoritmos para mapas continuos y mapas discretos me parece un poco ambigua.
Sin embargo, lo más cercano que encontré a un algoritmo para un mapa continuo es el algoritmo de Mitchell para el problema continuo de Dijkstra (o método continuo de Dijkstra). Este algoritmo utiliza ondículas que se distribuyen uniformemente desde el punto de partida. Por “difracción” de las ondículas, alcanzan áreas a las que no se puede llegar directamente. Esto crea un mapa de ruta más corta que se puede utilizar para identificar la ruta euclidiana más corta a cualquier punto en el espacio de configuración continuo.
Para más ver:
- "Algoritmos exactos o aproximados de las rutas más cortas euclidianas" por F. Li y R. Klette
- animación agradable pero un poco defectuosa por Ivan Chen
- solicitud de Anton Kovsharov
Se puede argumentar que el mapa de ruta más corta creado es solo otra discretización del espacio de configuración continua. Sin embargo, supongo que el mapa de ruta más corta es solo un resultado que se puede obtener si el algoritmo se aplica a todo el espacio de configuración. Si solo se desea el camino más corto entre dos puntos, el algoritmo podría detenerse después de alcanzar el punto de destino. Sigo sin estar seguro de la clasificación de estos algoritmos, pero esto debería responder a mi pregunta.