The Downward Refinement Property

Abstract

Using abstraction in planning does not guarantee an improvement in search efficiency; it is possible for an abstract planner to display worse performance than one that does not use abstraction. Analysis and experiments have shown that good abstraction hierarchies have, or are close to having, the downward refinement property, whereby, given that a concrete-level solution exists, every abstract solution can be refined to a concrete-level solution without backtracking across abstract levels. Working within a semantics for ABSTRIPS-style abstraction we provide a characterization of the downward refinement property. After discussing its effect on search efficiency, we develop a semantic condition sufficient for guaranteeing its presence in an abstraction hierarchy. Using the semantic condition, we then provide a set of sufficient and polynomial-time checkable syntactic conditions that can be used for checking a hierarchy for the downward refinement property.