Branch-and-cut-and-price for multi-agent pathfinding

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

32 Citations (Scopus)


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 languageEnglish
Title of host publicationProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
EditorsSarit Kraus
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages8
ISBN (Electronic)9780999241141
Publication statusPublished - 2019
EventInternational Joint Conference on Artificial Intelligence 2019 - Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28th (Proceedings)


ConferenceInternational Joint Conference on Artificial Intelligence 2019
Abbreviated titleIJCAI 2019
Internet address


  • Heuristic Search
  • Combinatorial Search and Optimisation
  • Distributed
  • Multi-agent Planning

Cite this