Non-optimal multi-agent pathfinding is solved (since 1984)

Röger, Gabriele and Helmert, Malte. (2012) Non-optimal multi-agent pathfinding is solved (since 1984). In: Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012). [Niagara Falls], pp. 173-174.

PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6043735

Downloads: Statistics Overview


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, all mentioning that it is an open problem which subclasses of non-optimal multi-agent pathfinding are tractable. However, it turns out that this problem has already been completely solved in another research community in the 1980s by a constructive proof that provides a polynomial algorithm that is complete for the entire class of problems. In this paper, we would like to bring this earlier related work to the attention of the robotics and AI communities.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Helmert, Malte and Röger, Gabriele
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:19 Nov 2018 16:28
Deposited On:13 Sep 2013 07:57

Repository Staff Only: item control page