8.4 Recherche de plus court chemin moiti-agents
157
peuvent alors être utilisées pour calculer une heuristique admissible. L' heuristique utilise
l ' inégalité triangulaire. Si par exemple JI X , Y ll est la longueur du plus court chemin entre
X et Y, et si les distances sont pré calculées depuis P , que le noeud courant est en D , et
que le but à atteindre est en A , on a les inégalités suivantes :
JIP, Ali S llP, Dll + llD, Ali
(8.1)
llD, Pll S llD, AJI + llA, Pll
(8.2)
Exercice : Trouver une heuristique admissible pour llD, Ali à partir ces inégalités.
Si les distances sont pré-calculées depuis plusieurs points, l ' heuristique choisit pour
h le maximum sur tous les points de l ' heuristique fournie par l' heuristique triangulaire et
de l' heuristique de Manhattan.
Pour accélérer le calcul de l' heuristique avec P points, au lieu de prendre l' heuristique
maximum sur les P points, on peut sélectionner à la racine le point qui donne le h maximum et ne plus utiliser que celui ci pour calculer l' heuristique par la suite. Pour chaque
noeud de la recherche, on prend alors le maximum de l' heuristique de Manhattan et de
l ' heuristique triangulaire pour ce point.
L'heuristique triangulaire avec seulement le meilleur point donne des valeurs plus
petites et donc moins bonnes que l ' heuristique triangulaire avec plusieurs points. La recherche développera plus de noeuds. Cependant le temps de calcul de l ' heuristique est
plus faible, ce qui finalement lui permet souvent d' avoir de meilleurs temps de réponse.
Exercice : Implémenter la recherche de plus court chemin avec l' heuristique triangulaire pour A* .
8.4 Recherche de plus court chemin moiti-agents
La recherche de plus court chemin multi-agents est un problème PSPACE-difficile
[43]. La difficulté supplémentaire par rapport au cas mono-agent est que les agents ne
doivent pas entrer en collision.
La plupart des recherches sur ce problème concernent des algorithmes inexacts car le
problème est considéré comme trop difficile pour être résolu exactement. Les algorithmes
inexacts consistent en général à combiner des chemins individuels comme par exemple
dans la recherche de plus court chemin coopérative [82).
157
peuvent alors être utilisées pour calculer une heuristique admissible. L' heuristique utilise
l ' inégalité triangulaire. Si par exemple JI X , Y ll est la longueur du plus court chemin entre
X et Y, et si les distances sont pré calculées depuis P , que le noeud courant est en D , et
que le but à atteindre est en A , on a les inégalités suivantes :
JIP, Ali S llP, Dll + llD, Ali
(8.1)
llD, Pll S llD, AJI + llA, Pll
(8.2)
Exercice : Trouver une heuristique admissible pour llD, Ali à partir ces inégalités.
Si les distances sont pré-calculées depuis plusieurs points, l ' heuristique choisit pour
h le maximum sur tous les points de l ' heuristique fournie par l' heuristique triangulaire et
de l' heuristique de Manhattan.
Pour accélérer le calcul de l' heuristique avec P points, au lieu de prendre l' heuristique
maximum sur les P points, on peut sélectionner à la racine le point qui donne le h maximum et ne plus utiliser que celui ci pour calculer l' heuristique par la suite. Pour chaque
noeud de la recherche, on prend alors le maximum de l' heuristique de Manhattan et de
l ' heuristique triangulaire pour ce point.
L'heuristique triangulaire avec seulement le meilleur point donne des valeurs plus
petites et donc moins bonnes que l ' heuristique triangulaire avec plusieurs points. La recherche développera plus de noeuds. Cependant le temps de calcul de l ' heuristique est
plus faible, ce qui finalement lui permet souvent d' avoir de meilleurs temps de réponse.
Exercice : Implémenter la recherche de plus court chemin avec l' heuristique triangulaire pour A* .
8.4 Recherche de plus court chemin moiti-agents
La recherche de plus court chemin multi-agents est un problème PSPACE-difficile
[43]. La difficulté supplémentaire par rapport au cas mono-agent est que les agents ne
doivent pas entrer en collision.
La plupart des recherches sur ce problème concernent des algorithmes inexacts car le
problème est considéré comme trop difficile pour être résolu exactement. Les algorithmes
inexacts consistent en général à combiner des chemins individuels comme par exemple
dans la recherche de plus court chemin coopérative [82).