{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T01:56:08Z","timestamp":1794362168709,"version":"4.9.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":[[2019,8]]},"abstract":"<jats:p>There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches using Branch-and-Cut-and-Price, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.<\/jats:p>","DOI":"10.24963\/ijcai.2019\/179","type":"proceedings-article","created":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:46:05Z","timestamp":1564285565000},"page":"1289-1296","source":"Crossref","is-referenced-by-count":25,"title":["Branch-and-Cut-and-Price for Multi-Agent Pathfinding"],"prefix":"10.24963","author":[{"given":"Edward","family":"Lam","sequence":"first","affiliation":[{"name":"Monash University, Melbourne, Australia"},{"name":"CSIRO Data61, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Le Bodic","sequence":"additional","affiliation":[{"name":"Monash University, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel D.","family":"Harabor","sequence":"additional","affiliation":[{"name":"Monash University, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter J.","family":"Stuckey","sequence":"additional","affiliation":[{"name":"Monash University, Melbourne, Australia"},{"name":"CSIRO Data61, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}","theme":"Artificial Intelligence","location":"Macao, China","acronym":"IJCAI-2019","number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2019,8,10]]},"end":{"date-parts":[[2019,8,16]]}},"container-title":["Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2019,7,28]],"date-time":"2019-07-28T03:47:23Z","timestamp":1564285643000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2019\/179"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2019\/179","relation":{},"subject":[],"published":{"date-parts":[[2019,8]]}}}