Pattern databases are dictionaries for heuristic estimates based on state-to-goal distances in state space abstractions. Their effectiveness is sensitive to the selection of the underlying patterns. Especially for multiple and additive pattern databases, a manual selection of pattern sets that lead to good exploration results is involved. For automating the selection process, greedy bin-packing strategies have been suggested. This paper proposes genetic algorithms to optimize their output. Patterns are encoded as Boolean matrices and optimized using an objective function based on predicting the heuristic search tree size, given the distribution of heuristic values in the abstract state spaces. To reduce the memory requirements of the databases we apply a construction process based on BDDs. Experiments in heuristic search planning show that the search efforts are significantly reduced.
Subjects: 1.11 Planning; 15.7 Search
Submitted: May 17, 2006