Bridging the Gap Between Centralised and Decentralised Multi-Agent Pathfinding

Multi-agent pathfinding is a challenging problem with many important real-life applications. Despite its completeness and solution solution optimality guarantees, a global search such as centralised A* has little practical value due to its exponential state space. Scalability to larger problems has been achieved with decentralized approaches, which decompose an initial problem into a series of searches. Even though their CPU and memory requirements are significantly lower, existing decentralized methods are incomplete and provide no criteria to distinguish between problems that can successfully be solved and problems where such algorithms fail. Further, no guarantees are given with respect to the running time, the memory requirements, and the quality of the computed solutions. Addressing such limitations is the central motivation for our recent and current work on identifying a tractable class of problems and developing an algorithm that is complete on this class of problems, with guarantees of low-polynomial running time, memory requirements and solution length.