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

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