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 conferencia

3 Citas (Scopus)

Resumen

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
Volumen2018-August
ISBN (versión digital)9781538643594
DOI
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

Conferencia

Conferencia14th IEEE Conference on Computational Intelligence and Games, CIG 2018
PaísPaíses Bajos
CiudadMaastricht
Período14/08/1817/08/18

    Huella digital

Á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

Citar esto

Sigurdson, D., Bulitko, V., Yeoh, W., Hernandez, C., & Koenig, S. (2018). Multi-Agent Pathfinding with Real-Time Heuristic Search. En Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games, CIG 2018 (Vol. 2018-August). [8490436] IEEE Computer Society. https://doi.org/10.1109/CIG.2018.8490436