Automatic Generation of Memory Based Search Heuristics

Our goal is to automatically generate heuristics to guide state space search. The heuristic values are distances computed in an abstract space which is automatically derived from the original space. The search space is described in a production system. Simple syntactic transformations of this description give rise to another search space. The distances of abstract states from the abstract goal state are stored in a look-up table and provide admissible and monotonic heuristics for search algorithms such as IDA*. The size of the abstract space is the size of the look-up table and different transformations on the description of the space give rise to abstract spaces of different size. We are interested in the relationship between the memory required to store the heuristic and the speed of search. We are also interested in ranking abstractions which generate abstract spaces of the same cardinalit