M.Sc Thesis


M.Sc StudentGreshler Nir
SubjectCooperative Multi-Agent Path Finding
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Nahum Shimkin
DR. Oren Salzman
Full Thesis textFull thesis text - English Version


Abstract

In this research, we introduce and study the Cooperative Multi-Agent Path Finding (Co-MAPF) problem, an extension to the classical MAPF problem, where cooperative behavior is explicitly incorporated. The classical MAPF problem deals with a group of agents that move in a shared environment. This problem is inherently cooperative, since each agent has to arrive at a goal location, without colliding with other agents in the group.

However, in many real-world applications, agents that operate in a shared environment are often heterogeneous and may have a different set of abilities and restrictions. Therefore, in the Co-MAPF framework, achieving goals and completing tasks may not depend only on avoiding collisions between agents, but also on actively coordinating their actions. Simply put, we may want agents not just to "not interrupt" each other, but also help each other achieve their goals. We term this a truly cooperative setting.

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. To complete cooperative tasks, agents must collaborate and coordinate their high-level decisions. This introduces a significant computational challenge on top of path planning and collision avoidance. 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. We suggest two improvements to Co-CBS that significantly improve its success rate.

We also address the Task Assignment (TA) problem, which is NP-hard in this context. We propose to formulate the TA problem as a Multi-Index Assignment Problem (MIAP), use an off-the-shelf algorithm to solve it, and show how to integrate in into Co-CBS.

Finally, we present empirical results on several MAPF benchmarks demonstrating the properties of several variants of Co-CBS.