Symmetry Breaking for k-Robust Multi-Agent Path Finding - Robotics Institute Carnegie Mellon University

Symmetry Breaking for k-Robust Multi-Agent Path Finding

Zhe Chen, Daniel Harabor, Jiaoyang Li, and Peter J. Stuckey
Conference Paper, Proceedings of 35th AAAI Conference on Artificial Intelligence (AAAI '21), pp. 12267 - 12274, February, 2021

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 coordinated and collision-free plan that is robust for up to k delays. In this work we introducing a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of conflicting 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.

BibTeX

@conference{Chen-2021-131400,
author = {Zhe Chen and Daniel Harabor and Jiaoyang Li and Peter J. Stuckey},
title = {Symmetry Breaking for k-Robust Multi-Agent Path Finding},
booktitle = {Proceedings of 35th AAAI Conference on Artificial Intelligence (AAAI '21)},
year = {2021},
month = {February},
pages = {12267 - 12274},
}