Technical Report MSC-2021-35

TR#:MSC-2021-35
Class:MSC
Title: Toward Understanding the Hardness of Multi-Agent Path Finding
Authors: Ofir Gordon
Supervisors: Oren Salzman
PDFCurrently accessibly only within the Technion network
Abstract: The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. This problem has attracted high interest among the artificial intelligence and robotics community in recent years. There exists different real-world applications which can be modeled and developed based on the theory behind the MAPF problem.

Even though planning an optimal path for a single agent can be done efficiently, solving the MAPF problem optimally is computationally intractable in the general case. Nevertheless, there are several algorithmic approaches for solving the MAPF problem optimally that are able to solve non-trivial problem instances effectively.

Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). Although this approach and its many improvements allow solving non-trivial instances of the problem in practice, CBS sometimes fails to solve MAPF instances even when allowed long periods of run-time. Interestingly, such instances do not exhibit notable differences from easy ones. That is, there is still a significant lack of understanding in the community regarding the causes for the hardness of the problem and the ability of different solvers to cope with it.

In this work, we address this issue and try to shed light on the main aspects that affect the problem’s hardness. We do so by revisiting the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case.

Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity. Our analysis is based on two complementary approaches: In the first approach, we bound the run-time using the size of a Multi-valued Decision Diagram MDD)—a layered graph that compactly contains all possible single-agent paths between two given vertices for a specific path length. In the second approach, we express the run-time by a novel recurrence relation which bounds the algorithm's complexity. We use a generating function-based analysis in order to tightly bound the recurrence.

This analysis provides new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the run-time of CBS for many cases. For example, on a set of common benchmarks, we improve the upper bound by a factor of at least 2 to the power of 10 to the power of 6. We also provide an extended discussion, which hopefully will allow to extend this line of research, toward improving our understanding of the MAPF problem's hardness.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2021/MSC/MSC-2021-35), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion
admin