Technical Report No. 142 - Abstract

Stefan Edelkamp
Planning with Pattern Databases

Heuristic search techniques and greedy local search methods effectively find solutions to difficult planning problems. However, when aiming at optimal solutions, the achieved results are relatively weak. To the contrary, pattern data bases are known to significantly improve lower-bound estimates for optimally solving challenging single-agent problems like the 24-Puzzle, Sokoban and the Rubik's Cube. Therefore, this paper studies the effect of pattern data bases in the context of deterministic planning. We face a fixed state description based on instantiated predicates and provide a general state space abstraction scheme to infer memory-based heuristics, whereas abstractions are found in factoring the planning space.