# CBS with Continuous-Time Revisit

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2025.

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

- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)

## Abstract (arXiv)

Multi-Agent Path Finding in Continuous Time (mapfr) extends the classical MAPF problem by allowing agents to operate in continuous time. Conflict-Based Search with Continuous Time (CCBS) is a foundational algorithm for solving mapfr optimally. In this paper, we revisit the theoretical claims of CCBS and show the algorithm is incomplete, due to an uncountably infinite state space created by continuous wait durations. Through theoretical analysis and counter-examples, we examine the inherent challenges of extending existing MAPF solvers to address mapfr while preserving optimality guarantees. By restricting waiting duration to fixed amounts, we identify a related sub-problem on graphs, mapfrdt which we show is optimally solvable, including by CCBS. It remains an open question whether similar models exist for mapfrct, a generalised version of mapfrdt that allows arbitrary wait times, and mapfrcs, which further allows arbitrary movements in continuous space.