# Optimal Multi-Agent Path Finding in Continuous Time

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

## Key facts

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

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

- [Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2603.18866/) (2026)

## Abstract (arXiv)

Continuous-time Conflict Based Search (CCBS) has been widely used as an exact baseline for Continuous-time Multi-Agent Path Finding (MAPFR), and its correctness guarantees underpin a range of continuation methods built on top of it. Recent work, however, has shown that CCBS's guarantees of exactness and solution completeness do not in fact hold: optimal solutions can be removed from the search, causing the algorithm to return suboptimal solutions. This paper establishes sufficient conditions for exactness and solution completeness in CCBS-style algorithms, and introduces Optimal Continuous-time Conflict-Based Search (OC-CBS) which satisfies these conditions. OC-CBS therefore guarantees an optimal solution on every solvable MAPFR instance. Experiments on benchmark problems show that OC-CBS remains competitive with CCBS in runtime while providing formal correctness guarantees. Because OC-CBS is a drop-in replacement for CCBS, it also restores the theoretical guarantees of existing methods that relied on CCBS's now-invalidated correctness. Finally, the framework and correctness criteria offer a general foundation for analyzing and designing future exact MAPFR solvers.