Dominance and Subsumption in Constraint-Posting Planning

I. Introduction

One glaring limitation of the traditional AI robot plan­ ning paradigm is its view of goals as logical predicates on world states. Such a view precludes the consideration of uncertainty except in rare cases where either uncertainty is adequately captured in tolerances or execution moni­ toring with replanning is viable. Even in the absence of uncertainty, planning to satisfy goal predicates provides no mechanism to choose among the plans that achieve the goal nor any guidance about what to do when no such plan exists. The literature has offered ad hoc solutions to overcome some of these limitations in specific cases, for ex­ ample, simple resource allocation mechanisms or domain­ specific meta-planning rules.

· Alternate views, such as Bayesian decision theory, of­ fer more comprehensive choice criteria but do not address the planning task of constructing strategies from more primitive actions.

In this paper I describe a formal framework for plan­ ning that permits the broader range of choice criteria nec­ essary in an environment of partially satisfiable goals with multiple objectives. At the same time it can incorporate many of the principles, representations, and techniques of existing research on planning. Central to the framework is the notion of planning as the derivation and propagation of dominance relations among classes of candidate plans.

1 Supported by National Institutes of Health Grant No. ROl LM04493 from the National Library of Medicine.

Definitions and explanations of the structures consti­ tuting the planning framework are provided in the sec­ tions below. The theoretical apparatus is illustrated with an investigation of TWEAK, a nonlinear constraint-posting planner [Chapman, 1985a] . Although TWEAK is defined in terms of logical goal predicates, an interpretation in terms of the dominance relation provides insight into its capabil­ ities and efficiency. An analysis of TWEAK's search proce­ dure highlights the role of plan subsumption computations in this approach to planning.

II. The Plan Lattice

Let f. be the planning language, or equivalently, the set of all syntactically valid plans. For example, if A = { a1, . .. , a,.} is an alphabet of primitive actions, then f. = A · is the language of linear plans. The language of nonlinear plans is similar, extended by an encoding for partial orders. A plan class is any set of plans, P ~ f. . P is also called a partial plan when it represents a set of constraints that incompletely specifies the plan we are con­ cerned about.

We can view the planning process as one of incre­ mentally adding constraints to candidate plan classes until some problem is solved regarding the plan to be executed. In traditional planning the problem is to identify a plan that satisfies the given goal. With a more versatile evalu­ ation criterion, the problem is to find the best plan. Ex­ cept for some special cases where convenient optimization techniques are applicable, it is not possible to determine whether a given plan is optimal by examining it in iso­ lation. It may be more reasonable to answer questions about the optimal plan without necessarily constructing a complete description.

The partial plans generated during the planning pro­ cess can be organized in a specialization lattice according to the subset relation. An example of a plan specialization lattice appears in Figure 1. The node in the graph marked "A*a1A*" denotes the set of all plans with at least one instance of action a 1_. The set of plans beginning with a 1 forms a subclass, as does the set of plans where a 1 is fol­ lowed by a2.

The plan lattice representat ion of a search space supports a eorutraint-po.ting approach to planning. A constraint-posting planner, illustrated best by MOL­ GEN [Stefik, 1981], can be more efficient than a planner that evaluates only complete plans. Flexibility is gained by allowing many forms of constraints rather than, for in­ stance, just adding actions to a sequence or specifying ex­ act bindings for variables, However, these advantages de­ pend on having some justification for the constraints based on properties of the partial plan. For example, MOLGEN knows that for a scrun operation to be useful, it must se­ lect the appropriate bacteria. Thus, when adding a screen step to a plan, MOLGEN is justified in posting a constraint of the form (resistl antibiotic-1 bacterium-,4); constrain­ ing the antibiotic to a particular chemical agent would be unjustifiably specific at this stage.

By adding only the constraints that have the best jus­ tifications, a planner implements a least commitment strat­ egy. An extreme form of least commitment propagates only provable properties of admiBBible plans. In practice, however, real planners, like MOLGEN, have to make guesses when no provable constraints are available. The least com­ mitment heuristic tends to minimi~e both the likelihood of wrong guesses and the extent of backtracking required to recover from such mistakes. A policy of working on plan classes at high levels of abstraction is simply a particu­ lar form of least commitment atrategy. Because it avoids backtracking, a search procedure that preserves the entire lattice of partial plans corresponds to "no commitment" planning.

