Branch-and-cut-and-price for Multi-Agent Pathfinding

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

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 PublicationCalifornia USA
PublisherInternational Joint Conferences on Artificial Intelligence
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/

Conference

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

Keywords

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

Cite this

Lam, E., Bodic, P. L., Harabor, D. D., & Stuckey, P. J. (2019). Branch-and-cut-and-price for Multi-Agent Pathfinding. In S. Kraus (Ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (pp. 1289-1296). California USA: International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2019/179
Lam, Edward ; Bodic, Pierre Le ; Harabor, Daniel D. ; Stuckey, Peter J. / Branch-and-cut-and-price for Multi-Agent Pathfinding. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. editor / Sarit Kraus. California USA : International Joint Conferences on Artificial Intelligence, 2019. pp. 1289-1296
@inproceedings{c094b65fdb0d46edade16f4d0e1fb97f,
title = "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.",
keywords = "Heuristic Search, Combinatorial Search and Optimisation, Distributed, Multi-agent Planning",
author = "Edward Lam and Bodic, {Pierre Le} and Harabor, {Daniel D.} and Stuckey, {Peter J.}",
year = "2019",
doi = "10.24963/ijcai.2019/179",
language = "English",
pages = "1289--1296",
editor = "Kraus, {Sarit }",
booktitle = "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence",
publisher = "International Joint Conferences on Artificial Intelligence",

}

Lam, E, Bodic, PL, Harabor, DD & Stuckey, PJ 2019, Branch-and-cut-and-price for Multi-Agent Pathfinding. in S Kraus (ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence, California USA, pp. 1289-1296, International Joint Conference on Artificial Intelligence 2019, Macao, China, 10/08/19. https://doi.org/10.24963/ijcai.2019/179

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 proceedingConference PaperResearchpeer-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

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 -

Lam E, Bodic PL, Harabor DD, Stuckey PJ. Branch-and-cut-and-price for Multi-Agent Pathfinding. In Kraus S, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. California USA: International Joint Conferences on Artificial Intelligence. 2019. p. 1289-1296 https://doi.org/10.24963/ijcai.2019/179