From Feasibility Tests to Path Planners for Multi-Agent Pathfinding

TitleFrom Feasibility Tests to Path Planners for Multi-Agent Pathfinding
Publication TypeConference Paper
Year of Publication2013
AuthorsKrontiris, A, Luna, R, Bekris, KE
Conference NameSymposium on Combinatorial Search (SoCS - 2013)
Date Published07/2013
Conference LocationLeavenworth, 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.

Refereed DesignationRefereed