III. Dominance in the Plan Lattice

To speak meaningfully of dominance among plan classes, we need to introduce a preference relation, >-, over plans. In categorical planning, for example, one plan is preferred to another if it achieves the goal and the other does not. To state this in terms of the situation calculus [McCarthy and Hayes, 1969], we write:

G is the goal predicate, defined on situations resulting from the robot performing a plan in a given situation. Here Bi denotes the initial situation. Two plans that both achieve or do not achieve the goal are equally preferred, or indif­ ferent, denoted by""'· The expreBSion 71"1 t 71"2 means that 71"1 is preferred or indifferent to 71"2 ·

The preference relation characterizes the choice cri­ terion employed by the planner. A planner based on ex­ pected utility takes

The discUBBion of dominance that follows does not depend on any particular criterion for plan choice. Although we assume that t ·is a total order on plans, we do not insist that the planner be given a complete or even an explicit description of the preference relation.

We say that a class of plans dominates another if, for any plan in the second class, some plan in the first class is preferred or indifferent. It should be emphasized that it is pOBBible to prove dominance without identifying the supe­ rior plan--otherwise this approach provides no advantage over branch-and-bound search. The dominance relation, D, is defined as follows:

The strict version of dominance, D', is defined similarly, except that here a particular plan in the first class is pre­ ·ferred to any in the second. 2

Clearly, strict dominance implies dominance. In addition, the properties below follow easily from the definitions:

These properties serve as dominance propagation rules within the plan lattice. By (8) and the transitivity of D, dominance by a particular class is inherited in the plan lattice. Strict dominance is also inherited, by (11) and weak dominance inheritance. Thus, markers or links indicating dominance relations need be stored only at the upper envelope of classes to which they apply. Dominance is propagated upwards in the lattice by application of the union properties (9 and 10), which also hold forD'.

2 Thi1 difference ia required bec&Uie of the pouibility of infinite plan claue. with no maximal element.. U (4) were exactly a 1hid venion of (3), then 1uch a clau would 1trictly dominate itlelf. For the 1ame rea10n, a definition of weak dominance that merely 1ubltituted ~ for >- In ( 4) would not entail the reflexive property. Auuminc every plan clau hu a maximal plan ia unrea10nable, even if it ia appropriate to require that l doe..

A plan class is restricted by asserting that it is weakly dominated by one of its subsets. In the MOLGEN exam­ ple given above, if P1 is the class of plans that include the screen operation, and P2 is the subclass that includes the resists relation as well, then D(P2, PI) asserts that (re­ sists antibiotic-1 bacterium-.4) is a valid constraint. The new dominance assertion represents progress because it lets us focus our attention on a smaller set of plans. Thus, deriving these restrictions is an important task of the dom­ inance prover.

Constraints might be posted to explore the search space even though the dominance relation does not prov­ ably hold. Often, such constraints are justified by identi­ fiable assumptions that imply dominance. We can express this case by asserting the conditional dominance relation, Ds, for S an assumption proposition

Normal dominance is just Dtrue· As an example of conditional dominance, suppose that we are uncertain about the identity of the organism of interest; it could be either bacterium-£ or bacterium-9. For i = 2 and 3, let S; be the proposition "Bacterium-i is the organism of inter­ est" and P; the plan class that restricts P1 to those plans in which the resists relation holds between antibiotic-1 and bacterium-i. Then we have Ds,(P2, PI), Ds 3 (Pa, P1), and S2 v S3 · By the definition of conditional dominance (12), we get D(P2, P1) V D(Pa, PI). Application of (10) yields the result D(P2 U Pa, P1).

Of particular value are conditional dominance rela­ tions where S itself contains dominance assertions. For example, if S' = D(P1. .C), then Ds· (P2, PI) asserts that given the optimal plan is in P1 we can further confine at­ tention to P2. 3 This is one way to derive the restrictions mentioned above. In fact, this is precisely the strategy employed by both Pednault [Pednault, 1985] and Chap­ man [Chapman, 1985b] to limit the search space of their planners. We will see how this works for the latter example in Section V below.

