Multi-Directional Heuristic Search

In the Multi-Agent Meeting problem (MAM), 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 Heuristic 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 an optimal meeting location for multiple agents. Several admissible heuristics are proposed, and experiments demonstrate the benefits of MM*.

Authors

• Dor Atzmon Ben-Gurion University of the Negev Royal Holloway, University of London
• Jiaoyang Li Carnegie Mellon University
• Ariel Felner Computer and Information Sciences, Ben-Gurion University of the Negev
• Eliran Nachmani
• Shahaf Shperberg
• Nathan Sturtevant
• Sven Koenig University of California & Örebro University

Keywords

• Agent-based and Multi-agent Systems: Multi-agent Planning
• Heuristic Search and Game Playing: Heuristic Search
• Planning and Scheduling: Planning and Scheduling