AAAI

Association for the Advancement of Artificial Intelligence

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

Multi-Directional Search

Authors

Dor Atzmon,Jiaoyang Li,Ariel Felner,Eliran Nachmani,Shahaf Shperberg,Nathan Sturtevant,Sven Koenig

Ben-Gurion University,University of Southern California,Ben-Gurion University,Ben-Gurion University,Ben-Gurion University,University of Alberta,University of Southern California


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Issue:

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Track:

Extended Abstracts

Downloads:

Download PDF

Abstract:

In the Multi-Agent Meeting (MAM) problem, the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding optimal meeting locations for multiple agents. A number of admissible heuristics are proposed and experiments demonstrate the benefits of MM*.

DOI:

10.1609/socs.v11i1.18518


SOCS

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search