Extended Abstract: An Improved Priority Function for Bidirectional Heuristic Search
- Guni Sharon
- Robert Holte, Department of Computing Science, University of Alberta
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Nathan R. Sturtevant
Bidirectional search algorithms interleave a search forward from the start state (start ) and a search backward (i.e. using reverse operators) from the goal state (goal). We say that the two searches “meet in the middle” if neither search expands a node whose g-value (in the given direction) exceeds C*/2 , where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.
Citation
G. Sharon, R. Holte, A. Felner, N. Sturtevant. "Extended Abstract: An Improved Priority Function for Bidirectional Heuristic Search". Symposium on Combinatorial Search, (ed: Jorge A. Baier, Adi Botea), pp 139-140, July 2016.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Sharon+al:SoCS16,
author = {Guni Sharon and Robert Holte and Ariel Felner and Nathan R.
Sturtevant},
title = {Extended Abstract: An Improved Priority Function for Bidirectional
Heuristic Search},
Editor = {Jorge A. Baier, Adi Botea},
Pages = {139-140},
booktitle = {Symposium on Combinatorial Search},
year = 2016,
}Last Updated: July 05, 2020Submitted by Sabina P
