Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters

Abstract

Pattern Databases (PDBs) are a common form of abstraction-based heuristic whichare often compressed so that a large PDB can fit inmemory. Partial Pattern Databases (PPDBs) achieve this by storing only layersof the PDB which are close to the goal. This paper studies the problem of howto best compress and use the 457 GB 12-edge Rubik's cube PDB, suggesting anumber of ways that Bloom filters can be used to effectively compress PPDBs. Wethen develop a theoretical model of the common min compression approach and ourBloom filters, showing that the original method of compressed PPDBs can neverbe better than min compression. We conclude with experimental results showingthat Bloom filter compression of PPDBs provides superior performance to mincompression in Rubik's cube.