Abstract
We present the system ABTWEAK, which extends the precondition-elimination abstraction of AB-STRIPS to hierarchical planners using the nonlinear plan representation as defined in TWEAK. We show that ABTWEAK satisfies the monotonic property, whereby the existence of a lowest level solution II implies the existence of a highest level solution that is structurally similar to II. This property enables one to prune a considerable amount of the search space without loss of completeness.
Introduction
In the field of automated planning, agents seek to determine a sequence of actions to achieve a specific goal. Early systems, such as STRIPS, operated on a "linear" basis, constructing plans as simple chains of events. Subsequent advancements led to "nonlinear" planners like TWEAK, which introduced "least-commitment" strategies. These strategies allow a planner to defer decisions regarding the exact ordering of actions or specific variable bindings until they are strictly necessary. While TWEAK offered significantly more flexibility than its predecessors, it suffered from a prohibitively large search space.
Hierarchical planners like ABSTRIPS attempted to mitigate search complexity through "abstraction"—simplifying the problem by initially ignoring low-level details (preconditions). However, the formal theory for abstraction was historically tied to linear planners. ABTWEAK bridges this gap by formally applying the power of hierarchical abstraction to the more sophisticated, nonlinear framework of TWEAK.
The ABTWEAK Framework
ABTWEAK integrates the precondition-elimination abstraction of ABSTRIPS into the nonlinear planning environment. The system is built upon several key technical components:
- Criticality Levels: Predicates (world conditions) are assigned integer "criticality" scores. At higher levels of abstraction, the planner ignores any precondition with a criticality score below the current threshold.
- Justified Plans: The authors introduce the concept of a "justified" plan. This is a stripped-down version of a plan that removes any operators or constraints that exist solely to satisfy preconditions that have been abstracted away at a given level.
- The Modal Truth Criterion (MTC): ABTWEAK adapts David Chapman’s MTC—a formal logic for determining if a statement is true within a partially ordered plan—to function across varying levels of abstraction.
- Search Control: Because nonlinear planning is semi-decidable, the authors propose a "diagonalizing enumeration" strategy. This ensures that the search remains complete across multiple levels of abstraction, preventing the planner from becoming trapped in infinite branches.
The Monotonic Property
The core theoretical contribution of ABTWEAK is the proof of the monotonic property. The authors demonstrate that ABTWEAK systems are inherently monotonic: if a solution exists at the most detailed (concrete) level, a structurally similar solution must exist at every higher abstract level.
This property enables safe pruning. Because of monotonicity, if a planner finds an abstract plan that cannot be refined (expanded) into a lower level, it can safely backtrack. The system can ignore vast branches of the search tree that are guaranteed not to lead to a concrete solution, significantly reducing computational waste. Notably, this property holds regardless of the specific criticality values assigned to preconditions, reducing the system's dependence on perfect human-authored hierarchies.
Conclusion and Future Work
ABTWEAK provides a formal roadmap for building search algorithms that are guaranteed to find solutions efficiently by navigating complex hierarchies. While the paper establishes a robust theoretical foundation and proves the upward solution property, it acknowledges that empirical benchmarking is the next step. Future work will focus on implementation and computational comparisons to provide concrete evidence of ABTWEAK's advantages over existing hierarchical systems in practice. By marrying least-commitment planning with formal abstraction, ABTWEAK represents a landmark step in managing the complexity of automated reasoning.
Summary updated