From Feasibility Tests to Path Planners for Multi-Agent Pathfinding

Abstract

Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, such as warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it takes linear time to check the feasibility of an instance. These linear-time feasibility tests can be extended to provide path planners but to the best of the authors’ knowledge no such solver has been provided for general graphs. This work first describes a path planner that is inspired by a linear-time feasibility test for multi-agent pathfinding on general graphs. Initial experiments indicated reasonable scalability but worse path quality relative to existing suboptimal solutions. This led to the development of an algorithm that achieves both efficient running time and path quality relative to the alternatives and which finds a solution on available benchmarks. The paper outlines the relation of the final method to the feasibility tests and existing suboptimal planners. Experimental results evaluate the different algorithms, including an optimal solver.