  During Multi-Agent Path Finding (MAPF) problems, agents can be delayed by
unexpected events. To address such situations recent work describes k-Robust
Conflict-BasedSearch (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 ina 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.
