Planning with Pattern Databases

摘要: Heuristic search planning effectively finds solutions for large problems, but since the estimates are either not admissible or too weak, optimal found in rare cases only. In contrast, heuristic pattern databases known to significantly improve lower bound optimally solving challenging single-agent problems like 24-Puzzle Rubik’s Cube. This paper studies effect of context deterministic planning. Given a fixed state description based on instantiated predicates, we provide general abstraction scheme automatically create domain-independent memory-based heuristics where abstractions factorizing space. We evaluate impact database A* and hill climbing algorithms collection benchmark domains.