Multi-Agent Pathfinding with Continuous Time
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.