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, December 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: May 24, 2007Submitted by Nelson Loyola
