Multi-Agent Pathfinding with Real-Time Heuristic Search. Sigurdson, D., Bultiko, V., Yeoh, W., Hernandez, C., & Koenig, S. In Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG), pages 1–8, 2018.
abstract   bibtex   
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.
@INPROCEEDINGS{SKoen18r, 
 AUTHOR= "D. Sigurdson and V. Bultiko and W. Yeoh and C. Hernandez and S. Koenig",
 TITLE= "Multi-Agent Pathfinding with Real-Time Heuristic Search",
 BOOKTITLE= "Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG)",
 YEAR= "2018",
 PDF= "http://idm-lab.org/bib/abstracts/papers/cig18.pdf",
 FLAGS= ":2018:,:svenkoenig:,:williamyeoh:",
 PAGES= "1--8",
 ABSTRACT= 
"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."  
}

Downloads: 0