Overview

We address a challenging multi-agent pathfinding (MAPF) problem for hundreds of agents moving on a 2D roadmap with continuous time. Despite its known potential for producing better solutions compared to typical grid and discrete-time cases, few approaches have been established to solve this problem due to the intractability of collision checks on a large scale. In this work, we propose Prioritized Safe-Interval Path Planning with Continuous-Time Conflicts (PSIPP/CTC) that extends a scalable prioritized planning algorithm to work on the 2D roadmap and continuous-time setup by alleviating intensive collision checks. Extensive experimental evaluations demonstrate that PSIPP/CTC significantly outperforms existing methods in terms of planning success rate and runtime while maintaining an acceptable solution quality. As a proof of concept, we also confirmed the effectiveness of the proposed approach on a physics simulation with differential wheeled robots.

Slides

Prioritized Safe Interval Path Planning with Continuous-Time Conflict Annotation

A promising direction to enable MAPF on a large scale is to adopt prioritized planning a fast non-complete MAPF algorithm that determines a set of agent paths one by one in sequence. We are interested in extending the prioritized planning to work with a continuous time setup, particularly by performing Safe Interval Path Planning (SIPP) to find each agent’s path. This is significantly challenging as SIPP requires all possible ‘safe’ (i.e., collision-free) intervals to be enumerated for each vertex and edge for each agent, which is computationally too expensive. A recent work has proposed pre-computing conflicts, pairs among vertices and edges that can cause collisions between agents, so that planning can be done without expensive collision checks. To extend this idea to our setup, we propose a novel concept named Continuous-Time Conflict (CTC), which describes a pair among vertices and edges associated with continuous-time intervals within which collisions can happen between agents. We pre-compute CTCs using geometric neighbor-search and sweeping techniques and annotate roadmaps with the CTCs just once before planning starts. Doing so allows us to efficiently enumerate collision-free time intervals for all vertices and edges and find each agent’s path with continuous time in prioritized planning.

Results

Environments and Generated Plans

Our method works with roadmaps in various environments.

It can even allow us to find collision-free paths for hundreds or thousands of agents in just 30 seconds.

Runtime

For various environments and roadmaps, our method reduces runtime for planning significantly, comparing with Prioritized Safe Interval Path Planning without Continuous-Time Conflict Annotation and baseline method (Continuous Conflict-Based Search).

Simulation Result

We simulated the plan produced by our method with differential wheeled robots. To produce plans executable by wheeled robots, we consider times for rotation, acceleration and deceleration.

Contact

Citation

@article{kasaura2022prioritized,
  title={Prioritized Safe Interval Path Planning for Multi-Agent Pathfinding With Continuous Time on 2D Roadmaps},
  author={Kasaura, Kazumi and Nishimura, Mai and Yonetani, Ryo},
  journal={IEEE Robotics and Automation Letters},
  volume={7},
  number={4},
  pages={10494--10501},
  year={2022},
  publisher={IEEE}
}