Multi-Directional Heuristic Search
- Dor Atzmon
- Jiaoyang Li
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Eliran Nachmani
- Shahaf S. Shperberg
- Nathan R. Sturtevant
- Sven Koenig
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
Citation
D. Atzmon, J. Li, A. Felner, E. Nachmani, S. Shperberg, N. Sturtevant, S. Koenig. "Multi-Directional Heuristic Search". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Christian Bessiere), pp 4062-4068, July 2020.Keywords: | Planning and Scheduling, Agent-based and Multi-agent Systems, Multi-agent Planning, Heuristic Search, Game Playing, Heuristic Search |
Category: | In Conference |
Web Links: | doi |
IJCAI |
BibTeX
@incollection{Atzmon+al:IJCAI20, author = {Dor Atzmon and Jiaoyang Li and Ariel Felner and Eliran Nachmani and Shahaf S. Shperberg and Nathan R. Sturtevant and Sven Koenig}, title = {Multi-Directional Heuristic Search}, Editor = {Christian Bessiere}, Pages = {4062-4068}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, year = 2020, }Last Updated: September 15, 2020
Submitted by Sabina P