提出并行化多机器人路径规划方法，显著提升大规模场景下的计算效率。
P-ARC: Exploiting Subproblem Independence for Parallel Multi-Robot Motion Planning
- 通过拆分独立子问题并批量处理冲突，实现高效并行规划。
- 在16个机械臂任务中，相比串行方法提速最高达6.67倍。
- 适合需要快速响应的大规模多机器人协同场景。
本文提出并行自适应机器人协调（P-ARC）方法，用于多机器人运动规划（MRMP），利用子问题间的独立性实现并行化。传统自适应机器人协调（ARC）通过动态分解规划空间暴露并行性：单机器人路径独立求解，通过迭代冲突检测与修复形成局部耦合的子问题。虽然单机器人查询的分配简单，但并非所有冲突可独立处理，因此P-ARC引入机器人不交集的冲突批次，支持高效分布式检测与并发修复。此外，在全局与子问题修复层级采用OR-multi-start策略，形成混合并行策略OR-P-ARC。我们在可控的二维移动机器人和平面机械臂任务中评估该方法，最多支持256个机器人；在3D Panda机械臂任务中最多支持16个机器人。在16机器人Panda任务中，使用16个工作节点时，P-ARC和OR-P-ARC分别实现3.48倍和6.67倍的加速比。
原文摘要 · Abstract (English)
This paper 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 trivial, 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 3.48X and 6.67X speedups, respectively.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。