|
Main /
PublicationM. Khorshid, R. Holte and N. Sturtevant. A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding. In Proceedings of the Symposium on Combinatorial Search (SoCS), pages 76-83, 2011. Abstract: Multi-agent pathfinding, where multiple agents must travelto their goal locations without getting stuck, has been studied in both theoretical and practical contexts, with a variety of both optimal and sub-optimal algorithms proposed for solving problems. Recent work has shown that there is a lineartime check for whether a multi-agent pathfinding problem can be solved in a tree, however this was not used to actually produce solutions. In this paper we provide a constructive proof of how to solve multi-agent pathfinding problems in a tree that culminates in a novel approach that we call the tree-based agent swapping strategy (TASS). Experimental results showed that TASS can find solutions to the multi-agent pathfinding problem on a highly crowded tree with 1000 nodes and 996 agents in less than 8 seconds. These results are far more efficient and general than existing work, suggesting that TASS is a productive line of study for multiagent pathfinding.
|