Recherche de chemins de coût minimal avec l’algorithme A* Mise en œuvre pratique

Recherche de cheminsde coût minimal

avec l’algorithme A*Mise en œuvre pratique

Olivier NOCENTIUT de Reims-Châlons-Charlevillerue des crayères, BP 103551687 Reims Cedex 2

Introduction

Objectif : Déterminer, pour un agent* donné, un chemin de coût minimum depuis un sommet source vers un sommet destination au sein d’un graphe orienté.

Un agent est un objet informatique autonome utilisé pour représenter une entité mobile dotée d’un comportement (humain, animal, véhicule, …)

Applications

Jeux vidéo Animation des personnages non joueurs (RPG, FPS) Déplacement réaliste d’un personnage contrôlé par le

joueur vers un objectif désigné par le joueur (RTS)

Simulation – vie artificielle Etude du comportement d’une foule, du traffic

automobile, … Effets spéciaux (scènes de bataille, …)

Représentation du graphe à partir d’informations topographiques

Relations d’adjacence : grille carrée

Prairie

Rivière

Pont

Relations d’adjacence : grille hexagonale

Prairie

Rivière

Pont

Relations d’adjacence : points visibles

Obstacles

Couloirs

Coût des arcs

Signification du coût d’un arc :

Distance kilométrique Recherche de chemins de longueur minimale

Temps (nécessaire au franchissement de l’arc) Recherche de chemins en temps minimum

Consommation de carburant Rechercher de chemins « économes »

Coût des arcs : grille carrée

1010

10

10

Coût des arcs : grille hexagonale

10

10

1010

10

10

10

10

10

10

10

10

Triangle équilatéral

Coût des arcs : pondération en fonction de la nature de l’environnement

10 1010

4010

4010

10

1040

10

10

10

80

10

40

10

40 80

40 40

80

40

80

Prairie

Montagne

Coût des arcs : pondération en fonction de la nature de l’agent

C C

Coût du franchissement d’un pont

C = 10 pour un humain.

C = 50 pour une voiture.

C = 500 pour un semi-remorque.

Algorithme A*

Principe général : évaluation du coût total d’un sommet

Coût total (F) = Coût depuis la source (G) + Coût vers la destination (H)

G : Coût depuis la source Algorithmes classiques (Ford, Bellman, Dijkstra) Gi = min Gj + Cij / i prédecesseur de j

Cij coût de l’arc (i,j)

H : Coût vers la destination Difficile puisque le reste du chemin (vers la

destination) est encore inconnu.

Coût vers la destination

Pourquoi évaluer un coût vers la destination ?Afin de resserrer l’ensemble des sommets à explorer en privilégiant les sommets « qui semblent » nous rapprocher de la destination.

RemarqueDans le cas d’un algorithme de recherche plus classique (Dijsktra), on effectue une recherche exhaustive parmi TOUS les sommets.

Conséquencel’algorithme A* est plus performant que n’importe quel autre algorithme puisqu’il diminue l’ensemble des sommets à explorer.

Coût vers la destination

Comment évaluer un coût vers la destination ?En utilisant des heuristiques (prédictions) afin d’évaluer un coût vers la destination INFERIEUR au coût réel (encore inconnu).

A ce titre, A* est un algorithme optimiste.

RemarqueSi l’heuristique était supérieur au coût réel, on risquerait de générer un chemin qui ne soit pas minimal.

Distance euclidienne

S

D

40

H 20

Théorème de Pythagore

H 2 = (Coté oppose) 2 +

(Coté adjacent) 2

H 2 = 40 2 + 20 2

= 2000

H = 20 x (5) 1/2

Distance de Manhattan

S

D

Nombre de cellules, en horizontal et en vertical entre la source et la destination.

Plus conforme à la nature des déplacements autorisés (haut, bas, gauche, droite)

Algorithme A*InitialisationSommet source (S)Sommet destination (D)Liste des sommets à explorer (E) : sommet source SListe des sommets visités (V) : vide

Tant que (la liste E est non vide) et (D n’est pas dans E) Faire+ Récupérer le sommet X de coût total F minimum.+ Ajouter X à la liste V+ Ajouter les successeurs de X (non déjà visités) à la liste E en évaluant leur coût total F et en identifiant leur prédécesseur.

+ Si (un successeur est déjà présent dans E) et (nouveau coût est inférieur à l’ancien) Alors

Changer son coût totalChanger son prédécesseur

FinSiFinFaire

Exemple 1

S

D

S

D

Sommet source

Sommet destination

Obstacle

Exemple 1

S

D10 + 30

10 + 50

10 + 50

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40 Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

20 + 60

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

