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

Authors

  • Nir Greshler Viterbi Faculty of Electrical & Computer Engineering, Technion, Haifa, Israel
  • Ofir Gordon Department of Computer Science, Technion, Haifa, Israel
  • Oren Salzman Department of Computer Science, Technion, Haifa, Israel
  • Nahum Shimkin Viterbi Faculty of Electrical & Computer Engineering, Technion, Haifa, Israel

Keywords:

Search In Robotics, Problem Solving Using Search, Real-life Applications

Abstract

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.

Downloads

Published

2021-07-21