Recent Changes - Search:


Home Page
MAPF Info
MAPF News
Mailing List
Meetings
Publications
Researchers
Benchmarks
Software
Apps
Tutorials
Class Projects

[Internal]

Publication

Z. Chen, D. Harabor, J. Li and P. Stuckey. Symmetry Breaking for k-Robust Multi-Agent Path Finding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 12267-12274, 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 introduce 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.


Download the paper in pdf.

Edit - History - Print - Recent Changes - Search
Page last modified on January 23, 2025, at 09:24 AM