Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence |
Editors | Sarit Kraus |
Place of Publication | Marina del Rey CA USA |
Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
Pages | 1289-1296 |
Number of pages | 8 |
ISBN (Electronic) | 9780999241141 |
DOIs | |
Publication status | Published - 2019 |
Event | International Joint Conference on Artificial Intelligence 2019 - Macao, China Duration: 10 Aug 2019 → 16 Aug 2019 Conference number: 28th https://ijcai19.org/ https://www.ijcai.org/proceedings/2019/ (Proceedings) |
Conference
Conference | International Joint Conference on Artificial Intelligence 2019 |
---|---|
Abbreviated title | IJCAI 2019 |
Country/Territory | China |
City | Macao |
Period | 10/08/19 → 16/08/19 |
Internet address |
Keywords
- Heuristic Search
- Combinatorial Search and Optimisation
- Distributed
- Multi-agent Planning