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^{10^{7}}$.
翻译:多重代理路径定位( MAPF) 问题要求为在特定环境中运行的代理团队寻找一套无冲突路径。 可以说, 计算最佳解决方案的最先进的方法是基于冲突搜索( CBS ) 。 在这项工作中, 我们重新审视了 CBS 的复杂分析, 为算法运行时间提供了最坏的更紧密的界限。 我们的分析为更好地确定算法复杂程度的参数铺平了道路。 我们的分析基于两种互补方法: 在第一个方法中, 我们使用多值决定图( MDD) 的大小来约束运行时间 -- -- 一个层次图, 精密地包含两个给定的垂直之间的所有可能的单一代理路径, 具体路径长度。 在第二个方法中, 我们用新的重现关系来表达运行时间。 我们用基于功能的分析来严格约束重现。 我们用这些技术在 CBS 的复杂程度上提供了几个新的上方位。 允许我们改进现有的C- 10 标准中的许多 C- 的上位基准。