{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,6]],"date-time":"2026-08-06T18:02:40Z","timestamp":1786039360471,"version":"3.56.0"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for multiple agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms that can solve large problems but usually find low-quality solutions. In this paper, we consider a third approach that combines the best of both worlds: anytime algorithms that quickly find an initial solution using efficient MAPF algorithms from the literature, even for large problems, and that subsequently improve the solution quality to near-optimal as time progresses by replanning subgroups of agents using Large Neighborhood Search. We compare our algorithm MAPF-LNS against a range of existing work and report significant gains in scalability, runtime to the initial solution, and speed of improving the solution.<\/jats:p>","DOI":"10.24963\/ijcai.2021\/568","type":"proceedings-article","created":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:00:49Z","timestamp":1628679649000},"page":"4127-4135","source":"Crossref","is-referenced-by-count":58,"title":["Anytime Multi-Agent Path Finding via Large Neighborhood Search"],"prefix":"10.24963","author":[{"given":"Jiaoyang","family":"Li","sequence":"first","affiliation":[{"name":"University of Southern California"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhe","family":"Chen","sequence":"additional","affiliation":[{"name":"Monash University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Harabor","sequence":"additional","affiliation":[{"name":"Monash University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter J.","family":"Stuckey","sequence":"additional","affiliation":[{"name":"Monash University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sven","family":"Koenig","sequence":"additional","affiliation":[{"name":"University of Southern California"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}","theme":"Artificial Intelligence","location":"Montreal, Canada","acronym":"IJCAI-2021","number":"30","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2021,8,19]]},"end":{"date-parts":[[2021,8,27]]}},"container-title":["Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2021,8,11]],"date-time":"2021-08-11T11:04:05Z","timestamp":1628679845000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2021\/568"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2021,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2021\/568","relation":{},"subject":[],"published":{"date-parts":[[2021,8]]}}}