Metraipolis › archive › dc_dca07b10715d
AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding — arXiv:2608.08175
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.08175
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T06:49:21.902Z
- SHA-256 of the archived text
b52eaf0a341c1d2be48efa40610639d70c07ed9bee0a517e8b54a9b22555592b- Stable URL of this page
https://metraipolis.com/documento/dc_dca07b10715d
How to cite
AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding — arXiv:2608.08175 — arXiv (en), https://arxiv.org/abs/2608.08175 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dca07b10715d (Metraipolis archive dc_dca07b10715d, sha256 b52eaf0a341c1d2be48efa40610639d70c07ed9bee0a517e8b54a9b22555592b)
BibTeX
@misc{dcdca07b10715d,
title = {AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding — arXiv:2608.08175},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.08175},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dca07b10715d; sha256 b52eaf0a341c1d2be48efa40610639d70c07ed9bee0a517e8b54a9b22555592b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.08175. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Many research fields share a common structure: a set of agents, each pursuing its own goal, whose actions must be coordinated so that no two of them conflict. Multi-Agent Path Finding (MAPF) is a concrete instance of this structure, with applications from warehouses to road traffic and airports. Much of MAPF research assumes discrete time, circular agents sharing one spatial graph, a single goal per agent, and that an agent must remain at its goal once reached, precluding heterogeneous fleets, non-geometric conflicts, task sequences, and agents that move on after completing them. We generalise the MAPF formulation to lift these assumptions, and present Anytime-Optimal Continuous-time Conflict-Based Search (AOC-CBS), an exact and solution-complete solver for it. AOC-CBS guarantees the eventual return of an optimal solution, while reporting an incumbent with a known optimality gap upper bound throughout its runtime; it is configurable with a portfolio of repair functions, one of which we introduce (Tier-Prioritized Safe Interval Path Planning), and can exploit multiple processor cores. We demonstrate AOC-CBS on a mixed fleet of non-convex agents moving along smooth, kinodynamically feasible trajectories. Preliminary experiments against the exact solver OC-CBS, on well-known benchmarks and roadmaps we sample from them, show AOC-CBS is comparable at finding optimal solutions while extending scalability from the tens to the hundreds of agents when a bounded optimality gap is accepted. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-11 in cs.MA). Categorie arXiv: Multiagent Systems (cs.MA). Pagina del lavoro: https://arxiv.org/abs/2608.08175 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T06:45:31.682Z dalla pagina https://arxiv.org/catchup/cs.MA/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).