Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics
- Eshed Shaham
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Nathan R. Sturtevant
- Jeffrey S. Rosenschein
A* is optimally effective with regard to node expansions among unidirectional admissible algorithms—those that only assume that the heuristic used is admissible. Among bidirectional algorithms the Fractional MM algorithm is optimally effective (given the correct parameters) among admissible algorithms.This paper generalizes the bidirectional result to more complex settings where more information on the problem domain can be exploited: (1) When the cost of the minimal edge is known. (2) When the algorithm knows that the heuristics are consistent. This characterization uses a novel algorithm called MT. MT is similar to Fractional MM and is also optimally effective, but simpler to analyze.
Citation
E. Shaham, A. Felner, N. Sturtevant, J. Rosenschein. "Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics". Symposium on Combinatorial Search, (ed: Vadim Bulitko, Sabine Storandt), pp 81-98, July 2018.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Shaham+al:SoCS18,
author = {Eshed Shaham and Ariel Felner and Nathan R. Sturtevant and Jeffrey
S. Rosenschein},
title = {Minimizing Node Expansions in Bidirectional Search with Consistent
Heuristics},
Editor = {Vadim Bulitko, Sabine Storandt},
Pages = {81-98},
booktitle = {Symposium on Combinatorial Search},
year = 2018,
}Last Updated: July 03, 2020Submitted by Sabina P
