Symmetry Breaking for k-Robust Multi-Agent Path Finding
Keywords:Heuristic Search, Motion and Path Planning, Multiagent Planning
AbstractDuring 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.
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. https://doi.org/10.1609/aaai.v35i14.17456
AAAI Technical Track on Search and Optimization