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 | California USA |
| Publisher | International Joint Conferences on Artificial Intelligence |
| 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/ |
Conference
| Conference | International Joint Conference on Artificial Intelligence 2019 |
|---|---|
| Abbreviated title | IJCAI-19 |
| Country | China |
| City | Macao |
| Period | 10/08/19 → 16/08/19 |
| Internet address |
Keywords
- Heuristic Search
- Combinatorial Search and Optimisation
- Distributed
- Multi-agent Planning
Cite this
}
Branch-and-cut-and-price for multi-agent pathfinding. / Lam, Edward; Bodic, Pierre Le; Harabor, Daniel D.; Stuckey, Peter J.
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. ed. / Sarit Kraus. California USA : International Joint Conferences on Artificial Intelligence, 2019. p. 1289-1296.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - Branch-and-cut-and-price for multi-agent pathfinding
AU - Lam, Edward
AU - Bodic, Pierre Le
AU - Harabor, Daniel D.
AU - Stuckey, Peter J.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - Heuristic Search
KW - Combinatorial Search and Optimisation
KW - Distributed
KW - Multi-agent Planning
UR - http://www.scopus.com/inward/record.url?scp=85074939146&partnerID=8YFLogxK
U2 - 10.24963/ijcai.2019/179
DO - 10.24963/ijcai.2019/179
M3 - Conference Paper
SP - 1289
EP - 1296
BT - Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
A2 - Kraus, Sarit
PB - International Joint Conferences on Artificial Intelligence
CY - California USA
ER -