Not Logged In

Hierarchical Heuristic Search Revisited

Pattern databases enable difficult search problems to be solved very quickly, but are large and time-consuming to build. They are therefore best suited to situations where many problem instances are to be solved, and less than ideal when only a few instances are to be solved. This paper examines a technique - hierarchical heuristic search - especially designed for the latter situation. The key idea is to compute, on demand, only those pattern database entries needed to solve a given problem instance. Our experiments show that Hierarchical IDA* can solve individual problems very quickly, up to two orders of magnitude faster than the time required to build an entire high-performance pattern database.

Citation

R. Holte, J. Grajkowski, B. Tanner. "Hierarchical Heuristic Search Revisited". Symposium on Abstraction, Reformulation and Approximation, Edinburg L, January 2005.

Keywords: hierarchical, heuristic, revisited
Category:  

BibTeX

@incollection{Holte+al:SARA05,
  author = {Robert Holte and Jeffery Grajkowski and Brian Tanner},
  title = {Hierarchical Heuristic Search Revisited},
  booktitle = {Symposium on Abstraction, Reformulation and Approximation},
  year = 2005,
}

Last Updated: April 25, 2007
Submitted by Nelson Loyola

University of Alberta Logo AICML Logo