Dual Lookups in Pattern Databases
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Uzi Zahavi, Computer Science, Bar-Ilan University, Israel
- Jonathan Schaeffer, Department of Computing Science, University of Alberta
- Robert Holte, Department of Computing Science, University of Alberta
A pattern database (PDB) is a heuristic function stored as a lookup table. Symmetries of a state space are often used to enable multiple values to be looked up in a PDB for a given state. This paper introduces an additional PDB lookup, called the dual PDB lookup. A dual PDB lookup is always admissible but can return inconsistent values. The paper also presents an extension of the well-known pathmax method so that inconsistencies in heuristic values are propagated in both directions (childto- parent, and parent-to-child) in the search tree. Experiments show that the addition of dual lookups and bidirectional pathmax propagation can reduce the number of nodes generated by IDA* by over one order of magnitude in the TopSpin puzzle and Rubik’s Cube, and by about a factor of two for the sliding tile puzzles.
Citation
A. Felner, U. Zahavi, J. Schaeffer, R. Holte. "Dual Lookups in Pattern Databases". International Joint Conference on Artificial Intelligence (IJCAI), Edinburgh, Scotland, pp 103-108, August 2005.| Keywords: | dual, lookkups, pattern |
| Category: | In Conference |
BibTeX
@incollection{Felner+al:IJCAI05,
author = {Ariel Felner and Uzi Zahavi and Jonathan Schaeffer and Robert
Holte},
title = {Dual Lookups in Pattern Databases},
Pages = {103-108},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2005,
}Last Updated: June 04, 2007Submitted by Staurt H. Johnson
