多机器人快速运动规划：采样和搜索相结合 (Quick Multi-Robot Motion Planning by Combining Sampling and Search)

We propose a novel algorithm to solve multi-robot motion planning (MRMP) rapidly, called Simultaneous Sampling-and-Search Planning (SSSP). Conventional MRMP studies mostly take the form of two-phase planning that constructs roadmaps and then finds inter-robot collision-free paths on those roadmaps. In contrast, SSSP simultaneously performs roadmap construction and collision-free pathfinding. This is realized by uniting techniques of single-robot sampling-based motion planning and search techniques of multi-agent pathfinding on discretized spaces. Doing so builds the small search space, leading to quick MRMP. SSSP ensures finding a solution eventually if exists. Our empirical evaluations in various scenarios demonstrate that SSSP significantly outperforms standard approaches to MRMP, i.e., solving more problem instances much faster. We also applied SSSP to planning for 32 ground robots in a dense situation.

翻译：我们提出了一种快速解决多机器人运动规划问题的新算法，称为“同时采样和搜索规划”（SSSP）。传统的多机器人运动规划主要采用两阶段规划的形式，即构建路线图，然后在这些路线图上查找机器人之间无冲突的路径。相比之下，SSSP同时进行路线图构建和无冲突路径规划。这是通过将单机器人采样式运动规划技术和离散空间上多智能体路径查找的搜索技术结合起来实现的。这样做可以建立较小的搜索空间，从而实现快速多机器人运动规划。SSSP确保最终找到解决方案，如果存在的话。我们在各种场景下进行了实证评估，证明SSSP显著优于标准的多机器人运动规划方法，即更快地解决更多的问题实例。我们还将SSSP应用于32个地面机器人在密集情况下的规划。