Navigating multiple mobile units on grid maps is an NP-complete problem [4, 1] with many real-life applications. Centralized search in the combined state space of all units scales very poorly. Previous approaches that decompose the initial problem into a series of smaller searches, such as FAR [5] and WHCA* [2], can significantly improve scalability and speed. However, such methods are incomplete. They provide no guarantees with respect to the total running time, and are unable to apriori tell whether they would succeed in finding a solution to a given instance. More recent algorithms, such as MAPP [6] and BIBOX [3], are complete on well-specified subclasses of problems. They also provide low-polynomial upper bounds for the running time, the solution length and the memory requirements. However, their empirical speed and scalability, compared to incomplete methods, has been an open question. In this paper we take steps towards bridging the gap between the two categories of algorithms, combining strengths specific to each of them. We extended MAPP to improve its completeness range, solution quality, and total runtime, addressing main bottlenecks of the original algorithm. We performed the first empirical analysis of MAPP, showing that the enhanced MAPP has better success ratio and scalability than state-of-the-art incomplete algorithms, and is competitive in running times, with at most 92% longer solutions, while maintaining the theoretical properties of the original MAPP.
Paper
Full text
Scalable Multi-Agent Pathfinding on Grid Maps with Tractability and Completeness Guarantees
Semantic Scholar · Computer Science · 2010
Abstract
Navigating multiple mobile units on grid maps is an NP-complete problem [4, 1] with many real-life applications. Centralized search in the combined state space of all units scales very poorly. Previous approaches that decompose the initial problem into a series of smaller searches, such as FAR [5] and WHCA* [2], can significantly improve scalability and speed. However, such methods are incomplete. They provide no guarantees with respect to the total running time, and are unable to apriori tell whether they would succeed in finding a solution to a given instance. More recent algorithms, such as MAPP [6] and BIBOX [3], are complete on well-specified subclasses of problems. They also provide low-polynomial upper bounds for the running time, the solution length and the memory requirements. However, their empirical speed and scalability, compared to incomplete methods, has been an open question. In this paper we take steps towards bridging the gap between the two categories of algorithms, combining strengths specific to each of them. We extended MAPP to improve its completeness range, solution quality, and total runtime, addressing main bottlenecks of the original algorithm. We performed the first empirical analysis of MAPP, showing that the enhanced MAPP has better success ratio and scalability than state-of-the-art incomplete algorithms, and is competitive in running times, with at most 92% longer solutions, while maintaining the theoretical properties of the original MAPP.