Introducing a continuum of abstraction-led hierarchical search techniques

Abstract

Abstraction in search works by replacing a state space by another space (the abstract space) that is easier to search, either because it is smaller or because it contains more solutions. Results of searches in the abstract space are then used to guide searches in the original space in one of two distinct ways. The first uses the lengths of the abstract solutions as a heuristic for an A* search of the original space: this always produces optimal solutions. The second uses the steps in the abstract solution as sub-goals for the search in the original space: this strategy does not guarantee optimality, but it does tend to find a solution quickly. In this paper, both of these types of abstraction-led search are explained, and a general setting for all abstraction-led search is introduced. The two standard cases are included as extreme cases in the general setting, and so are a continuum of new techniques between the two. It is hoped that further study of this continuum will lead to new, useful heuristic search techniques.