Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives

TitleMulti-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives
Publication TypeConference Paper
Year of Publication2012
AuthorsSajid, Q, Luna, R, Bekris, KE
Conference NameFifth Symposium on Combinatorial Search (SoCS)
Date Published07/2012
Conference LocationNiagara Falls, CA

Multi-agent pathfinding is a challenging combinatorial search problem that involves multiple agents moving on a graph from a set of initial nodes to a set of desired goals without inter-agent collisions. Searching the composite space of all agents has exponential complexity in the number of agents and does not scale well. Decoupled methods are more efficient but are generally incomplete. A recent development is the introduction of polynomial time algorithms utilizing single-agent primitives that provide completeness guarantees for a large class of problem instances on general graphs. One limitation of these alternatives is that the resulting solution is sequential, where only one agent moves at a time. Such solutions are of low quality when compared to methods where multiple agents can move simultaneously. Motivated by these recent developments, this paper proposes an algorithm for multi-agent pathfinding that utilizes similar single-agent primitives but allows all agents to move in parallel. The paper describes the algorithm and its desirable properties. Experimental comparisons suggest that the resulting solutions are considerably better than sequential ones, even after a post-processing parallelization step, as well as solutions returned by decoupled and coupled alternatives. The experiments also suggest excellent scalability and competitive computational performance.

Refereed DesignationRefereed