20 + 60

30 + 50 Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

20 + 60

30 + 50 30 + 30 Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

20 + 60

30 + 50 30 + 30 40 + 20 Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

20 + 60

30 + 50 30 + 30 40 + 20 50 + 10

50 + 10

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

10 + 30

10 + 50

10 + 50

20 + 40

20 + 40

20 + 60

20 + 60

30 + 50 30 + 30 40 + 20 50 + 10

50 + 10

60 + 20

60 + 0

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

Exemple 1

S

D

Exemple 2

S

D

S

D

Sommet source

Sommet destination

Obstacle

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80 50 + 70

50 + 50

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80 50 + 70

50 + 50

60 + 60

60 + 40

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80 50 + 70

50 + 50

60 + 60

60 + 40

70 + 50

70 + 30

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80 50 + 70

50 + 50

60 + 60

60 + 40

70 + 50

70 + 30

80 + 40

80 + 20

Exemple 2

S

D

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80 50 + 70

50 + 50

60 + 60

60 + 40

70 + 50

70 + 30

80 + 40

80 + 20

90 + 10

Exemple 2

S

Sommet déjà visité

Sommet à explorer

G + H

Coût depuisla source

Coût versla destination

Référence auprédécesseur

10 + 50 10 + 30

20 + 60

20 + 40

30 + 50

30 + 70

40 + 60

40 + 80 50 + 70

50 + 50

60 + 60

60 + 40

70 + 50

70 + 30

80 + 40

80 + 20

90 + 10

100 + 0

Exemple 2

S

D

Structure des données : détail d’implémentation

InitialisationSommet source (S)Sommet destination (D)Liste des sommets à explorer (E) : sommet source SListe des sommets visités (V) : vide

Tant que (la liste E est non vide) et (D n’est pas dans E) Faire+ Récupérer le sommet X de coût total F minimum.+ Ajouter X à la liste V+ Ajouter les successeurs de X (non déjà visités) à la liste E en évaluant leur coût total F et en identifiant leur prédécesseur.

+ Si (un successeur est déjà présent dans E) et (nouveau coût est inférieur à l’ancien) Alors

Changer son coût totalChanger son prédécesseur

FinSiFinFaire

Structure des données : détail d’implémentation

Nécessité de mettre en œuvre un conteneur permettant de :

Récupérer un élément de coût total minimum. Insérer un nouvel élément et trier le conteneur. Mettre à jour le coût total d’un élément déjà présent dans le

conteneur. Déterminer si le conteneur est vide.

Solution « élégante » : files

Template <class T>class std::queue{public:

…bool empty();T pop() {return pop_front();}void push(T t) { push_back(t);}

};

tpush(t) pop()

Solution « élégante » : files à priorité

Le type T doit surcharger l’opérateur de comparaison <

Template <class T>

class std::priority_queue

{

public:

…

bool empty();

T pop() {return pop_front();}

void push(T t) { /*insertion triée*/ }

};

tpush(t) pop()

Insertion triée « efficace »

Utilisation d’un arbre binaire d’éléments Le fils gauche est strictement inférieur au nœud courant. Le fils droit est supérieur ou égal au nœud courant.

5

3 12

41 7 20

15 25

Structure des données : std::priority_queue

Nécessité de mettre en œuvre un conteneur permettant de :

Récupérer un élément de coût total minimum : OUI Insérer un nouvel élément et trier le conteneur : OUI Mettre à jour le coût total d’un élément déjà présent dans le

conteneur : NON Déterminer si le conteneur est vide : OUI

Structure de données personnalisée : MyPriorityQueue

template<class T>class MyPriorityQueue{public :

T pop();void push();

private: std::vector<T> heap;

};

Structure de données personnalisée : MyPriorityQueue

template<class T>T MyPriorityQueue::pop(){

// L’élément le plus grand est au début// du conteneur heap : position 0.T value = heap.front();

// 1. Déplace le premier élément à la position N-1.// 2. Trie les éléments de la position 0 à N-2std::pop_heap(heap.begin(), heap.end(), Inf());

// Supprime l’élément en position N-1// c’est à dire, l’ancien premier.

heap.pop_back();

return value;}

Structure de données personnalisée : MyPriorityQueue

template<class T>T MyPriorityQueue::push(T value){

// Ajout de la valeur en queue du conteneur// position N.heap.push_back(value);

// Trie les éléments de la position 0 à N.std::push_heap(heap.begin(), heap.end(), Inf());

return value;}

Un peu de lecture

Game Programming Gems 1

by Mark de DeLoura

(Charles River Media )

August, 2000

http://www.gamedev.net

http://www.gamasutra.com