Not Logged In

Maximizing over Multiple Pattern Databases speeds up Heuristic Search

Full Text: aij06.pdf PDF

A pattern database (PDB) is a heuristic function stored as a lookup table. This paper considers how best to use a fixed amount (m units) of memory for storing pattern databases. In particular, we examine whether using n pattern databases of size m=n instead of one pattern database of size m improves search performance. In all the state spaces considered, the use of multiple smaller pattern databases reduces the number of nodes generated by IDA*. The paper provides an explanation for this phenomenon based on the distribution of heuristic values that occur during search.

Citation

R. Holte, A. Felner, J. Newton, R. Meshulam, D. Furcy. "Maximizing over Multiple Pattern Databases speeds up Heuristic Search". Artificial Intelligence (AIJ), 170, pp 1123-1136, November 2006.

Keywords:  
Category: In Journal

BibTeX

@article{Holte+al:AIJ06,
  author = {Robert Holte and Ariel Felner and Jack Newton and Ram Meshulam and
    David Furcy},
  title = {Maximizing over Multiple Pattern Databases speeds up Heuristic
    Search},
  Volume = "170",
  Pages = {1123-1136},
  journal = {Artificial Intelligence (AIJ)},
  year = 2006,
}

Last Updated: April 24, 2007
Submitted by Nelson Loyola

University of Alberta Logo AICML Logo