Multi-Directional Search

Authors

  • Dor Atzmon Ben-Gurion University
  • Jiaoyang Li University of Southern California
  • Ariel Felner Ben-Gurion University
  • Eliran Nachmani Ben-Gurion University
  • Shahaf Shperberg Ben-Gurion University
  • Nathan Sturtevant University of Alberta
  • Sven Koenig University of Southern California

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*.

Downloads

Published

2021-09-01