Combining Safe Intervals and RRT* for Efficient Multi-Robot Path Planning in Complex Environments
<|reference_start|>Combining Safe Intervals and RRT* for Efficient Multi-Robot Path Planning in Complex Environments: In this paper, we consider the problem of Multi-Robot Path Planning (MRPP) in continuous space to find conflict-free paths. The difficulty of the problem arises from two primary factors. First, the involvement of multiple robots leads to combinatorial decision-making, which escalates the search space exponentially. Second, the continuous space presents potentially infinite states and actions. For this problem, 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 find a high-quality solution quickly with a small number of samples. SI-CPP exhibits improved scalability while SI-CCBS produces higher-quality solutions compared to the state-of-the-art planners for continuous space. Compared to the most scalable existing algorithm, SI-CPP achieves a success rate that is up to 94% higher with 100 robots while maintaining solution quality (i.e., flowtime, the sum of travel times of all robots) without significant compromise. SI-CPP also decreases the makespan up to 45%. SI-CCBS decreases the flowtime by 9% compared to the competitor, albeit exhibiting a 14% lower success rate.<|reference_end|>
@article{sim2024combining,
    title={Combining Safe Intervals and RRT* for Efficient Multi-Robot Path
  Planning in Complex Environments},
    author={Joonyeol Sim, Joonkyung Kim, Changjoo Nam},
    journal={arXiv preprint arXiv:2404.01752},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.01752},
    primaryClass={cs.RO cs.AI cs.MA}
}