טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAdler Amir
SubjectReducing Memory Requirements for Pattern Databases
DepartmentDepartment of Computer Science
Supervisors Professor Shaul Markovitch
Dr. Ariel Felner


Abstract

 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.