Reasoning about conditional dominance can be im­ plemented straightforwardly via any mechanism for rea­ son maintenance [de Kleer, 1986a, McAllester, 1982]. The interesting task for the dominance prover is to come up with meaningful conditions that imply useful dominance relations.

IV. Planning

A program manipulates the plan lattice by repeatedly per­ forming the following steps (not in any particular order):

3Jn categorical planning, D5 , is the same a.a D (that is, D5 ,(Pt,P2) <:> D(Pt,A}} due to thl! binary nature of the prefer­ ence relation ( 1).

• Generate new plan classes by adding constraints to undominated classes.
• Construct and refine the prediction/ evaluation part of the world model.
• Derive and propagate dominance relations among plan classes. Strengthen conditional dominance relations.

We will say that a program performing these tasks is planning. Note that in this view planning is not a search for a single plan to execute, but an exploration of proper­ ties of admissible plans. A planner performs useful work by refining the plan lattice, even if the lowest-level classes are never reduced to singleton sets. If, after much compu­ tation, the planner has narrowed the admissible plans to a set that contains 10 400 or possibly an uncountable in­ finity of plans, this may seem like little progress. But if we can determine that all plans contain, for example, an appendectomy, we solve a significant problem. 4

The prevailing view of planning as construction of a completely specified course of action is never totally ac­ curate. Planners devote their resources to isolated deci­ sions, as in whether or not to perform an appendectomy, without specifying all other features of the plan. A plan to obtain some bananas is complete only with respect to a have-bananas goal; in the larger context of satisfying all physical and emotional needs forever, the agent never stops planning. Figuring out how to get the bananas is a small act of refinement on THE BIG PLAN.

The framework presented so far should be regarded as an abstract model of planning with partially satisfiable objectives. It generalizes the case of goal predicates and applies to uncertain situations. Rather than prove that a plan necessarily achieves a goal, as in traditional AI plan­ ning, the planner tries to prove properties of the optimal plan. These properties define the class of ad~ssible plans.

To instantiate the abstract model to a particular plan­ ning mechanism, one needs to specify:

• The plan language, .C.
• A constraint language (representation for partial plans).
• A domain modeling language, including a way to de­ scribe the effects of actions and a representation for the preference relation, >-.
• A dominance prover.

The structures described e"arlier-the plan lattice and dominance relations--serve mainly as theoretical machin­ ery for analysis of this class of planners. Specifying the languages and the dominance prover is the real work in designing a planner.

4 Pla.n cla.a11e1 with such huge cardinalities should be the norm, not exceptions. If the plan language includes real-valued parameters, then all but the tightest constraints still leave an uncountable set of candidate plana. The plan cla.aa · Administer a dose of drug X within the next minute· includes individual plana where the drug is given at any point in the 60-aecond interval.

As a simple illustration, consider mathematical opti­ mization techniques as planners. Optimization is a special case of dominance proving where the program tries to find a singleton dominator, often in one step. For example, if our plan language is !Rn and the domain model consists of a linear objective function and a set of linear constraints among the elements of the vector, then our dominance prover should be a linear programming algorithm. In this case there are no partial plans. Branch-and-bound integer programming is an example of an optimization procedure that does make use of partial plans and explicit dominance proving.

In the development of the planning model up to now, we have paid little attention to efficiency. The computa­ tional value of planners in this framework depends on a judicious choice of the languages and algorithms that de­ fine it. Although it is difficult to characterize efficiency at the present level of generality, there are a few high-level issues that can be identified at this point. First, the addi­ tion of constraints during lattice refinement cannot be ar­ bitrary. The planner must generate constraints that relate to the problem at hand and are meaningful to the domi­ nance prover. Unless the prover can establish dominance relations on the lattice, refinement is irrelevant. Second, it is important to consolidate the plan lattice to avoid redun­ dancy and further the propagation of dominance relations. We will examine this topic further in Sections VI and VII below.

V. An Extended Illustration: Tweak

In the introduction I suggested that existing planning work can be recast in this framework. In this section I examine TWEAK [Chapman, 1985a, Chapman, 1985b], a nonlinear planner that captures much of the state-of-the-art in a neat algorithm. Though TWEAK belongs to the mainstream planning tradition in considering only goal predicates, its main ideas can be expressed clearly in terms of the plan lattice and dominance relation.

