Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Extended Abstracts

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.

10.1609/socs.v12i1.18574