8.4 Recherche de plus court chemin moiti-agents
159
91
0
0
0
0
0
0
0
0
0
0
0
0
0
0
az
0
0
0
0
0
0
a1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
92
TA BLE 8.2 - Interblocage dans un couloir avec 2 agents
replanifier son chemin en prenant en compte la position de l' autre agent. Le nouveau
plus court chemin de a1 commencera par se déplacer vers la droite, de même pour az .
Après ce premier déplacement, les deux agents seront de nouveau en interblocage. Ils se ·
déplaceront alors vers la gauche et se retrouveront dans la même position qu' auparavant.
On a alors un cycle d' interblocages.
Pour éviter les cycles on peut utiliser un niveau d' agitation de l ' agent. À chaque fois
qu' il doit replanifier, son niveau d' agitation augmente ce qui revient à aj outer du bruit à
son heuristique. Les agents agiront ainsi de plus en plus aléatoirement au fur et à mesure
des interblocages ce qui peut permettre de les débloquer. Le problème avec cette stratégie
est qu'elle peut rester bloquée longtemps lorsqu' il y a beaucoup d' agents et que chaque
agent exécute un A* à chaque déplacement [85] ce qui conduit à des comportements peu
intelligents et lents.
8.4.3 Recherche coopérative
La recherche coopérative [82] calcule chaque chemin individuellement. Elle effectue
les recherches dans on ordre determiné des agents. Après chaque nouveau chemin calculé,
les positions par lesquelles passe l ' agent sont réservées dans une table de réservation. Un
état comprend une position et un temps auquel cette position est occupée. Plutôt que de
représenter tous les états possibles, on utilise une table de hachage pour stocker les états
réservés. Les chemins des agents suivants connaissent les réservations et les évitent.
Il arrive toutefois que le chemin réservé par un agent empèche les agents suivants de
trouver un chemin. La recherche coopérative ne peut pas résoudre le problème de la figure
8.1 par exemple. Elle permet toutefois de résoudre le problème de la figure 8.2.
Les problèmes rencontrés par la recherche coopérative sont par exemple quand un
agent atteint son but dans un couloir et empèche les autres agents de passer, ou quand
l' ordre des agents fixé une fois pour toutes empèche de trouver une solution. De plus cette
recherche est coûteuse en temps. L' algorithme peut être amélioré en variant l 'ordre des
agents et en intercalant la planification avec les actions. La recherche avec une fenêtre [82]
est une solution à ces problèmes. Elle consiste à faire la recherche à une profondeur fixée
159
91
0
0
0
0
0
0
0
0
0
0
0
0
0
0
az
0
0
0
0
0
0
a1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
92
TA BLE 8.2 - Interblocage dans un couloir avec 2 agents
replanifier son chemin en prenant en compte la position de l' autre agent. Le nouveau
plus court chemin de a1 commencera par se déplacer vers la droite, de même pour az .
Après ce premier déplacement, les deux agents seront de nouveau en interblocage. Ils se ·
déplaceront alors vers la gauche et se retrouveront dans la même position qu' auparavant.
On a alors un cycle d' interblocages.
Pour éviter les cycles on peut utiliser un niveau d' agitation de l ' agent. À chaque fois
qu' il doit replanifier, son niveau d' agitation augmente ce qui revient à aj outer du bruit à
son heuristique. Les agents agiront ainsi de plus en plus aléatoirement au fur et à mesure
des interblocages ce qui peut permettre de les débloquer. Le problème avec cette stratégie
est qu'elle peut rester bloquée longtemps lorsqu' il y a beaucoup d' agents et que chaque
agent exécute un A* à chaque déplacement [85] ce qui conduit à des comportements peu
intelligents et lents.
8.4.3 Recherche coopérative
La recherche coopérative [82] calcule chaque chemin individuellement. Elle effectue
les recherches dans on ordre determiné des agents. Après chaque nouveau chemin calculé,
les positions par lesquelles passe l ' agent sont réservées dans une table de réservation. Un
état comprend une position et un temps auquel cette position est occupée. Plutôt que de
représenter tous les états possibles, on utilise une table de hachage pour stocker les états
réservés. Les chemins des agents suivants connaissent les réservations et les évitent.
Il arrive toutefois que le chemin réservé par un agent empèche les agents suivants de
trouver un chemin. La recherche coopérative ne peut pas résoudre le problème de la figure
8.1 par exemple. Elle permet toutefois de résoudre le problème de la figure 8.2.
Les problèmes rencontrés par la recherche coopérative sont par exemple quand un
agent atteint son but dans un couloir et empèche les autres agents de passer, ou quand
l' ordre des agents fixé une fois pour toutes empèche de trouver une solution. De plus cette
recherche est coûteuse en temps. L' algorithme peut être amélioré en variant l 'ordre des
agents et en intercalant la planification avec les actions. La recherche avec une fenêtre [82]
est une solution à ces problèmes. Elle consiste à faire la recherche à une profondeur fixée