Multi-Agent Pathfinding with Continuous Time
Multi-Agent Pathfinding with Continuous Time
Anton Andreychuk, Konstantin Yakovlev, Dor Atzmon, Roni Stern
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 39-45.
https://doi.org/10.24963/ijcai.2019/6
Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that every agent reaches its goal and the agents do not collide. Most prior work on MAPF were on grids, assumed agents' actions have uniform duration, and that time is discretized into timesteps. In this work, we propose a MAPF algorithm that do not assume any of these assumptions, is complete, and provides provably optimal solutions. This algorithm is based on a novel combination of Safe Interval Path Planning (SIPP), a continuous time single agent planning algorithms, and Conflict-Based Search (CBS). We analyze this algorithm, discuss its pros and cons, and evaluate it experimentally on several standard benchmarks.
Keywords:
Agent-based and Multi-agent Systems: Multi-agent Planning
Heuristic Search and Game Playing: Heuristic Search