Metraipolis › archive › dc_53170baeef2c

The Cost of Classical Multi-Agent Path Finding — arXiv:2610.10100

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.10100
License (as archived)
CC0-1.0
Archived
2026-10-08T11:02:10.993Z
SHA-256 of the archived text
b78c8e12d26bb3401add153c8fa79b8ff0ea1f745854bc65e9c552915d928737
Stable URL of this page
https://metraipolis.com/documento/dc_53170baeef2c

How to cite

The Cost of Classical Multi-Agent Path Finding — arXiv:2610.10100 — arXiv (en), https://arxiv.org/abs/2610.10100 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_53170baeef2c (Metraipolis archive dc_53170baeef2c, sha256 b78c8e12d26bb3401add153c8fa79b8ff0ea1f745854bc65e9c552915d928737)
BibTeX
@misc{dc53170baeef2c,
  title = {The Cost of Classical Multi-Agent Path Finding — arXiv:2610.10100},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10100},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_53170baeef2c; sha256 b78c8e12d26bb3401add153c8fa79b8ff0ea1f745854bc65e9c552915d928737},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10100. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Multi-Agent Path Finding (MAPF) is the problem of planning conflict-free paths for multiple agents in a shared space, each from its start to its goal. Classical MAPF has been the dominant formulation for many years, with its assumptions of discrete time and graph-based conflicts presumably easing the search for solutions. These assumptions limit the physical environments and agents for which a solution is truly collision-free, and also place an upper bound on solution quality that no algorithmic improvements can lift. This work investigates how much solution quality, and in what contexts, the classical MAPF formulation forfeits. Continuous-time MAPF (MAPF$_R$) relaxes these assumptions, making it a natural counter-formulation to compare against across various agent counts and sizes, and graph connectedness, topologies, and resolutions. We find that continuous time and agent shape consideration are worth relatively little on their own; their value comes from enabling an expanded range of move actions, on average improving solution quality by at least $5\%$ on narrow and constrained maps and $17\%$ on maps with open spaces. In some cases, the improvements exceed $20\%$. Doubling the map resolution with classical MAPF recovers less than $3\%$, meaning that little of what is forfeited can be bought back through more compute. This work therefore provides insight on when classical MAPF is a reasonable simplification, and when MAPF$_R$ unlocks significantly higher-quality solutions.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.MA, nuovi lavori del giorno).
Categorie arXiv: Multiagent Systems (cs.MA).
Pagina del lavoro: https://arxiv.org/abs/2610.10100 — 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-08T10:09:05.139Z dalla pagina https://arxiv.org/list/cs.MA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).