Enfoques de un algoritmo de detección de ruta dinámica

Question

La implementación de Mi * funciona bien para mi entorno estático. Si ahora quisiera trabajar con un entorno dinámico, es decir, ciertos costos entre mis nodos cambian mientras estamos atravesando desde el principio hasta el final.

Según mi lectura hasta ahora, he encontrado el algoritmo LPA *, D * y D * Lite que podría ayudarme. Bueno, mi peor caso sería implementarlo todo y ver qué funciona mejor.

¿Se ha realizado alguna investigación para comparar las capacidades de estos algoritmos? Los documentos que he leído hasta ahora solo se enfocan en un solo algoritmo a la vez y dado que los entornos de sus experimentos son diferentes, es difícil hacer una comparación.

** Algunos antecedentes: Estoy usando C++ y mi entorno es una escena en 3D con mi gráfico de búsqueda representado mediante navmeshes.

Answer 1

Tal vez podría ayudarle a this paper, reactivas de deformación Planes de trabajo: Planificación de movimiento de múltiples robots en entornos dinámicos por Russell Gayle Avneesh Sud Ming Lin C Dinesh Manocha; El resumen es el siguiente:

Se presenta un nuevo algoritmo para planificación del movimiento de múltiples robots entre obstáculos dinámicos. Nuestro enfoque se basa en una nueva representación de la hoja de ruta que utiliza enlaces deformables y se retrae dinámicamente a para capturar la conectividad del espacio libre . Usamos Newtonian Physics y Ley de Hooke para actualizar la posición de los hitos y deformar los enlaces en respuesta al movimiento de otros robots y los obstáculos. En base a esta representación de hoja de ruta , describimos nuestros algoritmos de planificación que pueden calcular rutas sin colisiones para decenas de robots en entornos dinámicos complejos .

Se presenta un algoritmo que se basa físicamente, hoja de ruta adaptativa representación que se retrae y cambia su topología como una función del entorno dinámico. Iit se puede utilizar para planificar el movimiento de un solo robot o varios robots entre obstáculos dinámicos.

Answer 2

Ha pasado un tiempo desde que lo pidió, así que tal vez ya haya tenido tiempo de probarlos todos ... Pero para lo que vale, el documento D * -Lite (http://www.aaai.org/ Papers/AAAI/2002/AAAI02-072.pdf) tiene una sección al final, Resultados experimentales, que compara el rendimiento con LPA *, D * y A *.