New valid inequalities in branch-and-cut-and-price for Multi-agent Path Finding

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

3 Citations (Scopus)

Abstract

BCP, a state-of-the-art algorithm for optimal Multi-agent Path Finding, uses the branch-and-cut-and-price framework to decompose the problem into (1) a master problem that selects a set of collision-free low-cost paths, (2) a pricing problem that adds lower-cost paths to the master problem, (3) separation problems that resolve various kinds of conflicts in the master problem, and (4) branching rules that split the nodes in the high-level branch-and-bound search tree. This paper focuses on the separation aspects of the decomposition by introducing five new classes of fractional conflicts and valid inequalities that remove these conflicts to tighten the linear programming relaxation in the master problem. Experimental results on 12820 instances across 16 maps indicate that including the five families of inequalities allows BCP to solve an additional 585 instances, optimize the same instances 41% faster, and solve 2068 more instances than CBSH-RM and 157 more than Lazy CBS.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Conference on Automated Planning and Scheduling
EditorsJ. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, Shirin Sohrabi
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages184-192
Number of pages9
ISBN (Electronic)9781577358244
Publication statusPublished - 1 Jun 2020
EventInternational Conference on Automated Planning and Scheduling 2020 - Nancy, France
Duration: 26 Oct 202030 Oct 2020
Conference number: 30th
https://aaai.org/ojs/index.php/ICAPS/issue/view/263 (Proceedings)
https://icaps20.icaps-conference.org (Website)

Publication series

NameProceedings International Conference on Automated Planning and Scheduling, ICAPS
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume30
ISSN (Print)2334-0835

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2020
Abbreviated titleICAPS 2020
Country/TerritoryFrance
CityNancy
Period26/10/2030/10/20
Internet address

Cite this