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*), de Anthony Stentz, est un algorithme de recherche incrémentale informé.
 L'algorithme Focused D* (ou D* focalisé) est un algoritme de recherche incrémentale informé heuristique de Anthony Stentz qui combine des idées de A* 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) est un algorithme de recherche incremental heuristique de Sven Koenig et Maxim Likhachev qui s'appuie sur LPA*, un algorithme de recherche incrementale heuristique qui combine les idées de A* et Dynamic SWSF-FP.

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, 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. 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.

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 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.

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

Liens externes 
  Page web de Sven Koenig
  Page web de Anthony Stentz

Robotique
D*
Algorithme de recherche
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* ) , de Anthony Stentz , est un algorithme de recherche incrémentale informé . L' algorithme Focused D* ( ou D* focalisé ) est un algoritme de recherche incrémentale informé heuristique de Anthony Stentz qui combine de les idées de A* 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 ) est un algorithme de recherche incremental heuristique de Sven Koenig et Maxim Likhachev qui s' appuie sur LPA* , un algorithme de recherche incrementale heuristique qui combine les idées de A* et Dynamic SWSF -FP . 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 , dans laquelle un robot doit naviguer à les coordonnées d' un but donné en terrain inconnu . Il doit faire de les hypothèses sur la partie inconnue de le 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 de le but selon ces hypothèses . Le robot suit alors le chemin . Lorsqu' il observe une nouvelle information cartographique ( telle que de les 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 de le but donné . Il répète le processus jusqu' à ce qu' il atteigne les coordonnées de le but ou qu' il détermine que les coordonnées de le 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 de les séquences de problèmes de recherche similaires en utilisant l' expérience acquise sur de les problèmes précédents pour résoudre plus rapidement le problème courant . Sous l' hypothèse que les coordonnées de le but ne changent pas , tous les trois algoritmes de recherche sont plus efficients que de les 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 . 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 Le nom D* vient de le terme " Dynamic A* " , parce que l' algorithme se comporte comme A* sauf que le coût de les arcs change à le 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 de les nœuds à évaluer , appelée la liste " OUVERTE " . Les nœuds sont marqués comme ayant un de les 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 de le nœud à tous les nœuds de le voisinage et les place dans la liste OUVERTE . Ce processus de propagation est appelé " expansion " . Contrairement à le A* canonique , qui suit le chemin de le 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' à le but peut être trouvé en suivant simplement les rétro-pointeurs . Gestion de les obstacles Lorsqu' un obstruction est détectée le long de le 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 de le nœud . Si ce n' est pas le cas , l' état ELEVE est propagé à tous les descendants de le nœud , c'est-à-dire les nœuds qui ont de les 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 autre interblocage se produit Cette fois , l' interblocage ne peut pas être contourné aussi élégamment . Aucun de les 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 de le canal que de les 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 de les points marqués inaccessibles avec une nouvelle route d' information . 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 de le 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 de les 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 D* L' algorithme D* en trois dimensions se focalise sur le calcul de le 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 de les informations de terrain . Cet algorithme léger est implémentable sur de le matériel embarqué a été développé pour de les 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 à le 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 Liens externes Page web de Sven Koenig Page web de Anthony Stentz Robotique D* Algorithme de recherche