A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding

Authors

  • Mokhtar Khorshid University of Alberta
  • Robert Holte University of Alberta
  • Nathan Sturtevant University of Denver

DOI:

https://doi.org/10.1609/socs.v2i1.18205

Keywords:

multi-agent, pathfinding, cooperative, tree, search

Abstract

Multi-agent pathfinding, where multiple agents must travel to 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 linear-time 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 multi-agent pathfinding.

Downloads

Published

2021-08-19