  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}}$.
