论文标题
通过组合采样和搜索来快速多机器人运动计划
Quick Multi-Robot Motion Planning by Combining Sampling and Search
论文作者
论文摘要
我们提出了一种新颖的算法来迅速解决多机器人运动计划（MRMP），称为同时采样和搜索计划（SSSP）。常规的MRMP研究主要采用两相规划的形式，该计划构建了路线图，然后在这些路线图上找到无机间碰撞路径。相比之下，SSSP同时执行路线图构造和无冲突的路径。这是通过将基于单机器人采样的运动计划和搜索技术在离散空间上的多代理探路方面的搜索技术实现的。这样做可以建立小搜索空间，从而导致MRMP快速。 SSSP确保最终找到解决方案（如果存在）。在各种情况下，我们的经验评估表明，SSSP明显优于MRMP的标准方法，即更快地解决更多问题实例。我们还将SSSP应用于在密集情况下计划32个地面机器人。
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.
