Automated Pattern Database Design

Stefan Edelkamp

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.