Symmetry breaking for k-Robust Multi-Agent Path Finding

Zhe Chen, Daniel Harabor, Jiaoyang Li, Peter J. Stuckey

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

1 Citation (Scopus)

Abstract

During Multi-Agent Path Finding (MAPF) problems, agents can be delayed by unexpected events. To address such situations recent work describes k-Robust Conflict-Based Search (k-CBS): an algorithm that produces a coordinated and collision-free plan that is robust for up to k delays for any agent. In this work we introduce a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of colliding agents. We give a thorough description of the new constraints and report large improvements to success rate in a range of domains including: (i) classic MAPF benchmarks, (ii) automated warehouse domains, and (iii) on maps from the 2019 Flatland Challenge, a recently introduced railway domain where k-robust planning can be fruitfully applied to schedule trains.

Original languageEnglish
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence, AAAI-21
EditorsKevin Leyton-Brown, Mausam
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages12267-12274
Number of pages8
ISBN (Electronic)9781713835974
Publication statusPublished - 2021
EventAAAI Conference on Artificial Intelligence 2021 - Online, United States of America
Duration: 2 Feb 20219 Feb 2021
Conference number: 35th
https://aaai.org/Conferences/AAAI-21/ (Website)

Publication series

Name35th AAAI Conference on Artificial Intelligence, AAAI 2021
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume14A
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence 2021
Abbreviated titleAAAI 2021
Country/TerritoryUnited States of America
Period2/02/219/02/21
Internet address

Keywords

  • Heuristic Search
  • motion and path planning
  • Multiagent Planning

Cite this