Optimization Online


Branch-and-Cut-and-Price for Multi-Agent Pathfinding

Edward Lam(Edward.Lam***at***monash.edu)
Pierre Le Bodic(Pierre.LeBodic***at***monash.edu)
Daniel Harabor(Daniel.Harabor***at***monash.edu)
Peter J. Stuckey(Peter.Stuckey***at***monash.edu)

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: multi-agent, planning, artificial intelligence, shortest path, column generation

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming (0-1 Programming )

Category 3: Applications -- OR and Management Sciences (Transportation )

Citation: (IJCAI 2019) Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence Main track. Pages 1289-1296. https://doi.org/10.24963/ijcai.2019/179

Download: [PDF]

Entry Submitted: 08/20/2019
Entry Accepted: 09/03/2019
Entry Last Modified: 08/20/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society