Pattern databases are heuristics used in search that rely on abstractions that aggregate states if they agree on a subset of the state variables. This paper considers a more general class of abstractions called merge-and-shrink abstractions. Shrinking projects the state space to be searched surjectively onto a reduced state space, merging involves creating an abstraction from two abstractions that involve disjoint variables on the state space. From these operations one constructs a tree of abstractions called a merge-and-shrink tree.

This paper provides a description of a generic merge-and-shrink algorithm. This abstracts away from the merging strategy and the shrinking strategy. Concrete construction of the tree requires choosing the strategies for merging and shrinking. The main tool used to make these choices is to relax bisimilarity of the representations.

Since many problems of interest are specified in terms of the allowable transitions between states, a major concern is that the total state space for the problem can be very large. The main results of this paper show that merge-and-shrink abstractions can be constructed in polynomial time. Furthermore, the resulting abstraction provides good lower bound estimates for reachability.

The authors identify the class of transition systems--factored ones--which allow these abstractions to be built in a practical, incremental way, without loss of information. For the purposes of exposition, the paper uses a simplified logistics planning problem involving a truck and two packages. The paper also includes the results of experiments on planning tasks using the authors’ merge-and-shrink approach, and compares the results to other planning techniques. While the paper is somewhat densely written, it provides full details for the reader.