Symmetry Breaking for k-Robust Multi-Agent Path Finding
Zhe Chen, Daniel D. Harabor, Jiaoyang Li, Peter J. Stuckey
Abstract
During Multi-Agent Path Finding (MAPF) problems, agentscan be delayed by unexpected events. To address suchsituations recent work describes k-Robust Conflict-BasedSearch (k-CBS): an algorithm that produces coordinated andcollision-free plan that is robust for up tokdelays. In thiswork we introducing a variety of pairwise symmetry break-ing constraints, specific tok-robust planning, that can effi-ciently find compatible and optimal paths for pairs of con-flicting agents. We give a thorough description of the newconstraints and report large improvements to success rate ina range of domains including: (i) classic MAPF benchmarks;(ii) automated warehouse domains and; (iii) on maps fromthe 2019 Flatland Challenge, a recently introduced railwaydomain wherek-robust planning can be fruitfully applied toschedule trains.
BibTeX
@inproceedings{aaai2021_symmetrybreaking,
title = {Symmetry Breaking for k-Robust Multi-Agent Path Finding},
author = {Zhe Chen and Daniel D. Harabor and Jiaoyang Li and Peter J. Stuckey},
booktitle = {AAAI 2021},
year = {2021}
}