MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability
  and Completeness Guarantees
  Multi-agent path planning is a challenging problem with numerous real-life
applications. Running a centralized search such as A* in the combined state
space of all units is complete and cost-optimal, but scales poorly, as the
state space size is exponential in the number of mobile units. Traditional
decentralized approaches, such as FAR and WHCA*, are faster and more scalable,
being based on problem decomposition. However, such methods are incomplete and
provide no guarantees with respect to the running time or the solution quality.
They are not necessarily able to tell in a reasonable time whether they would
succeed in finding a solution to a given instance. We introduce MAPP, a
tractable algorithm for multi-agent path planning on undirected graphs. We
present a basic version and several extensions. They have low-polynomial
worst-case upper bounds for the running time, the memory requirements, and the
length of solutions. Even though all algorithmic versions are incomplete in the
general case, each provides formal guarantees on problems it can solve. For
each version, we discuss the algorithms completeness with respect to clearly
defined subclasses of instances. Experiments were run on realistic game grid
maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the
percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably
solvable during the first stage of plan computation. Parts of MAPPs computation
can be re-used across instances on the same map. Speed-wise, MAPP is
competitive or significantly faster than WHCA*, depending on whether MAPP
performs all computations from scratch. When data that MAPP can re-use are
preprocessed offline and readily available, MAPP is slower than the very fast
FAR algorithm by a factor of 2.18 on average. MAPPs solutions are on average
20% longer than FARs solutions and 7--31% longer than WHCA*s solutions.
