Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space
This addresses the problem of scalable and high-quality path planning for multiple robots in continuous environments, which is incremental as it builds on existing sampling-based and conflict-resolution methods.
The paper tackles multi-robot path planning in continuous space by proposing a two-level approach with Safe Interval RRT* (SI-RRT*) for individual robot trajectories and high-level methods like Prioritized Planning (SI-CPP) and Conflict Based Search (SI-CCBS) to resolve conflicts, resulting in SI-CPP showing improved scalability and SI-CCBS producing higher-quality solutions compared to state-of-the-art planners.
In this paper, we consider the problem of Multi-Robot Path Planning (MRPP) in continuous space. The difficulty of the problem arises from the extremely large search space caused by the combinatorial nature of the problem and the continuous state space. We propose a two-level approach where the low level is a sampling-based planner Safe Interval RRT* (SI-RRT*) that finds a collision-free trajectory for individual robots. The high level can use any method that can resolve inter-robot conflicts where we employ two representative methods that are Prioritized Planning (SI-CPP) and Conflict Based Search (SI-CCBS). Experimental results show that SI-RRT* can quickly find a high-quality solution with a few samples. SI-CPP exhibits improved scalability while SI-CCBS produces higher-quality solutions compared to the state-of-the-art planners for continuous space.