As described in the previous section, the way to in­ stantiate this planning framework is to define the various representations appearing in and operations performed on the plan lattice. The plan language for TWEAK is particu­ larly simple. A plan is a sequence of steps, each specifying an action applied to some objects. The term "nonlinear" refers not to plans, but to the representation for incom­ plete plans, or plan classes. 15 A plan class is nonlinear if it specifies only .a partial order on its steps. There are two other sources of incompleteness in TWEAK: steps may be missing, and steps may refer to variables rather than con­ stant objects. Thus any partial plan in TWEAK may be specified by the steps it includes, the ordering constraints on the steps, and the constraints on the designations of variables in the steps.

5 A planner with a parallel execution capability (for example, a multi-agent planner) could actually have a nonlinear plan language. The co111traint language for auch a planner would be more complex.

The domain modeling language is also quite simple. The effects of actions are completely described by finite sets of pre- and post-conditions on each step. A world model corresponding to each plan class records the sta­ tus of goal and condition propositions in a propositional database. Finally, ~ is defined by the categorical planning preference relation (1). In TWEAK, G is simply a conjunc­ tion of propositions.

The interesting part of TWEAK is not these represen­ tation languages, but the dominance properties that are applied. The power of the planning algorithm derives from the fact that, given a partial plan, we need to consider only a few types of constraints to guarantee that if a satisfactory completion of the partial plan exists, one also exists among its constrained subclasses. Constraints are posted via plan modification operators. For our purposes it helps to regard these operators as functions that return constrained plan classes given a starting plan class and possibly some other arguments. We need five plan modification operators:

• addstep(P, t)
• order(P, s, t)
• codesignate(P,x,y)
• noncodesignate(P,x,y)
• ifcodesignate(P, x, y, z, w)

Each returns the set of elements of P that satisfy the indicated constraint. Addstep constrains the partial plan to include an instance of step t. Order confines P to those plans in which steps is applied before step t. Note that if this (or the result of any modification operation) is a con­ tradiction, then the function returns the empty plan class. Analogously, if the constraint is already implied, the op­ erator is the identity function on P. The codesignate ( ab­ breviated cod) and noncodesignate (ncod) functions add the appropriate constraints to the elements indicated. In general, there may be several ways to implement a codes­ ignation among complex elements (such as predicate in­ stances) in terms of their primitive constituents. Finally, the ifcodesignate (ifcod) function constrains z and w to codesignate if x and y do.

TWEAK is defined by a nondeterministic procedure that achieves a goal by applying combinations of these op­ erators to a partial plan. Chapman presents the procedure &II a simple graph ([Chapman, 1985a, page 1024], [Chap­ man, 1985b, page 11]) where the paths from start to end exhaust the possible sequences of plan modifications that can restrict a partial plan P to achieve a goal proposition p at step s. A completely analogous description in our func­ tional notation is the expression appearing in Figure 2. This complicated expression, consisting of a combination of plan classes formed by various modifications on P, rep­ resents the set of plans nondeterministically explored by Chapman's algorithm.

