Recent Changes - Search:


Home Page
MAPF Info MAPF News Mailing List Meetings Publications Researchers Benchmarks Software Apps Tutorials Class Projects

Publication

O. Gordon,, Y. Filmus, and O. Salzman. Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds. In Proceedings of the Symposium on Combinatorial Search (SoCS), pages 64-72, 2021.


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. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit 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 which compactly contains all possible single-agent paths between two given vertices for a specific path length. In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence. Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running 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,000,000.


Download the paper in pdf.

Edit - History - Print - Recent Changes - Search
Page last modified on October 06, 2024, at 07:17 AM