Metraipolis › archive › dc_2c530144efdf
LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions — arXiv:2611.10363
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.10363
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-10T18:40:14.283Z
- SHA-256 of the archived text
c9b042d7e70311e82969814b711d65017124cb4d4621af960d0db0675359e620- Stable URL of this page
https://metraipolis.com/documento/dc_2c530144efdf
How to cite
LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions — arXiv:2611.10363 — arXiv (en), https://arxiv.org/abs/2611.10363 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2c530144efdf (Metraipolis archive dc_2c530144efdf, sha256 c9b042d7e70311e82969814b711d65017124cb4d4621af960d0db0675359e620)
BibTeX
@misc{dc2c530144efdf,
title = {LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions — arXiv:2611.10363},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.10363},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2c530144efdf; sha256 c9b042d7e70311e82969814b711d65017124cb4d4621af960d0db0675359e620},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.10363. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit the use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-based Planning (LSRP) was proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSRP* and test it against several baselines with up to 1000 agents on various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.MA, nuovi lavori del giorno). Categorie arXiv: Robotics (cs.RO) ; Artificial Intelligence (cs.AI); Multiagent Systems (cs.MA). Pagina del lavoro: https://arxiv.org/abs/2611.10363 — 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-11-10T18:37:22.457Z dalla pagina https://arxiv.org/list/cs.MA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).