Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance
This addresses path planning for groups of autonomous agents needing collaboration in shared environments, such as robotics or logistics, but is incremental as it builds on existing MAPF and CBS methods.
The paper tackles the Cooperative Multi-Agent Path Finding (Co-MAPF) problem by extending classical MAPF to include cooperative tasks, and introduces Co-CBS, an algorithm that solves it optimally for many cases with empirical validation on benchmarks.
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.