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

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

11 Citations (Scopus)

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 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)
Pages1289-1296
Number of pages8
ISBN (Electronic)9780999241141
DOIs
Publication statusPublished - 2019
EventInternational Joint Conference on Artificial Intelligence 2019 - Macao, China
Duration: 10 Aug 201916 Aug 2019
Conference number: 28th
https://ijcai19.org/
https://www.ijcai.org/proceedings/2019/ (Proceedings)

Conference

ConferenceInternational Joint Conference on Artificial Intelligence 2019
Abbreviated titleIJCAI 2019
CountryChina
CityMacao
Period10/08/1916/08/19
Internet address

Keywords

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

Cite this