Let P' denote this plan class. In the figure, E is the set of establishers; that is, actions that possibly assert the goal proposition. C and Ware the potential clobberers (ac­ tions that negate the goal) and white knights (actions that re-establish the goal), respectively. The function conseq on steps returns the consequent propositions, or postcon­ ditions, of the action. That there is a plan in P' that achieves the goal if there is one in P can be captured by asserting D(P', P). This is a restriction, because each of the components of the P' expression is itself a subset of P.

The main theoretical contribution of TWEAK boils down to this dominance condition. TWEAK refines P by adding constraints until it finds a partial plan that neces­ sarily achieves the goal, that is, a class provably containing only goal-achieving plans. The theoretical apparatus we have developed can help us understand this process.

Each term in the expression of Figure 2 corresponds to a plan class which is a subset of P. These distinguished plan classes serve as intermediate structure in the plan lattice depicted in Figure 3. This lattice reflects a decom­ position of the search space based on the TWEAK algo­ rithm. The plan classes with subscripts denote parameter­ ized classes; a complete diagram of this lattice would in­ clude, for instance, an At for every tEE. For the directed links, the plan class pointed to is defined by the boxed set operation applied to the others. Thus Kt ~f Bt n At and I. ~r n 9 Ic,q· All connections indicate specialization of plan classes from higher to lower levels.

Because it would be difficult for the planner to gen­ erate a description of P' directly from the definition of Figure 2, in practice it is necessary to manipulate represen­ tations of these intermediate classes. The TWEAK search procedure nondeterri:linistically chooses intermediate plan classes to instantiate and combine until it finds a subset of P' that necessarily achieves p at s. In the process, the algorithm recursively invokes itself, taking one of the inter­ mediate classes as P and forming the structure of Figure 3

beneath it.

VI. Classification and Dependency-Directed Search

It is possible that a recursive invocation of the TWEAK domiaance relation would reveal that some intermediate plan classes at one level are dominated by more restricted classes at lower levels. More generally, propagation via (8) through (11) may uncover dominance conditions within or between levels which can be exploited to reduce the search space.

These possibilities suggest an addition to the plan­ ning steps listed at the beginning of Section IV. When partial plans are generated, they are classified by finding their greatest lower and least upper bounds in the plan lattice. 6 Classification serves to consolidate the lattice, re­ sulting in a maximal propagation of the known dominance conditions.

The dominance relation provides us with a class of no­ good sets to be used in pruning the search space. Planners without a notion of dominance can consider only contradic­ tory plans (that is, empty plan classes) to be nogood; other pruning criteria must be built into the control mechanism. The discussion above illustrates that although TWEAK's search procedure implicitly takes advantage of the fact D(P', P), it cannot exploit the dominance consequences for intermediate plan classes.

Consolidating the plan lattice through classification prevents redundancy in plan space search. Notice, for ex­ ample, that the plan class Dq depends only on q, even though its position in the expression for P' is within the scope of c. A chronologically backtracking search would generate this class for every (c,q) pair encountered during the iteration, resulting in a duplication of effort if clobber­ era share consequents.

11 The term claui~d ia used here in the II&Jne sense that concepts are classified in KL-ONE [Schmolse and Lipkia, 1083]. Swartout and Neches [Swartout and Neches, 1086] represent plana by the goals they are intended to achieve and employ a cla.saifier to construct a taxonomy of intents. Their decision-making program selects from the taxonomy the moat specific pla.n for the purpose at hand. Because this taxonomy comprises complek plana, their use of classification falls outside of the planning framework developed here.

A simple dependency-recording mechanism would most likely avoid this and similar redundancies. A clever enough scheme might even recognize that At and ;w are the same when t = w. However, it is doubtful that any of the standard dependency maintenance mechanisms would catch the more subtle relationships that hold be­ tween classes created on successive recursive invocations of the planning algorithm. A precise characterization of avoidable redundancies israrely offered in descriptions of planners.

Following the terminology used by de Kleer in de­ scribing his assumption-based truth maintenance system (ATMS) [de Kleer, 1986a], each plan class is an assump­ tion context represented by the plan modification opera­ tors defining it. The plan specialization lattice corresponds to the context lattice of the ATMS with context subset re­ placed by plan subsumption. Indeed, an implementation using an ATMS would be just as powerful as the clas­ sification scheme presented here, provided that we could construct a propositional interface [de Kleer, 1986b] capa­ ble of communicating the relevant implications of partial plans. In our case, though, this does not appear feasible. A mapping of partial plans to sets of propositions would force us to create distinctions (for instance, in unique iden­ tifiers for steps) that would fail to preserve isomorphism characteristics.

Like the assumption-based approach, the plan lattice structure facilitates the exploration of multiple consistent contexts simultaneously. 7 But contrary to the ATMS view, we are not interested in finding all solutions (the class of all plans that achieve the goal). Therefore, we can restrict the domain of assumption sets that need to be considered to those explicitly created as plan classes by the planning algorithm.

To recap, the scheme presented here offers two sources of benefits with respect to plan search efficiency. First, the dominance relation provides a major new class of nogoods which may potentially shrink the search space. Second, consolidation of the lattice through classification of par­ tial plans takes advantage of dependencies that might be obscured by an interface with a propositional TMS.

VII. The Complexity of Subsumption

As for knowledge representation mechanisms, the key oper­ ation in plan classification is the computation of subsumption relations [Brachman and Levesque, 1984]. We saw above that classifying plans as they are generated mini­ mizes the search space. 8 Conversely, a perfect dependency mechanism is in effect computing these subsumptions.

