On Variable Dependencies and Compressed Pattern Databases

Proceedings of the International Symposium on Combinatorial Search, 10

Volume

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

Short Papers

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.

10.1609/socs.v8i1.18437