Algorithme D*
L'algorithme D* (qui se prononce D étoile ou D star à l'anglaise) recouvre un ensemble de trois algorithmes de recherche incrémentale heuristique suivants :
- L'algorithme original D* (original D*)[1], de Anthony Stentz, est un algorithme de recherche incrémentale informé.
- L'algorithme Focused D* (ou D* focalisé)[2] est un algoritme de recherche incrémentale informé heuristique de Anthony Stentz qui combine des idées de A*[3] et de l'algorithme original D*. L'algorithme D* focalisé résulte d'un développement plus poussé de l'algorithme D* d'origine.
- L'algorithme D* Lite (ou D* léger)[4] est un algorithme de recherche incremental heuristique de Sven Koenig et Maxim Likhachev qui s'appuie sur LPA*[5], un algorithme de recherche incrementale heuristique qui combine les idées de A* et Dynamic SWSF-FP[6].
Les trois algorithmes résolvent les mêmes problèmes de planification de chemins à base d'hypothèses, incluant la planification avec l'hypothèse d'espace libre[7], dans laquelle un robot doit naviguer aux coordonnées d'un but donné en terrain inconnu. Il doit faire des hypothèses sur la partie inconnue du terrain (par exemple: qu'il ne contient pas d'obstacles) et trouver un chemin le plus court depuis ses coordonnées courantes vers les coordonnées du but selon ces hypothèses. Le robot suit alors le chemin. Lorsqu'il observe une nouvelle information cartographique (telle que des obstacles précédemment inconnus), il ajoute l'information à sa carte et, si nécessaire, replanifie un nouveau chemin le plus court depuis ses coordonnées courantes vers les coordonnées du but donné. Il répète le processus jusqu'à ce qu'il atteigne les coordonnées du but ou qu'il détermine que les coordonnées du but n'ont pas été atteintes. En traversant un terrain inconnu, de nouveaux obstacles peuvent fréquemment être découverts, donc cette replanification doit être rapide. Les algorithmes de recherche incrémentale heuristique accélèrent la recherche pour des séquences de problèmes de recherche similaires en utilisant l'expérience acquise sur des problèmes précédents pour résoudre plus rapidement le problème courant. Sous l'hypothèse que les coordonnées du but ne changent pas, tous les trois algoritmes de recherche sont plus efficients que des recherches A* répétées.
D* et ses variantes ont été largement utilisés pour la navigation de robots mobiles et de véhicules autonomes. Les systèmes actuels sont typiquement basés sur D* Lite plutôt que sur le D* original ou Focused D*. En fait, même le laboratoire de Stentz utilise D* Lite plutôt que D* dans certaines implémentations[8]. De tels systèmes de navigation incluent un système prototype testé sur les rovers de Mars Opportunity et Spirit et le système de navigation qui a remporté le DARPA Urban Challenge, tous deux développés à l'Université Carnegie Mellon.
L'algorithme D* original a été présenté par Anthony Stentz en 1994. Le nom D* vient du terme "Dynamic A*", parce que l'algorithme se comporte comme A* sauf que le coût des arcs change au fur et à mesure que l'algorithme s'exécute.
Fonctionnement
Le fonctionnement de base de D* est décrit ci-dessous.
Comme l'algorithme de Dijkstra et A*, D* maintient une liste des nœuds à évaluer, appelée la liste "OUVERTE". Les nœuds sont marqués comme ayant un des différents états suivants :
- NOUVEAU, signifiant qu'il n'a jamais été placé dans la liste OUVERTE,
- OUVERT, signifiant qu'il est actuellement dans la liste OUVERTE,
- FERME, signifiant qu'il n'est plus dans la liste OUVERTE,
- ELEVE, indiquant que son coût est plus grand que la dernière fois qu'il a été dans la liste OUVERTE,
- BAISSE, indiquant que son coût est plus bas que la dernière fois qu'il a été dans la liste OUVERTE.
Expansion
L'algorithme travaille en sélectionnant itérativement un nœud de la liste OUVERTE et en l'évaluant. Il propage les changements du nœud à tous les nœuds du voisinage et les place dans la liste OUVERTE. Ce processus de propagation est appelé "expansion". Contrairement au A* canonique, qui suit le chemin du début à la fin, D* commence par chercher en arrière depuis le nœud but. Chaque nœud expansé a un rétro-pointeur qui référence le nœud suivant menant à la cible, et chaque nœud connaît le coût exact jusqu'à la cible. Lorsque le nœud de départ est le prochain nœud à être expansé, l'algorithme se termine, et le chemin jusqu'au but peut être trouvé en suivant simplement les rétro-pointeurs.
Expansion en cours. Le nœud d'arrivée (jaune) est au milieu du rang de points le plus haut, le nœud de départ est au milieu du rang de points le plus bas. La couleur rouge matérialise un obstacle; le dégradé noir/bleu représente les noeuds expensés (la luminosité indique le coût). La couleur verte indique les nœuds qui sont expansés.
L'expansion s'est terminée. Le chemin est indiqué en cyan.
Gestion des obstacles
Lorsqu'un obstruction est détectée le long du chemin prévu, tous les points qui sont affectés sont placés de nouveau dans la liste OUVERTE, cette fois marqués ELEVE. Avant qu'un nœud ELEVE ne voit son coût s'élever, cependant, l'algorithme vérifie ses voisins et examine s'il peut réduire le coût du nœud. Si ce n'est pas le cas, l'état ELEVE est propagé à tous les descendants du nœud, c'est-à -dire les nœuds qui ont des rétro-pointeurs vers celui-ci. Ces nœuds sont alors évalués, et l'état ELEVE est transmis, formant une vague. Lorsque le coût d'un nœud ELEVE peut être réduit, ses rétro-pointeurs sont mis à jour, et il transmet l'état BAISSE à ses voisins. Ces vagues d'états d'élévation et de baisse forment le cœur de l'algorithme D*.
Par ce point, toute une série entière de points sont protégés d'être "touchés" par les vagues. L'algorithme a donc seulement travaillé sur les points qui sont concernés par le changement de coût.
Un obstacle été ajouté (rouge) et les noeuds ont été marqués ELEVE (jaune).
L'expansion est en cours. La couleur jaune montre les nœuds marqués comme ELEVE, la couleur verte montre les nœuds marqués BAISSE.
Un autre interblocage se produit
Cette fois, l'interblocage ne peut pas être contourné aussi élégamment. Aucun des points ne peut trouver une nouvelle route depuis un voisin vers la destination. C'est pourquoi, ils continuent de propager leur augmentation de coût. C'est seulement à l'extérieur du canal que des points qui mènent à destination via une route viable peuvent être trouvés. C'est comme cela que deux vagues de BAISSE se développement, qui s'étendent comme des points marqués inaccessibles avec une nouvelle route d'information.
Le canal est bloqués par des obstacles additionnels (rouge)
Expansion en cours (Vague ELEVE en jaune, vague BAISSE en vert)
Nouveau chemin trouvé (cyan)
Pseudo-code
while (!pointsOuvertsListe.estVide()) {
point = pointsOuvertsListe.donnePremier();
expansion(point);
}
Expansion
void expansion(pointCourant) {
boolean estEleve = estEleve(pointCourant);
double cout;
foreach (pointVoisin in pointCourant.donneVoisins()) {
if (estEleve) {
if (pointVoisin.prochainPoint == pointCourant) {
pointVoisin.fixeProchainPointEtActualiseCout(pointCourant);
pointsOuvertsListe.add(pointVoisin );
} else {
cout = pointVoisin.calculeCoutPassantPar(pointCourant);
if (cout < pointVoisin.donneCout()) {
pointCourant.fixeCoutMinimumAuCoutCourant();
pointsOuvertsListe.add(pointCourant);
}
}
} else {
cout = pointVoisin.calculeCoutPassantPar(pointCourant);
if (cout < pointVoisin.donneCout()) {
pointVoisin.fixeProchainPointEtActualiseCout(pointCourant);
pointsOuvertsListe.add(pointVoisin);
}
}
}
}
Vérification de l'élévation
boolean estEleve(point) {
double cout;
if (point.donneCoutCourant() > point.donneCoutMinimum()) {
foreach(pointVoisin in point.donneVoisins()) {
cout = point.calculeCoutPassantPar(pointVoisin);
if (cout < point.donneCoutCourant()) {
point.fixeProchainPointEtActualiseCout(pointVoisin);
}
}
}
return point.donneCoutCourant() > point.donneCoutMinimum();
}
Variantes
Focused D*
Comme son nom le suggère, Focused D* est une extension de D* qui utilise une heuristique pour focaliser l'élévation et la baisse en direction du robot. De cette façon, seuls les états qui comptent sont mis à jour, de la même façon que A* calcule seulement le coût de certains des nœuds.
D* Lite
D* Lite n'est pas basé sur l'algorithme original D* ou Focused D*, mais il implémente un comportement similaire. Il est plus simple à comprendre et peut être implémenté en moins de lignes de code, d'où son nom "D* Lite". Pointe de vue performances, il est aussi bon ou meilleur que Focused D*. D* Lite est basé sur LPA* (Lifelong Planning A*), qui a été présenté par Koenig et Likhachev quelques années plus tôt. D* Lite
Algorithme 3D D*
L'algorithme D* en trois dimensions se focalise sur le calcul du chemin optimal en matière de consommation d'énergie dans un environnement non coopératif à trois dimensions. Il utilise un concept d'allocation de coût dynamique dans l'axe vertical et prend une approche de planification de chemin incrémentale pour calculer la route selon les mises à jour des informations de terrain. Cet algorithme léger est implémentable sur du matériel embarqué a été développé pour des robots aériens de petite taille par Shibarchi et Manishankar.
Coût minimum vs. coût actuel
Pour D*, il est important de faire la distinction entre le coût courant et le cout minimum. Le premier est seulement important au moment de la collecte et le second est critique car il ordonne la liste OUVERT. La fonction qui retourne le coût minimum est toujours le coût le plus bas vers le point courant car c'est la première entrée dans la liste OUVERT.
Références
- (en) Anthony Stentz, « Optimal and Efficient Path Planning for [sic] Known Environments », Proceedings of the International Conference on Robotics and Automation,‎ , p. 3310–3317 (CiteSeerx 10.1.1.15.3683)
- (en) Anthony Stentz, « The Focussed D* Algorithm for Real-Time Replanning », Proceedings of the International Joint Conference on Artificial Intelligence,‎ , p. 1652–1659 (CiteSeerx 10.1.1.41.8257)
- (en) P. Hart, N. Nilsson et B. Raphael, « A Formal Basis for the Heuristic Determination of Minimum Cost Paths », IEEE Trans. Syst. Science and Cybernetics, vol. SSC-4, no 2,‎ , p. 100–107
- (en) S. Koenig et M. Likhachev, « Fast Replanning for Navigation in Unknown Terrain », Transactions on Robotics, vol. 21, no 3,‎ , p. 354–363 (DOI 10.1109/tro.2004.838026)
- (en) S. Koenig, M. Likhachev et D. Furcy, « Lifelong Planning A* », Artificial Intelligence Journal, vol. 155, nos 1–2,‎ , p. 93–146 (DOI 10.1016/j.artint.2003.12.001)
- (en) G. Ramalingam et T. Reps, « An incremental algorithm for a generalization of the shortest-path problem », Journal of Algorithms, vol. 21,‎ , p. 267–305 (DOI 10.1006/jagm.1996.0046)
- (en) S. Koenig, Y. Smirnov et C. Tovey, « Performance Bounds for Planning in Unknown Terrain », Artificial Intelligence Journal, vol. 147, nos 1–2,‎ , p. 253–279 (DOI 10.1016/s0004-3702(03)00062-6)
- (en) D. Wooden, Graph-based Path Planning for Mobile Robots, Georgia Institute of Technology,