P-ARC: Exploiting Subproblem Independence for Parallel Multi-Robot Motion Planning

doi:10.1109/lra.2026.3730392

Return

P-ARC: Exploiting Subproblem Independence for Parallel Multi-Robot Motion Planning

2026-09-02

James Motes

Marco Morales

Nancy M. Amato

DOI：10.1109/lra.2026.3730392

Original

Original request for help

Save

Abstract

En 中文

This letter presents Parallel ARC (P-ARC), a parallel formulation of the Adaptive Robot Coordination (ARC) approach to multi-robot motion planning (MRMP) which exploits subproblem independence. ARC’s adaptive (de)composition of the multi-robot planning space exposes parallelism: single-robot paths are solved independently and iterative conflict detection and resolution create locally coupled subproblems. While distributing single-robot queries is straightforward, not all conflicts are independent, so P-ARC proposes robot-disjoint conflict batches which enable efficient distributed detection and concurrent repair. Additionally, OR-multi-start strategies are employed at the global and subproblem resolution levels, creating a hybrid parallel strategy OR-P-ARC. We evaluate the methods against sequential ARC, multi-start OR-ARC, and coupled and prioritized parallel baselines on controlled 2D mobile-robot and planar-manipulator problems with up to 256 robots and 3D Panda manipulator problems with up to 16 robots. On 16-robot Panda tasks, with 16 workers, P-ARC and OR-P-ARC achieve 4 × and 3 × speedups and planning times of 1.1 s and 1.5 s, respectively.

Keywords:

Motion and path planning

multi-robot systems

parallel robots