# On the Completeness of Conflict-Based Search: Temporally-Relative Duplicate Pruning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 25 references that are in the map.
- First posted on arXiv 16 Aug 2024.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm](https://mlsanity.com/paper/1703.04159/) (2017)
- [Improving Continuous-time Conflict Based Search](https://mlsanity.com/paper/2101.09723/) (2021)
- [Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds](https://mlsanity.com/paper/2104.08759/) (2021)

## Abstract (arXiv)

Conflict-Based Search (CBS) algorithm for the multi-agent pathfinding (MAPF) problem is that it is incomplete for problems which have no solution; if no mitigating procedure is run in parallel, CBS will run forever when given an unsolvable problem instance. In this work, we introduce Temporally-Relative Duplicate Pruning (TRDP), a technique for duplicate detection and removal in both classic and continuous-time MAPF domains. TRDP is a simple procedure which closes the long-standing theoretic loophole of incompleteness for CBS by detecting and avoiding the expansion of duplicate states. TRDP is shown both theoretically and empirically to ensure termination without a significant impact on runtime in the majority of problem instances. In certain cases, TRDP is shown to increase performance significantly