Branch-and-Cut-and-Price for Multi-Agent Pathfinding
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.
Cite
Text
Lam et al. "Branch-and-Cut-and-Price for Multi-Agent Pathfinding." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/179Markdown
[Lam et al. "Branch-and-Cut-and-Price for Multi-Agent Pathfinding." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/lam2019ijcai-branch/) doi:10.24963/IJCAI.2019/179BibTeX
@inproceedings{lam2019ijcai-branch,
title = {{Branch-and-Cut-and-Price for Multi-Agent Pathfinding}},
author = {Lam, Edward and Le Bodic, Pierre and Harabor, Daniel Damir and Stuckey, Peter J.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2019},
pages = {1289-1296},
doi = {10.24963/IJCAI.2019/179},
url = {https://mlanthology.org/ijcai/2019/lam2019ijcai-branch/}
}