Planning with Pattern Databases

TLDR

Heuristic search planning can solve large planning problems, but its estimates are often inadmissible or weak, limiting optimal solutions; pattern databases, however, provide strong lower‑bound estimates that have proven effective for challenging single‑agent puzzles such as the 24‑Puzzle and Rubik’s Cube. The study investigates how pattern databases influence deterministic planning performance. The authors present a general abstraction scheme that automatically generates admissible, domain‑independent memory‑based heuristics by factorizing the planning space, and evaluate their impact on A* and hill‑climbing search across benchmark domains.

Abstract

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