# Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds

arXiv: https://arxiv.org/abs/2104.08759 · HTML: https://mlsanity.com/paper/2104.08759/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 20 references that are in the map.
- First posted on arXiv 18 Apr 2021.

## Builds on (most cited first, 2 of 2)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Intractability of Optimal Multi-Robot Path Planning on Planar Graphs](https://mlsanity.com/paper/1504.02072/) (2015)

## Built on by (most cited first, 8 of 8)

- [Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance](https://mlsanity.com/paper/2105.10993/) (2021)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)
- [Leveraging Experience in Lifelong Multi-Agent Pathfinding](https://mlsanity.com/paper/2202.04382/) (2022)
- [Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids](https://mlsanity.com/paper/2305.16303/) (2023)
- [Scalable Mechanism Design for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.17044/) (2024)
- [Multi-Agent Terraforming: Efficient Multi-Agent Path Finding via Environment Manipulation](https://mlsanity.com/paper/2203.10540/) (2022)
- [On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning](https://mlsanity.com/paper/2408.09028/) (2024)
- [Multi-Agent Path Finding For Large Agents Is Intractable](https://mlsanity.com/paper/2505.10387/) (2025)

## Abstract (arXiv)

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^107.