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.

本文介绍了多机器人路径规划问题中考虑异常情况的 k-Robust Conflict-Based Search 算法，以及引入对 k-robust 规划特定的对称性约束可以有效地找到冲突代理的兼容和最优路径，在多个领域中的应用效果较好，包括传统的 MAPF 基准测试，自动化仓库领域和最近推出 Flatland 挑战的铁路领域。

k - 强韧多智能体路径规划中的对称性破缺

Symmetry Breaking for k-Robust Multi-Agent Path Finding

We consider a common type of symmetry where we have a matrix of decision
variables with interchangeable rows and columns. A simple and efficient method
to deal with such row and column symmetry is to post symmetry breaking
constraints like DOUBLELEX and SNAKELEX. We provide a number of positive and
negative results on posting such symmetry breaking constraints. On the positive
side, we prove that we can compute in polynomial time a unique representative
of an equivalence class in a matrix model with row and column symmetry if the
number of rows (or of columns) is bounded and in a number of other special
cases. On the negative side, we show that whilst DOUBLELEX and SNAKELEX are
often effective in practice, they can leave a large number of symmetric
solutions in the worst case. In addition, we prove that propagating DOUBLELEX
completely is NP-hard. Finally we consider how to break row, column and value
symmetry, correcting a result in the literature about the safeness of combining
different symmetry breaking constraints. We end with the first experimental
study on how much symmetry is left by DOUBLELEX and SNAKELEX on some benchmark
problems.

研究了一种对称性，提出了一种简单有效的方法处理行与列对称性矩阵模型，对该对称性下的对称性破坏约束的陈述作出了一系列正面和负面的结论，并提出了关于破坏行、列和值的对称性的快速算法，实验研究了一些基准问题中，DOUBLELEX 和 SNAKELEX 留下的对称性问题的数量。