Bridging the Gap Between Centralised and Decentralised Multi-Agent Pathfinding
Ko-Hsin Cindy Wang · 2009
lem into a series of searches [Silver, 2005; Wang and Botea, 2008]. Even though their CPU and memory requirements are significantly lower, existing decentralized methods, including Silver’s and Wang and Botea’s, 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 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 [Wang and Botea, 2009]. This is the starting point of a series of studies that we have planned on investigating the theoretical properties of multi-agent path planning problems. We also address the practical issues by developing algorithms that work well in practice and that are complete for well specified classes of problems.