Optimal Multi-Agent Path Finding in Continuous Time
arXiv:2508.16410v3 Announce Type: replace-cross Abstract: 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
Overview
arXiv:2508.16410v3 Announce Type: replace-cross Abstract: 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.
Source
Originally published at arxiv.org.
Related Articles
- PhysX-CoT: Structured Physical Reasoning from a Single Image to Simulation-Ready 3D Assets
- Anchor-Based AI Approach for Pre-Crash Object Detection Utilizing Micro-Doppler Signatures in Automotive Radar
- Removing Infrastructure Barriers in Human-Robot Collaboration Through Wireless Reconfigurable Cells
Source: https://arxiv.org/abs/2508.16410
