Non-Optimal Multi-Agent Pathfinding Is Solved (Since 1984)

Optimal solutions for multi-agent pathfinding problems are often too expensive to compute. For this reason, suboptimal approaches have been widely studied in the literature. Specifically, in recent years a number of efficient suboptimal algorithms that are complete for certain subclasses have been proposed at highly-rated robotics and AI conferences. However, it turns out that the problem of non-optimal multi-agent pathfinding has already been completely solved in another research community in the 1980s. In this paper, we would like to bring this earlier related work to the attention of the robotics and AI communities.