協調型マルチエージェント経路探索:経路計画と衝突回避を超えて
Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance
エージェント群が衝突を避けつつ協調タスクを遂行するCo-MAPF問題を定式化し、協調計画を経路計画から分離したCo-CBSアルゴリズムで最適解を求める手法を提案した。
著者: Nir Greshler, Ofir Gordon, Oren Salzman, Nahum Shimkin
分類: cs.MA, cs.AI, cs.RO
原文アブストラクト
We introduce the Cooperative Multi-Agent Path Finding (Co-MAPF) problem, an extension to the classical MAPF problem, where cooperative behavior is incorporated. In this setting, a group of autonomous agents operate in a shared environment and have to complete cooperative tasks while avoiding collisions with the other agents in the group. This extension naturally models many real-world applications, where groups of agents are required to collaborate in order to complete a given task. To this end, we formalize the Co-MAPF problem and introduce Cooperative Conflict-Based Search (Co-CBS), a CBS-based algorithm for solving the problem optimally for a wide set of Co-MAPF problems. Co-CBS uses a cooperation-planning module integrated into CBS such that cooperation planning is decoupled from path planning. Finally, we present empirical results on several MAPF benchmarks demonstrating our algorithm's properties.
