Dominance and Subsumption in Constraint-Posting Planning

Michael P. WellmanIJCAI 1987 · OpenReview

Abstract

By integrating a dominance prover into the plan search process, the traditional constraint-posting planning paradigm can be generalised to permit partially satisfiable goals. In this approach, the view of planning as theorem proving is retained, although the emphasis is on proving theorems about dominance relations on classes of candidate plans. Plan classes are generated by posting constraints at various levels of abstraction, then classified within a plan lattice that manages inheritance of properties and dominance characteristics. An analysis of TWEAK demonstrates how to recast existing planning ideas in this framework, providing insight into the planner's capabilities with a dominance-proving interpretation. The plan lattice representation highlights the role of plan subsumption in optimizing search.

Introduction: Beyond Categorical Goal Satisfaction

Traditional AI planning, exemplified by the STRIPS paradigm, typically treats goals as binary logical predicates: a plan either achieves the goal or it fails. This "all-or-nothing" approach suffers from two significant limitations. First, it is inflexible, unable to handle uncertainty or scenarios where goals can only be partially satisfied. Second, it is indiscriminate; if multiple plans satisfy a goal, the system lacks a formal mechanism to select the most efficient or highest-utility option.

Michael Wellman proposes a shift from this categorical view toward an optimization-based framework. In this paradigm, planning is viewed as a search over a space of candidate plans, where the objective is to prove that certain classes of plans are superior to others through formal dominance relations.

The Plan Lattice and Dominance Relations

The core of this framework rests on two structural tools: the Plan Lattice and Dominance Relations.

The Plan Lattice is a hierarchical structure where each node represents a "plan class"—a set of plans sharing specific constraints. Moving down the lattice represents specialization (adding constraints), while moving up represents abstraction. This structure supports "least commitment" planning, allowing an agent to reason about abstract plan classes before committing to specific details.

A specialization lattice of plan classes, where nodes represent sets of plans defined by specific constraints.

Dominance relations ($D$) provide the logical basis for comparing these classes. A plan class $P_1$ is said to dominate $P_2$ if, for every plan in $P_2$, there exists a plan in $P_1$ that is at least as good according to a defined utility function. This allows the planner to prune entire branches of the search space that are proven to be inferior, even if they technically "satisfy" the goal.

Planning as Dominance Proving

Instead of proving that a single plan satisfies a goal, the planner's task is to prove theorems about dominance between plan classes. This approach enables the planner to narrow the search to "admissible" plans without requiring an immediate optimal solution.

Structural decomposition of a plan class into components for dominance proving.

By classifying new plan classes within the lattice, the system can detect redundancies through subsumption. If a new plan class is subsumed by one already known to be dominated, it can be discarded immediately. Furthermore, the framework introduces conditional dominance ($D_s$), where dominance holds only under specific assumptions ($S$), providing a robust way to handle planning under uncertainty.

Case Study: Re-interpreting TWEAK

The paper applies this framework to TWEAK, a landmark nonlinear constraint-posting planner. By re-interpreting TWEAK’s search operators—such as adding a step or ordering—as movements within the plan lattice, Wellman demonstrates that the algorithm's efficiency stems from its implicit ability to prune dominated plan classes. This formalization provides a more rigorous explanation for the effectiveness of nonlinear planning search procedures.

Key Results and Complexity

A critical finding of this work is that nonlinear plan subsumption is NP-complete. This implies that while the lattice approach is theoretically powerful, the computational cost of determining if one partial plan is a version of another is high. Practical implementations must therefore use restricted constraint languages or domain-specific heuristics to maintain a manageable lattice.

Additionally, the framework provides a principled method for generating "nogoods" (sets of constraints to be avoided) based on dominance. This is significantly more powerful than traditional pruning, which only identifies logical contradictions.

Conclusion and Future Directions

Wellman's framework lays the groundwork for integrating decision theory with AI planning. While it successfully formalizes existing techniques like TWEAK, challenges remain. Computing dominance for unions of plan classes (disjunctive planning) is substantially more complex than for intersections. Future work aims to fully integrate complex utility functions into the dominance prover, moving closer to a truly Bayesian approach to automated planning.

Summary updated

Abstract

By integrating a dominance prover into the plan search process, the traditional constraint-posting planning paradigm can be generalised to permit partially satisfiable goals. In this approach, the view of planning as theorem proving is retained, although the emphasis is on proving theorems about dominance relations on classes of candidate plans. Plan classes are generated by posting constraints at various levels of abstraction, then classified within a plan lattice that manages inheritance of properties and dominance characteristics. An analysis of TWEAK demonstrates how to recast existing planning ideas in this framework, providing insight into the planner's capabilities with a dominance-proving interpretation. The plan lattice representation highlights the role of plan subsumption in optimizing search.
BibTeX
@inproceedings{wellman1987dominance,
  author = {Michael P. Wellman},
  title = {{Dominance and Subsumption in Constraint-Posting Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
  url = {https://openreview.net/forum?id=BkZSNXG_WB},
}
Figure