Sommaire des Sommaire des algorithmes de algorithmes de

recherche de chemins recherche de chemins coopérativecoopérative

Équipe PathfinderÉquipe Pathfinder

Michael BrunelleMichael Brunelle

Marc MichaudMarc Michaud

Dominique RuestDominique Ruest

Département d’informatiqueDépartement d’informatique

Université de SherbrookeUniversité de Sherbrooke

HypothèsesHypothèses

• Domaine discret :Domaine discret :– La carte est donnée sous forme de grille La carte est donnée sous forme de grille

divisées en cellules pouvant être libre ou divisées en cellules pouvant être libre ou occupée.occupée.

– Les agents occupent une seule cellule à la Les agents occupent une seule cellule à la fois (un agent ne peut pas être entre deux fois (un agent ne peut pas être entre deux cellule).cellule).

– Les déplacements sont instantanés, c.-à-d. Les déplacements sont instantanés, c.-à-d. que la vitesse de tous les agents est que la vitesse de tous les agents est d’exactement une case par unité de temps.d’exactement une case par unité de temps.

• Actions permises :Actions permises :– Déplacement dans 4 (ou 8?) directionsDéplacement dans 4 (ou 8?) directions– Rester immobile (Rester immobile (WaitWait))

PlanPlan

• LRA*LRA* ((……• CA* CA* (Coopetive A*)(Coopetive A*)• HCA* HCA* ( Hierarchical ( Hierarchical ……• WHCA*WHCA* ( ...( ...• FARFAR( ( ……

Local Repair A* (LRA*)Local Repair A* (LRA*)• N’est pas coopératifN’est pas coopératif• A* a été conçu à la base pour fonctionner A* a été conçu à la base pour fonctionner

avec un seul agentavec un seul agent• LRA* recalcule au complet le chemin LRA* recalcule au complet le chemin

lorsqu’une collision est imminentelorsqu’une collision est imminente• Inefficace lors de situations difficilesInefficace lors de situations difficiles

– Grand nombre d’agentsGrand nombre d’agents– Carte avec circulation restreinteCarte avec circulation restreinte

• Malgré tous ses défauts, il est Malgré tous ses défauts, il est l’algorithme le plus utilisé dans les jeuxl’algorithme le plus utilisé dans les jeux

Cooperative A* (CA*)Cooperative A* (CA*)

• Une recherche par agentUne recherche par agent• Un agent peut rester sur place Un agent peut rester sur place

pendant un tour (pendant un tour (wait movewait move))• La distance de Manhattan peut être La distance de Manhattan peut être

utilisée comme heuristique même utilisée comme heuristique même s’il est recommandé d’utiliser une s’il est recommandé d’utiliser une autre méthode.autre méthode.

Cooperative A* (CA*)Cooperative A* (CA*)

• Utilise les coordonnées de l’espace-Utilise les coordonnées de l’espace-temps (x,y,t) qui sont enregistrés temps (x,y,t) qui sont enregistrés dans une table de réservationdans une table de réservation

Cooperative A* (CA*)Cooperative A* (CA*)

• Certains problèmes ne peuvent être Certains problèmes ne peuvent être résolus par CA*.résolus par CA*.

Hierarchical Cooperative A* Hierarchical Cooperative A* (HCA*)(HCA*)

• Amélioration de CA* en utilisant une Amélioration de CA* en utilisant une meilleure heuristique : Reverse meilleure heuristique : Reverse Resumable A* (RRA*)Resumable A* (RRA*)– RRA est une recherche A* modifiée pour RRA est une recherche A* modifiée pour

partir du but vers le point de départ de partir du but vers le point de départ de l’agentl’agent

– Utilise la distance de Manhattan comme Utilise la distance de Manhattan comme heuristiqueheuristique

• Abstraction en utilisant seulement deux Abstraction en utilisant seulement deux dimensions (x,y) en ignorant les autres dimensions (x,y) en ignorant les autres agentsagents

Windowed Hierarchical Windowed Hierarchical Cooperative A* (WHCA*)Cooperative A* (WHCA*)

• Amélioration de HCA* en utilisant une fenêtre Amélioration de HCA* en utilisant une fenêtre pour vérifier les interactions avec les autres pour vérifier les interactions avec les autres agents.agents.– Calculs répartis tout au long des mouvementsCalculs répartis tout au long des mouvements– Coopératif seulement dans la fenêtreCoopératif seulement dans la fenêtre

• Comme HCA*, WHCA* utilise RRA* comme Comme HCA*, WHCA* utilise RRA* comme heuristique.heuristique.

• Priorité dynamique, chaque agent va avoir une Priorité dynamique, chaque agent va avoir une priorité plus haute pour une courte période de priorité plus haute pour une courte période de temps.temps.

• Un agent rendu à sa destination continue de Un agent rendu à sa destination continue de calculer des chemins dans sa fenêtre pour les calculer des chemins dans sa fenêtre pour les cas où il faudrait qu’il se déplace pour qu’un cas où il faudrait qu’il se déplace pour qu’un autre agent arrive à destination.autre agent arrive à destination.

Flow Annotation Flow Annotation Replanning (FAR)Replanning (FAR)

• Abstraction en utilisant des restrictions sur les directions Abstraction en utilisant des restrictions sur les directions que peuvent prendre les agentsque peuvent prendre les agents– Une ligne et une colonne complète ont la même directionUne ligne et une colonne complète ont la même direction

• Réduction du facteur de branchementRéduction du facteur de branchement• Réduction du risque de collision entre les agentsRéduction du risque de collision entre les agents

– Alternance entre les directions à chaque ligne/colonneAlternance entre les directions à chaque ligne/colonne• Réparation locale au lieu d’une replanification complète lors Réparation locale au lieu d’une replanification complète lors

d’une collisiond’une collision• Utilisation d’A* sur le graphe annotéUtilisation d’A* sur le graphe annoté• Faible demande de temps CPU et de mémoireFaible demande de temps CPU et de mémoire• Utilise les déplacements en diagonale seulement lorsque Utilise les déplacements en diagonale seulement lorsque

c’est nécessairec’est nécessaire• Minimise le plus possible les changements de direction afin Minimise le plus possible les changements de direction afin

de réduire le risque de collisionsde réduire le risque de collisions• Pour un fenêtrage de k, il faut que l’agent puisse réserver Pour un fenêtrage de k, il faut que l’agent puisse réserver

ses k cases d’avance avant de pouvoir bouger, sauf s’il lui en ses k cases d’avance avant de pouvoir bouger, sauf s’il lui en faut moins pour arriver à destination.faut moins pour arriver à destination.

Flow Annotation Flow Annotation Replanning (FAR)Replanning (FAR)

• Connectivité Connectivité – Certaines arrêtes du graphe sont Certaines arrêtes du graphe sont

bidirectionnelles pour éviter d’être confiné bidirectionnelles pour éviter d’être confiné dans une case sans sortiesdans une case sans sorties

Flow Annotation Flow Annotation Replanning (FAR)Replanning (FAR)

• Étreinte fatale (Étreinte fatale (deadlockdeadlock))– Heuristique de densité des nœuds.Heuristique de densité des nœuds.– Déplacement d’un agent du nœud Déplacement d’un agent du nœud

critiquecritique