Abstract
Abstraction is a cornerstone of efficient planning, yet its application does not inherently guarantee performance gains. In many cases, an abstract planner can perform worse than a flat search if the chosen abstraction forces frequent backtracking across levels. This paper formalizes the Downward Refinement Property (DRP), a condition ensuring that any abstract solution can be refined into a concrete one without revisiting higher-level decisions. By establishing semantic foundations and polynomial-time syntactic checks, this work provides a rigorous framework for designing and verifying efficient abstraction hierarchies in ABSTRIPS-style planners.
Introduction: The Abstraction Paradox
In artificial intelligence, planning involves finding a sequence of actions to reach a goal state. To manage the state-space explosion, researchers often use abstraction—simplifying the problem by ignoring certain details (preconditions) to find a high-level "skeleton" plan. However, abstraction is a double-edged sword. If a high-level plan is found that cannot be realized at the detailed level, the planner must backtrack to the abstract level and try a different skeleton. This "backtracking across levels" can lead to worse performance than a standard search.
The key to unlocking the power of abstraction lies in the Downward Refinement Property (DRP). When a hierarchy possesses DRP, the planner can "fill in the blanks" of a high-level plan with total confidence, knowing that the high-level structure will remain valid.
Defining the Downward Refinement Property
The DRP is formally defined within the context of ABSTRIPS-style abstraction. In this framework, literals are assigned "criticality" levels. Abstract levels are created by dropping preconditions with lower criticality.
A hierarchy satisfies the DRP if, given that a concrete-level solution exists, every abstract solution can be refined to a concrete-level solution without backtracking across abstract levels. This property ensures that the search space is effectively partitioned, allowing the planner to solve a series of smaller sub-problems rather than one massive search.
The Importance of Directionality
The paper illustrates the DRP using the Towers of Hanoi domain. The success of the abstraction depends entirely on which disks are considered "critical":
- Correct Abstraction: If the "Big Disk" has higher criticality than the "Small Disk," the DRP holds. One can plan to move the big disk first; if the small disk is in the way, it can always be moved to a different peg without disturbing the big disk's eventual destination.
- Incorrect Abstraction: If the "Small Disk" is more critical, the DRP fails. A plan to move the small disk might be impossible to refine because the big disk (ignored at the abstract level) is physically blocking the path in a way that requires undoing the small disk's movement.
Formal Semantics and Syntactic Checks
The authors provide a formal characterization of DRP by defining planning states as sets of possible worlds and operators as partial functions. While semantic verification of DRP is computationally difficult, the paper introduces three increasingly sophisticated, polynomial-time checkable syntactic conditions:
- Complete Independence: Operators at different levels do not interact, ensuring that low-level actions never interfere with high-level literals.
- Complete Low-Level Connectivity: Any two states that appear identical at a high level can be connected by a low-level path that does not disturb high-level literals.
- Necessary Connectivity: A more practical, relaxed version of connectivity that only requires paths between states specifically generated by the operator sequences in the plan.
Impact on Search Efficiency
The theoretical impact of DRP on search complexity is profound. In a standard search with branching factor $b$ and depth $d$, complexity is $O(b^d)$. With a $k$-level abstraction hierarchy satisfying DRP, the complexity can be reduced to approximately $O(k \cdot b^{d/k})$, representing an exponential gain.
Empirical results using the ABTWEAK planner support these findings. In the Towers of Hanoi domain, a hierarchy with DRP demonstrated a 10-fold improvement in both search time and memory usage. In many instances, the presence of DRP was the deciding factor in whether the search terminated at all.
Conclusion and Future Work
This research moves the Downward Refinement Property from an intuitive concept to a mathematically rigorous tool. By providing syntactic tests, the authors allow developers to verify the efficiency of a planning hierarchy before execution.
However, the current scope is limited to ABSTRIPS-style precondition dropping. Future work remains in extending these properties to other abstraction types, such as macro-operators or state-grouping. Additionally, while the paper provides tools to check a hierarchy, the challenge of automatically generating an optimal hierarchy that satisfies DRP remains an open area for research. The authors also suggest exploring "probabilistic DRP," where a hierarchy is designed to be "mostly" refinement-friendly, offering a trade-off between strict guarantees and practical flexibility.
Summary updated