Multi-Agent Pathfinding with Real-Time Heuristic Search

Devon Sigurdson, Vadim Bulitko, William Yeoh, Carlos Hernandez, Sven Koenig

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

12 Citas (Scopus)


Multi-agent pathfinding, namely finding collision-free paths for several agents from their given start locations to their given goal locations on a known stationary map, is an important task for non-player characters in video games. A variety of heuristic search algorithms have been developed for this task. Non-real-time algorithms, such as Flow Annotated Replanning (FAR), first find complete paths for all agents and then move the agents along these paths. However, their searches are often too expensive. Real-time algorithms have the ability to produce the next moves for all agents without finding complete paths for them and thus allow the agents to move in real time. Real-time heuristic search algorithms have so far typically been developed for single-agent pathfinding. We, on the other hand, present a real-time heuristic search algorithm for multi-agent pathfinding, called Bounded Multi-Agent A∗ (BMAA∗), that works as follows: Every agent runs an individual real-time heuristic search that updates heuristic values assigned to locations and treats the other agents as (moving) obstacles. Agents do not coordinate with each other, in particular, they neither share their paths nor heuristic values. We show how BMAA∗ can be enhanced by adding FAR-style flow annotations and allowing agents to push other agents temporarily off their goal locations, when necessary. In our experiments, BMAA∗ has higher completion rates and lower completion times than FAR.

Idioma originalInglés
Título de la publicación alojadaProceedings of the 2018 IEEE Conference on Computational Intelligence and Games, CIG 2018
EditorialIEEE Computer Society
ISBN (versión digital)9781538643594
EstadoPublicada - 11 oct. 2018
Evento14th IEEE Conference on Computational Intelligence and Games, CIG 2018 - Maastricht, Países Bajos
Duración: 14 ago. 201817 ago. 2018

Serie de la publicación

NombreIEEE Conference on Computatonal Intelligence and Games, CIG
ISSN (versión impresa)2325-4270
ISSN (versión digital)2325-4289


Conferencia14th IEEE Conference on Computational Intelligence and Games, CIG 2018
País/TerritorioPaíses Bajos

Áreas temáticas de ASJC Scopus

  • Inteligencia artificial
  • Infografía y diseno asistido por ordenador
  • Visión artificial y reconocimiento de patrones
  • Interacción persona-ordenador
  • Software


Profundice en los temas de investigación de 'Multi-Agent Pathfinding with Real-Time Heuristic Search'. En conjunto forman una huella única.

Citar esto