Búsqueda de ruta: una descripción detallada para un lego del algoritmo D *

Question

La red grande (del tipo de gráfico de mundo pequeño) que deseo tratar es de naturaleza dinámica, los nuevos nodos se agregan y se restan con frecuencia. ¿Supongo que usar D * sobre A * sería una mejor manera de detectar rutas en este entorno dinámico?

¿Qué tan sólido es D *? ¿Ha tenido alguna experiencia del mundo real? como un algoritmo criptográfico: ¿está D * reforzado por un montón de revisiones y pruebas por pares? ¿Usaría D * para este problema?

Answer 1

Según tengo entendido, la primera vez que ejecutas D * se encuentra la misma ruta que A * con casi el mismo tiempo de ejecución. Sin embargo, cuando un nodo cambia su valor de borde o los nodos se agregan, A * vuelve a calcular TODA la ruta, mientras que D * simplemente vuelve a calcular los nodos inconsistentes la segunda vez en lugar de todo.

El algoritmo D * de Anthony Stentz (documento técnico original aquí ) ha sido en gran parte desaprobado por los derivados de su trabajo. D * Lite y LPA * son los que se encuentran más comúnmente y son mucho más fáciles de codificar / implementar.

En cuanto a la experiencia del mundo real, Joseph Carsten y Art Rankin, del Laboratorio de Propulsión a Chorro de la NASA, instalaron una versión del Campo D * con elementos de D * Lite en los rovers de Mars " Spirit " y " Oportunidad " (pase de diapositivas de rovers utilizando D * aquí ). En febrero de 2007, se utilizó para navegar de forma autónoma por completo.

texto alternativo http://asm.arc.nasa.gov/ Galería / images / generic / rover.jpg

Al parecer, D * es realmente útil en el dominio de la robótica porque los robots a bordo de los sensores están reevaluando constantemente los valores de borde. Eso lo haría bonito "batalla probada" en mi opinion

Del mismo modo, encontré otro whitepaper que menciona el uso del Algoritmo D * Lite en juegos móviles.

Terminaré esta respuesta diciendo que nunca he implementado D * antes, solo A *. Debido al aumento significativo de la complejidad, diría que D * (o D * Lite) solo se debe usar en los casos en que haya cambios significativos y frecuentes en el gráfico. Usted describió su situación como similar a esa, así que diría que definitivamente iría por D * Lite. Si la NASA lo usa, puedes apostar con seguridad que se ha investigado exhaustivamente.

Answer 2

He implementado los algoritmos D * y A *. Por lo tanto, le aconsejo que, si su mapa no tiene obstáculos dinámicos, debe implementar A *. Si no, implementa D *. Por la razón principal es: En la primera búsqueda, D * calcula todos los nodos en el mapa, luego muestra la ruta más corta, mientras que A * solo calcula un área limitada alrededor de los puntos de inicio y meta en el mapa. Por lo tanto, es mucho más rápido que D *. En un entorno dinámico, D * es más rápido y más eficiente que A *. Porque en el camino del robot, si detecta un nuevo obstáculo, solo actualiza algunos nodos alrededor del obstáculo inesperado. Mientras, A * volverá a calcular todas las cosas.