158
Recherche de plus court chemin sur une carte
ai a2 a3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
a4 as a6
TA BLE 8.1 - É change de places dans un couloir pour 6 agents
8.4.1 Algorithme optimal
L' algorithme exact standard est A * . La facteur de branchement de l'algorithme est
5 n b Agen t s si l'agent a cinq actions possibles (haut, bas, droite, gauche et attendre). La
taille de l'espace d'états est de l'ordre de tailleCarte n b Agen t s où tailleCarte est le
nombre de positions sur la carte.
Lorsque le nombre d'agents est élevé, il peut être très intéressant de décomposer les
déplacements des agents en déplacements individuels et d'évaluer après chaque déplacement individuel si la recherche ne dépasse pas le seuil autorisé en combinaison avec un
algorithme d'approfondissement itératif [26].
Une autre approche qui permet de trouver des chemins optimaux à moindre coût dans
de nombreux cas est décrite dans [90, 91].
8.4.2 Algorithme avec replanification
L' algorithme le plus simple pour résoudre efficacement la recherche de plus court
chemin multi-agents est de calculer le plus court chemin de chaque agent indépendamment des autres agents. Si les chemins trouvés ne créent pas de collisions, on a alors
un résultat optimal. To utefois, il arrive souvent sur des cartes difficiles que les chemins
se croisent, surtout lorsque la carte comporte des passages étroits et qu'il y a beaucoup
d'agents. Une solution est d'utiliser quand même les chemins individuels et de chercher à
nouveau lorsque le chemin est impraticable à cause des autres agents. Le problème avec
cet algorithme est qu'il ne résout pas les interblocages et les répétitions d'états.
Un problème difficile de planification multi-agents est donné figure 8.1 ; le but est que
ai, a2 et a3 échangent de places avec a4, as et a6. L' agent a4 doit aller à la place de ai, as
en a2 et a6 en a3. L' algorithme optimal est capable de résoudre le problème de la figure
8. 1 alors que la replanification n'en est pas capable.
Concernant le problème de la figure 8.2 l'agent ai doit aller en 9i et l'agent a2 doit
aller en g2. Or ai est sur le chemin de a2 et réciproquement. Chaque agent va alors
Recherche de plus court chemin sur une carte
ai a2 a3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
a4 as a6
TA BLE 8.1 - É change de places dans un couloir pour 6 agents
8.4.1 Algorithme optimal
L' algorithme exact standard est A * . La facteur de branchement de l'algorithme est
5 n b Agen t s si l'agent a cinq actions possibles (haut, bas, droite, gauche et attendre). La
taille de l'espace d'états est de l'ordre de tailleCarte n b Agen t s où tailleCarte est le
nombre de positions sur la carte.
Lorsque le nombre d'agents est élevé, il peut être très intéressant de décomposer les
déplacements des agents en déplacements individuels et d'évaluer après chaque déplacement individuel si la recherche ne dépasse pas le seuil autorisé en combinaison avec un
algorithme d'approfondissement itératif [26].
Une autre approche qui permet de trouver des chemins optimaux à moindre coût dans
de nombreux cas est décrite dans [90, 91].
8.4.2 Algorithme avec replanification
L' algorithme le plus simple pour résoudre efficacement la recherche de plus court
chemin multi-agents est de calculer le plus court chemin de chaque agent indépendamment des autres agents. Si les chemins trouvés ne créent pas de collisions, on a alors
un résultat optimal. To utefois, il arrive souvent sur des cartes difficiles que les chemins
se croisent, surtout lorsque la carte comporte des passages étroits et qu'il y a beaucoup
d'agents. Une solution est d'utiliser quand même les chemins individuels et de chercher à
nouveau lorsque le chemin est impraticable à cause des autres agents. Le problème avec
cet algorithme est qu'il ne résout pas les interblocages et les répétitions d'états.
Un problème difficile de planification multi-agents est donné figure 8.1 ; le but est que
ai, a2 et a3 échangent de places avec a4, as et a6. L' agent a4 doit aller à la place de ai, as
en a2 et a6 en a3. L' algorithme optimal est capable de résoudre le problème de la figure
8. 1 alors que la replanification n'en est pas capable.
Concernant le problème de la figure 8.2 l'agent ai doit aller en 9i et l'agent a2 doit
aller en g2. Or ai est sur le chemin de a2 et réciproquement. Chaque agent va alors