|M.Sc Student||Adler Amir|
|Subject||Reducing Memory Requirements for Pattern Databases|
|Department||Department of Computer Science||Supervisors||Professor Shaul Markovitch|
|Dr. Ariel Felner|
A pattern database (PDB) is a heuristic function stored as a
lookup table that stores the lengths of optimal solutions for
instances of subproblems. A disjoint pattern database heuristic
function calculates the sum of several disjoint pattern databases.
The speed of search is inversely related to the size of the PDB
used, i.e., the number of patterns it contains. However, with a
given size of memory, only PDBs of up to a fixed size can be
stored. In this thesis we present two different approaches to
decreasing the amount of memory needed to store pattern databases.
In the first part of
this thesis we offer a method for compressing a PDB so that only a
fraction of the memory that would be needed to store it in its
uncompressed form is used. We suggest storing PDBs in advanced data
structures instead of storing them in tables.
This enables several adjacent patterns to be mapped to only one entry instead of having a unique PDB entry for each pattern, without losing any heuristic values. We introduce two types of data structures to store the PDBs - a trie and a sequence-divider. Experimental results on the sliding-tile puzzle domain show improvements of up to a factor of 8 in the amount of memory needed to store the PDBs compared with the benchmark.
In the second part of this thesis we try another approach. Instead of computing the entire state space once and using it for all problem instances, we compute a memory-based heuristic for a single problem instance. This enables us evolving only part of the entire state space for each problem. We describe a method for reducing PDB memory requirements by storing only PDB values for a specific instance of start and goal states. In other words, we store in memory only a subset of the original PDB values, which we assume have a bigger chance of being used during the search than other PDB values. Applying this method in the 24-tile puzzle domain enabled us using PDBs, which are larger than the benchmark 6-6-6-6 partition, e.g. an 8-8-8 partition of this domain. We also suggest a number of general enhancements and simplifications to this method and apply them to the 24-tile puzzle. Experimental results show a reduction of up to a factor of 40 in the number of generated nodes for random instances of this puzzle.