En 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 nodos nuevos se agregan y restan con frecuencia. ¿Presumiblemente usar D * sobre A * sería una mejor manera de detectar caminos en este entorno dinámico?

¿Qué tan sólido es D *? ¿Ha tenido alguna experiencia en el mundo real? como un algoritmo criptográfico: ¿D * se endurece por una gran cantidad de revisiones y pruebas por parte de colegas? ¿Usarías D * para este problema?

Answer 1

Según entiendo, la primera vez que ejecuta D * 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 se agregan nodos, A * recalcula TODA la ruta mientras D * simplemente vuelve a calcular los nodos inconsistentes la segunda vez en lugar de todo.

El algoritmo D * de Anthony Stentz (documento original original here) ha sido en gran parte obsoleto por los derivados de su trabajo. D * Lite y LPA * son los más comunes 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 de Field D * utilizando elementos de D * Lite en los rovers "Spirit" y "Opportunity" D * here). En febrero de 2007, se utilizó para navegar completamente por el rover mars de forma autónoma.

alt text http://asm.arc.nasa.gov/Gallery/images/generic/rover.jpg

Al parecer D * es realmente útil en el dominio de la robótica, porque los robots de a bordo sensores están constantemente re-evaluando los valores de borde. Eso lo haría bastante "probado en la batalla" en mi propia opinión.

De manera similar, encontré otro whitepaper que menciona el uso del algoritmo D * Lite en Mobile Gaming.

Voy a 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, así que definitivamente diría que es D * Lite. Si la NASA lo usa, podría apostar de forma segura que ha sido investigado a fondo.

Answer 2

He implementado el algoritmo D * y A *. Entonces, te aconsejo que, si tu mapa no tiene obstáculos dinámicos, debes implementar A *. De lo contrario, implemente D *. Por la razón principal es: En la primera búsqueda, D * calcula todos los nodos en el mapa, luego le muestra la ruta más corta, mientras que A * solo calcula un área limitada alrededor del objetivo y puntos de inicio en el mapa. Entonces, es mucho más rápido que D *. En ambiente dinámico, D * es más rápido y más eficiente que A *. Porque en el camino va el robot, si detecta un nuevo obstáculo, solo actualiza unos pocos nodos alrededor del obstáculo inesperado. Mientras, A * volverá a calcular todas las cosas.