Sur la recherche du chemin: description détaillée d'un profane de l'algorithme D *

Question

Le grand réseau (type graphique de petit monde) que je souhaite traiter est de nature dynamique, de nouveaux nœuds sont ajoutés et soustraits fréquemment. Vraisemblablement, utiliser D * sur A * serait un meilleur moyen de détecter les chemins dans cet environnement dynamique?

À quel point D * est-il solide? At-il eu une expérience du monde réel? comme un algorithme cryptographique - D * est-il durci par de nombreux examens et tests par les pairs? Voulez-vous utiliser D * pour résoudre ce problème?

Answer 1

Si je comprends bien, la première fois que vous exécutez D *, il trouve le même chemin que A * avec à peu près le même runtime. Cependant, lorsqu'un nœud change de valeur ou qu'il ajoute des nœuds, A * recalcule TOUT le chemin, D * recalcule simplement les nœuds incohérents la deuxième fois plutôt que le tout.

L'algorithme D * d'Anthony Stentz (livre blanc original ici ) a été en grande partie déconseillé pour les dérivés de son travail. D * Lite et LPA * sont les plus couramment rencontrés et sont beaucoup plus faciles à coder / implémenter.

En ce qui concerne l'expérience du monde réel, Joseph Carsten et Art Rankin du laboratoire de propulsion par réaction de la NASA ont installé une version de Field D * utilisant des éléments de D * Lite sur les moteurs de recherche "Spirit" de Mars. et " Opportunity " (diaporama des rovers utilisant D * ici ). En février 2007, il permettait de naviguer de manière autonome dans le rover mars.

texte de remplacement http://asm.arc.nasa.gov/ Galerie / images / generic / rover.jpg

Apparemment, D * est vraiment utile dans le domaine de la robotique car les capteurs embarqués des robots réévaluent constamment les valeurs de bord. Cela le rendrait joli & "testé au combat" à mon avis.

De même, j'ai trouvé un autre livre blanc qui mentionne l'utilisation du Algorithme D * Lite dans les jeux mobiles.

Je terminerai cette réponse en déclarant que je n’ai jamais implémenté D * auparavant, seulement A *. En raison de l’augmentation considérable de la complexité, je dirais que D * (ou D * Lite) ne devrait être utilisé que dans les cas où le graphique présente des changements importants et fréquents. Vous avez décrit votre situation comme étant similaire à celle-ci, je vous conseille donc de choisir D * Lite. Si la NASA l’utilise, vous pouvez parier qu’elle a fait l’objet d’une enquête approfondie.

Answer 2

J'ai mis en œuvre les algorithmes D * et A *. Je vous conseille donc de mettre en œuvre A * si votre carte ne présente pas d'obstacles dynamiques. Sinon, implémentez D *. Pour la raison principale est: Lors de la première recherche, D * calcule tous les nœuds de la carte, puis vous indique le chemin le plus court, tandis que A * calcule uniquement une zone limitée autour de l'objectif et des points de départ sur la carte. Donc, c'est beaucoup plus rapide que D *. En environnement dynamique, D * est plus rapide et plus efficace que A *. Parce que sur le chemin, le robot se rend, s'il détecte un nouvel obstacle, il ne met à jour que quelques nœuds autour de l'obstacle inattendu. Tandis que A * calculera à nouveau toutes choses.