P-ARC: サブ問題独立性を活用した並列マルチロボット動作計画
本論文は、マルチロボット動作計画（MRMP）における適応型ロボット調整（ARC）の並列変種であるParallel ARC（P-ARC）を提案する。P-ARCは、ARCの3つの主要段階（初期個別解、衝突検出、衝突解決）それぞれに並列変種を導入し、ARCによるMRMP問題の分解が生み出す独立性を活用する。さらに、ARCとP-ARCの両方にOR並列マルチスタート戦略を適用し、ハイブリッド並列戦略OR-P-ARCを構築する。最大128台のロボットを用いた2D移動および平面マニピュレータシナリオで異なる並列戦略の影響を評価し、16CPUコアで実世界に即した大規模Pandaマルチマニピュレータチームにおいて、逐次版と比べて計画時間が約4倍高速化することを実証した。
マルチロボット動作計画（Multi-Robot Motion Planning, MRMP）は、複数のロボットが共有空間内で衝突を回避しながら経路を計算する重要な課題である。ロボットの台数が増加するにつれ、従来の逐次計画手法は計算時間の爆発的な増加に直面し、リアルタイム性が要求される応用には適さなくなる。この問題を解決するため、マルチコアプロセッサの並列計算能力を活用するアルゴリズムが注目されている。
適応型ロボット調整（Adaptive Robot Coordination, ARC）は、MRMPを3つの主要段階（初期個別解の生成、衝突検出、衝突解決）に分解する効果的な手法である。しかし、これらの段階を逐次的に実行するため、全体の効率が制限される。最新の研究であるP-ARC（Parallel ARC）は、James D. Motesらによって提案され、ARCの分解が生み出す部分問題の独立性を活用した並列戦略を導入することで、高い並列処理効率を実現する。
P-ARCは、ARCの各段階に特化した並列変種を提供する。初期個別解生成段階では、複数のロボットの経路を独立に並列計算できる。衝突検出段階では、複数のロボットペアの衝突チェックを同時に実行する。衝突解決段階では、衝突経路の調整を並行して行う。さらに、OR並列マルチスタート戦略をARCとP-ARCの両方に適用し、複数の初期解を同時に探索することで、成功率と効率を向上させるハイブリッド戦略OR-P-ARCを構築した。
評価では、2次元移動ロボットと平面マニピュレータのシナリオを用い、ロボット台数を少数から最大128台まで変化させた。実験では特に、衝突制御と各ノード間の作業負荷分散に注目した。実世界を模したPandaマルチマニピュレータ環境において、16CPUコアを使用した場合、P-ARCは逐次版ARCと比較して約4倍の計画時間短縮を達成した。これにより、大規模ロボットチームの計画が大幅に高速化され、リアルタイムでの経路再計画が可能となる。
本研究は、問題分解と並列化によって大規模ロボットシステムの計画能力を大幅に向上できることを示しており、倉庫自動化、群ロボット、多アーム協調製造などの応用が期待される。論文は2026年6月26日にarXivに投稿され（arXiv:2606.27625）、著者はJames D. Motesら3名である。対象分野はロボティクス（cs.RO）および分散並列コンピューティング（cs.DC）である。