Dual Lookups in Pattern Databases
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 103-107.
Abstract
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.
@inproceedings{ijcai2005p12,
title = {Dual Lookups in Pattern Databases},
author = {Felner, Ariel and Zahavi, Uzi and Schaeffer, Jonathan and Holte, Robert C.},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {103--107},
year = {2005},
url = {https://ijcai.org/proceedings/2005/12},
}
TY - CPAPER TI - Dual Lookups in Pattern Databases AU - Felner, Ariel AU - Zahavi, Uzi AU - Schaeffer, Jonathan AU - Holte, Robert C. T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 103 EP - 107 UR - https://ijcai.org/proceedings/2005/12 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
