From Feasibility Tests to Path Planners for Multi-Agent Pathfinding
|Title||From Feasibility Tests to Path Planners for Multi-Agent Pathfinding|
|Publication Type||Conference Paper|
|Year of Publication||2013|
|Authors||Krontiris, A, Luna, R, Bekris, KE|
|Conference Name||Symposium on Combinatorial Search (SoCS - 2013)|
|Conference Location||Leavenworth, WA, USA|
Multi-agent pathfinding is an important challenge that relates to combinatorial search and has many applications, including warehouse management, robotics and computer games. Finding an optimal solution is NP-hard and raises scalability issues for optimal solvers. Interestingly, however, it is possible to check in linear time if an instance is solvable or not. 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. This work first describes a path planner that is inspired by linear-time feasibility tests for multi-agent pathfinding. 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.