7This contrasts with the dependency-directed backtracking em­ ployed by TWEAK. The design of SCHEMER [Zabih, 1987, Zabih et ol., 1987]-a dependency-directed interpreter for a non-deterministic LISP-illustrates this difference and highlights the issues in construct­ ing a propositional interface for arbitrary dependencies.

Unfortunately, nonlinear plan subsumption is NP­ complete.9 This is true even for plan classes derived ex­ clusively from addstep and order operators, that is, partial orders on steps. The exponential potential of subsumption lies in the combinatorial number of possible mappings be­ tween the steps of the two plan classes. If, however, we can specify the correspondences between steps (for exam­ ple, which put-on in P1 corresponds to which in P2), then subsumption is at worst quadratic. In practice we will gen­ erally not have complete correspondences, but typically the possible mappings between steps will be highly con­ strained. Actions may map only to others of the same type, therefore the computation will not be prohibitive as long as plan classes do not contain many steps of a single type. Codesignation constraints also help to restrict the possible mappings, as do explicit identifications among steps which may be provided by the planner when introducing steps in several partial plans at once. Finally, we might consider restricting the constraint language so that subsumption is tractable, perhaps to tree-shaped partial orders.

The effect on subsumption complexity of proposed ex­ tensions to the constraint language should also be consid­ ered. For example, we could allow actions themselves to be expressed at multiple levels of abstraction (as in the sequence low-dose steroid therapy is-a steroid therapy is­ a drug therapy) without significant cost in complexity, as long as action subsumption itself is not expensive. 10 Ex­ tending the plan modification operators to include union and intersection, as suggested by Figure 3, is not as be­ nign. Intersection (conjunction) presents no problem be­ cause the plan modification operators associate and com­ mute, but computing subsumption among classes that are unions (disjunctions) of other classes appears substantially more difficult.

VIII. Summary

In this paper I have introduced and applied some ana­ lytical tools for studying and designing constraint-posting planners. The main components of this framework are a specialization lattice and a dominance relation defined over plan classes. These concepts were motivated with simple eXamples from MOLGEN and a more detailed ac­ count of TWEAK. The power of the TWEAK algorithm re­ sides in a central dominance result which allows the plan­ ner to restrict attention to a small subset of the possi­ ble completions of a partial plan. Explicit characteriza­ tion of the dominance relation allows the planner to rec­ ognize that certain plan classes need not be explored, even though they might contain a valid plan. Although stan­ dard dependency-directed backtracking methods improve search efficiency, the only way to ensure complete lack of redundancy is to classify the partial plans in the lattice by computing subsumption among plan classes. This prob­ lem is NP-complete for nonlinear planning, but constraints commonly arising in practice may render the computation tractable. Recognizing the centrality of subsumption sug­ gests a novel approach to analyzing the complexity impli­ cations of plan constraint languages.

·For true optimality we must also determine the most general plan class that is dominated. This corresponds to extracting the minimal nogood assumption set, which is not generally feasible. Note that minimality is with respect to a particular constraint language; slight changes may have dramatic effects on the dominance prover's ability to derive nogood sets at high levels of generality. For example, Pednault [Pednault, 1985] achieves stronger dominance results . by including protected conditions as constraints on plans.

PThe proof, by reduction from EXACT COVER BY 3-SETS, was provided by Ronald L. Rivest, personal communication.

lOGiven a static action lattice, action subsumption takes logarith­ mic time. H actions are described more flexibly-perhaps as dy­ namically generated KL-ONE concepts.:_then subsumption is more complex [Brachman and Levesque, 1984].

The true test of the scheme presented here will be how well it supports tasks that require planning in the presence of uncertainty and partially satisfiable objectives. I am currently applying this framework to the design of a plan­ ner for the task of formulating decision models from a large medical knowledge base. The domain modeling language and dominance prover proposed for this task are based on ongoing work on qualitative inft.uence networks [Wellman, 1987a, Wellman, 1987b].

Acknowledgments

Discussions with Zak Kohane, Ramesh Patil, Ron "Rivest, Elisha Sacks, Peter Szolovits, Kate Unrath, Tom Wu, and Ramin Zabih contributed to the style and content of this paper.