AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 14

Studying Online Multi-Agent Path Finding

Authors

Jonathan Morag,Roni Stern,Ariel Felner,Dor Atzmon,Eli Boyarski

Ben-Gurion University of the Negev,Ben Gurion University of the Negev,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 14

Volume

Issue:

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search

Track:

Student Papers

Downloads:

Download PDF

Abstract:

Multi-agent path finding (MAPF) is the problem of planning a set of non-conflicting plans on a graph, for a set of agents. Online MAPF extends MAPF by considering a more realistic problem in which new agents may appear over time. While planning, an online solver does not know whether and which agents will join in the future. Therefore, in online problems the notion of snapshot-optimal was defined, where only current knowledge is considered. The quality of such a solution may be weaker than the quality of a solution to an equivalent offline MAPF problem (offline-optimality), where the solver is preinformed of all the agents that will appear in the future. In this paper we explore, theoretically and empirically, the quality of snapshot-optimal solutions compared to offline-optimal solutions.

DOI:

10.1609/socs.v12i1.18592


SOCS

Vol. 14 No. 1 (2021): Fourteenth International Symposium on Combinatorial Search