Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
  Multi-Agent Path Finding (MAPF) is an NP-hard problem well studied in
artificial intelligence and robotics. It has many real-world applications for
which existing MAPF solvers use various heuristics. However, these solvers are
deterministic and perform poorly on "hard" instances typically characterized by
many agents interfering with each other in a small region. In this paper, we
enhance MAPF solvers with randomization and observe that they exhibit
heavy-tailed distributions of runtimes on hard instances. This leads us to
develop simple rapid randomized restart (RRR) strategies with the intuition
that, given a hard instance, multiple short runs have a better chance of
solving it compared to one long run. We validate this intuition through
experiments and show that our RRR strategies indeed boost the performance of
state-of-the-art MAPF solvers such as iECBS and M*.
