On Variable Dependencies and Compressed Pattern Databases
- Malte Helmert
- Nathan R. Sturtevant
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
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.
Citation
M. Helmert, N. Sturtevant, A. Felner. "On Variable Dependencies and Compressed Pattern Databases". Symposium on Combinatorial Search, (ed: Alex Fukunaga, Akihiro Kishimoto), pp 129-133, June 2017.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Helmert+al:SoCS17,
author = {Malte Helmert and Nathan R. Sturtevant and Ariel Felner},
title = {On Variable Dependencies and Compressed Pattern Databases},
Editor = {Alex Fukunaga, Akihiro Kishimoto},
Pages = {129-133},
booktitle = {Symposium on Combinatorial Search},
year = 2017,
}Last Updated: July 05, 2020Submitted by Sabina P
