AAAI Publications, Tenth Annual Symposium on Combinatorial Search

Font Size: 
On Variable Dependencies and Compressed Pattern Databases
Malte Helmert, Nathan R. Sturtevant, Ariel Felner

Last modified: 2017-06-05


Pattern databases are among the strongest known heuristics for many classical search benchmarks such as sliding-tile puzzles, the 4-peg Towers of Hanoi puzzles, Rubik's Cube, and TopSpin. Min-compression is a generally applicable technique for augmenting pattern database heuristics that has led to marked experimental improvements in some settings, while being ineffective in others. We provide a theoretical explanation for these experimental phenomena by studying the interaction between the ranking function used to order abstract states in a pattern database, the compression scheme used to abstract states, and the dependencies between state variables in the problem representation.

Full Text: PDF