• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Multi-Agent Pathfinding with Continuous Time

P. 39-45.
Andreychuk A., Yakovlev K., Atzmon D., Stern R.

Multi-Agent Pathfinding (MAPF) is the problem offinding paths for multiple agents such that everyagent reaches its goal and the agents do not col-lide. Most prior work on MAPF was on grids, as-sumed agents’ actions have uniform duration, andthat time is discretized into timesteps. We proposea MAPF algorithm that does not rely on these as-sumptions, is complete, and provides provably op-timal solutions. This algorithm is based on a noveladaptation of Safe interval path planning (SIPP), acontinuous time single-agent planning algorithm,and a modified version of Conflict-based search(CBS), a state of the art multi-agent pathfinding al-gorithm. We analyze this algorithm, discuss its prosand cons, and evaluate it experimentally on severalstandard benchmarks.

In book

Edited by: S. Kraus. International Joint Conferences on Artificial Intelligence, 2019.