Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters
- Nathan R. Sturtevant
- Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
- Malte Helmert
Pattern Databases (PDBs) are a common form of abstraction-based heuristic which are often compressed so that a large PDB can fit in memory. Partial Pattern Databases (PPDBs) achieve this by storing only layers of the PDB which are close to the goal. This paper studies the problem of how to best compress and use the 457 GB 12-edge Rubik's cube PDB, suggesting a number of ways that Bloom filters can be used to effectively compress PPDBs. We then develop a theoretical model of the common min compression approach and our Bloom filters, showing that the original method of compressed PPDBs can never be better than min compression. We conclude with experimental results showing that Bloom filter compression of PPDBs provides superior performance to min compression in Rubik's cube.
Citation
N. Sturtevant, A. Felner, M. Helmert. "Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters". Symposium on Combinatorial Search, (ed: Stefan Edelkamp, Roman Barták), pp 175-183, August 2014.| Keywords: | Search, Rubik's cube, heuristic |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Sturtevant+al:SoCS14,
author = {Nathan R. Sturtevant and Ariel Felner and Malte Helmert},
title = {Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern
Databases and Bloom Filters},
Editor = {Stefan Edelkamp, Roman Barták},
Pages = {175-183},
booktitle = {Symposium on Combinatorial Search},
year = 2014,
}Last Updated: July 09, 2020Submitted by Sabina P
