Maximizing over Multiple Pattern Databases speeds up Heuristic Search
- Robert Holte, Department of Computing Science, University of Alberta
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Jack Newton
- Ram Meshulam, Computer Science, Bar-Ilan University, Israel
- David Furcy, Georgia Institute of Technology, Atlanta, GA
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