  Multi-Agent Path Finding (MAPF) is a challenging combinatorial problem that
asks us to plan collision-free paths for a team of cooperative agents. In this
work, we show that one of the reasons why MAPF is so hard to solve is due to a
phenomenon called pairwise symmetry, which occurs when two agents have many
different paths to their target locations, all of which appear promising, but
every combination of them results in a collision. We identify several classes
of pairwise symmetries and show that each one arises commonly in practice and
can produce an exponential explosion in the space of possible collision
resolutions, leading to unacceptable runtimes for current state-of-the-art
(bounded-sub)optimal MAPF algorithms. We propose a variety of reasoning
techniques that detect the symmetries efficiently as they arise and resolve
them by using specialized constraints to eliminate all permutations of pairwise
colliding paths in a single branching step. We implement these ideas in the
context of the leading optimal MAPF algorithm CBS and show that the addition of
the symmetry reasoning techniques can have a dramatic positive effect on its
performance - we report a reduction in the number of node expansions by up to
four orders of magnitude and an increase in scalability by up to thirty times.
These gains allow us to solve to optimality a variety of challenging MAPF
instances previously considered out of reach for CBS.
