P-ARC: Exploiting Subproblem Independence for Parallel Multi-Robot Motion Planning
This work addresses the computational bottleneck of multi-robot motion planning for robotics practitioners, but the improvements are incremental as they parallelize an existing method.
P-ARC parallelizes the three stages of the Adaptive Robot Coordination (ARC) approach for multi-robot motion planning, achieving up to 4X speedup over the sequential version on 16 CPU cores for large robot teams.
This paper presents Parallel ARC (P-ARC), a parallel variant of the Adaptive Robot Coordination (ARC) approach to multi-robot motion planning (MRMP). P-ARC proposes a parallel variant for each of the three main stages in ARC: initial individual solutions, conflict detection, and conflict resolution, exploiting the independence created by ARC's decomposition of the MRMP problem. Additionally, we employ an OR-parallel multi-start strategy to both ARC and P-ARC, creating a hybrid parallel strategy OR-P-ARC. We evaluate the impact of the different parallel strategies for ARC using a set of scaling 2D mobile and planar manipulator scenarios with up to 128 robots to control for conflicts and work distribution across the stages of ARC. Additionally, we demonstrate planning time speedups approaching 4X over the sequential version for large Panda multi-manipulator teams in real-world inspired scenarios when deploying 16 CPU cores.