Searching With Abstractions: AUnifying Framework and New High-Performance Algorithm 1

This paper presents a common algorithmic framework encompassing the two main methods for using an abstract solution to guide search. It identifies certain key issues in the design of techniques for using abstraction to guide search. New approaches to these issues give rise to new search techniques. Tw o of these are described in detail and compared experimentally with a standard search technique, classical refinement. The "alternating opportunism" technique produces shorter solutions than classical refinement with the same amount of search, and is a more robust technique in the sense that its solution lengths are very similar across a range of different abstractions of any giv en space.