Symmetry Breaking for k-Robust Multi-Agent Path Finding

Authors

  • Zhe Chen Monash University
  • Daniel D. Harabor Monash University
  • Jiaoyang Li University of Southern California
  • Peter J. Stuckey Monash University

Keywords:

Heuristic Search, Motion and Path Planning, Multiagent Planning

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.

Downloads

Published

2021-05-18

How to Cite

Chen, Z., Harabor, D. D., Li, J., & Stuckey, P. J. (2021). Symmetry Breaking for k-Robust Multi-Agent Path Finding. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12267-12274. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17456

Issue

Section

AAAI Technical Track on Search and Optimization