Disjoint pattern database heuristics

We explore a method for computing admissible heuristic evaluation functions for search problems. It utilizes pattern databases (Culberson & Schaeer, 1998), which are precom-puted tables of the exact cost of solving various subproblems of an existing problem. Unlike standard pattern database heuristics, however, we partition our problems into disjoint sub-problems, so that the costs of solving the dierent subproblems can be added together without overestimating the cost of solving the original problem. Previously (Korf & Fel-ner, 2002) we showed how to statically partition the sliding-tile puzzles into disjoint groups of tiles to compute an admissible heuristic, using the same partition for each state and problem instance. Here we extend the method and show that it applies to other domains as well. We also present another method for additive heuristics which we call dynamically partitioned pattern databases. Here we partition the problem into disjoint subproblems for each state of the search dynamically. We discuss the pros and cons of each of these methods and apply both methods to three dierent problem domains: the sliding-tile puzzles, the 4-peg Towers of Hanoi problem, and nding an optimal vertex cover of a graph. We nd that in some problem domains, static partitioning is most eective, while in others dynamic partitioning is a better choice. In each of these problem domains, either statically parti-tioned or dynamically partitioned pattern database heuristics are the best known heuristics for the problem