Scalable cooperative multi-agent pathfinding with tractability and completeness guarantees

Abstract

Pathfinding is the technique of finding a sequence of moves, forming a continuous path, to reach a goal. Multi-agent pathfinding is a challenging problem with numerous important applications, including robotics, logistics, military operations planning, disaster rescue, and computer games. Running a systematic centralised search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the number of states grows exponentially in the number of mobile units. In addition to the inherent difficulty of the problem, many real-life applications require solutions to be computed in real time, using limited CPU and memory resources. Decoupled approaches (where paths are planned individually for each unit) such as the successful WHCA* algorithm, decompose the initial problem into a series of smaller searches, significantly improving speed and scalability but at the expense of completeness. This thesis addresses the important issues in multi-agent pathfinding in concert, including tractability, completeness, scalability, solution quality, and efficiency. We first present FAR, which is empirically shown to run significantly faster than WHCA* on grid maps, using much less memory, and scaling up to problems with more mobile units. Like WHCA*, FAR is incomplete, and does not tell in advance whether it would succeed in finding a solution to a given instance, nor does it provide guarantees with respect to the total running time or solution quality. To overcome such limitations, we introduce MAPP, a tractable algorithm on undirected graphs. We present a basic version and several extensions. All versions have low-polynomial worst-case upper bounds on the running time, memory, and solution length. Even though all versions are incomplete in the general case, each provides efficiently computable formal guarantees on problems it can solve. For each version, we discuss the algorithm's completeness with respect to clearly defined subclasses of instances. We believe that this was the first study that formalises restrictions to obtain a tractable class of multi-agent pathfinding problems. Experiments were run on grid maps extracted from a popular commercial computer game called BALDUR'S GATE, with uniformly randomly generated start and target locations for 100-2000 mobile units. On average, MAPP is 10% faster than WHCA* (and significantly faster when reusing data across instances on the same map), while producing solutions of similar lengths. Using lower bounds from a relaxed problem, we also show that MAPP's solutions have a reasonable quality when solving significantly larger multi-agent pathfinding problems than can be tractably handled using optimal algorithms. For example, MAPP's total travel distance is on average 76% longer than that of the relaxed problem where units are allowed to pass through each other. Out of the three algorithms, FAR is the fastest running, and also gives the shortest solutions. Nonetheless, MAPP has the advantages of providing completeness guarantees and low- polynomial upper bounds on resources required, as well as being the clear winner in scalability and success ratio, solving 99.98% of units and fully solving 24.7-37.6% more instances than FAR and WHCA*, establishing a new benchmark in this area. -- provided by Candidate. Show more