In the preceding sections, we showed that the primary advantage that UA has over TO is that UA's search tree may be exponentially smaller than TO's search tree, and we also showed that UA only pays a small (polynomial) extra cost per node for this advantage. Thus far we have assumed a very restricted planning language in which the operators are propositional; however, most practical problems demand operators with variables, conditional effects, or conditional preconditions. With a more expressive planning language, will the time cost per node be significantly greater for UA than for TO? One might think so, since the work required to identify interacting steps can increase with the expressiveness of the operator language used (Dean & Boddy, 1988; Hertzberg & Horz, 1989). If the cost of detecting step interaction is high enough, the savings that UA enjoys due to its reduced search space will be outweighed by the additional expense incurred at each node.
Consider the case for simple breadth-first search. Earlier we showed
that the ratio of the total time costs of TO and UA is as
follows, where the subtree considered by UA under breadth-first search
is denoted by 
, the number of steps in plan a U is
denoted by 
, and the number of edges in U is denoted by 
:
This cost comparison is specific to the simple propositional operator
language used so far, but the basic idea is more general. UA will
generally outperform TO whenever its cost per node is less than the
product of the cost per node for TO and the number of TO nodes
that correspond under 
. Thus, UA could incur an exponential
cost per node and still outperform TO in some cases. This can
happen, for example, if the exponential number of linearizations of a
UA partial order is greater than the exponential cost per node for
UA. In general, however, we would like to avoid the case where UA
pays an exponential cost per node and, instead, consider an approach
that can guarantee that the cost per node for UA remains polynomial
(as long as the cost per node for TO also remains polynomial).
The cost per node for UA is dominated by the cost of updating the goal set (Step 5) and the cost of selecting the orderings (Step 4). Updating the goal set remains polynomial as long as a plan is unambiguous. Since each precondition in an unambiguous plan is either necessarily true or necessarily false, we can determine the truth value of a given precondition by examining its truth value in an arbitrary linearization of the plan. Thus, we can simply linearize the plan and then use the same procedure TO uses for calculating the goal set. As a result, it is only the cost of maintaining the unambiguous property (i.e., Step 4) that is impacted by more expressive languages. One approach for efficiently maintaining this property relies on a ``conservative'' ordering strategy in which operators are ordered if they even possibly interact.
As an illustration of this approach, consider a simple propositional language with conditional effects, such as ``if p and q, then add r''. Hence, an operator can add (or delete) propositions depending on the state in which it is applied. We refer to conditions such as ``p'' in our example as dependency conditions. (Note that, like preconditions, dependency conditions are simple propositions.) Chapman (1987) showed that with this type of language it is NP-hard to decide whether a precondition is true in a partially ordered plan. However, as we pointed out above, for the special case of unambiguous plans, this decision can be accomplished in polynomial time.
Formally, the language is specified as follows. An operator O, as
before, has a list of preconditions, pre(O), a list of
(unconditional) adds, adds(O), a list of (unconditional) deletes,
dels(O). In addition, it has a list of conditional adds,
cadds(O), and a list of conditional deletes, cdels(O); both
containing pairs 
, where 
is a
conjunctive set of dependency conditions and e is the conditional
effect (either an added or a deleted condition). Analogous with the
constraint that every delete must be a precondition, every conditional
delete must be a member of its dependency conditions; that is, for
every 
cdels(O), 
.
Figure 12 shows a version of the UA algorithm, called UA-C,
which is appropriate for this language. The primary difference
between the UA and UA-C algorithms is that in both Steps 3 and 4b
an operator may be specialized with respect to a set of
dependency conditions. The function specialize(O, D ) accepts a
plan step, O, and a set of dependency conditions, D; it returns a
new step O' that is just like O, but with certain conditional
effects made unconditional. The effects that are selected for this
transformation are exactly those whose dependency conditions are a
subset of D. Thus, the act of specializing a plan step is the act
of committing to expanding its causal role in a plan.
Once a step is
specialized, UA-C has made a commitment to use it for a given set of
effects. Of course, a step can be further specialized in a later
search node, but specializations are never retracted.
More precisely, the definition of 
,
where O is a step, D is a conjunctive set of dependency conditions
in O, and 
is the set difference operator, is as
follows.
.
.
.
.
.
The definition of step interaction is generalized for UA-C as follows. We say that two steps in a plan interact if they are unordered with respect to each other and the following disjunction holds:
Figure 12: The UA-C planning algorithm
Figure 13 shows a schematic example illustrating how UA-C
extends a plan. The preconditions of each operator are shown on the
left of each operator, and the unconditional adds on the right. (We
only show the preconditions and effects necessary to illustrate the
specialization process; no deletes are used in the example.)
Conditional adds are shown underneath each operator. For instance, the
first operator in the plan at the top of the page has precondition
p. This operator adds q and conditionally adds u
if t is true. The figure illustrates two of the plans produced
as a result of adding a new conditional operator to the plan. In one
plan, the conditional effects 
and 
are selected in the specialization process, and in the other plan
they are not.
Figure 13: An example illustrating the UA-C algorithm
The new step, Step 4b, requires only polynomial time per plan generated, and the time cost of the other steps are the same as for UA. Hence, as with our original UA algorithm, the cost per node for the UA-C algorithm is polynomial.
TO can also handle this language given the corresponding
modifications (changing Step 3 and adding Step 4b), and the time cost
per plan also remains polynomial. Moreover, the same relationship holds between the two
planners' search spaces - 
is never larger than
and can be exponentially smaller. This example
illustrates that the theoretical advantages that UA has over TO
can be preserved for a more expressive language. As we pointed out,
our definition of interaction is a sufficient criterion for
guaranteeing that the resulting plans are unambiguous, but it is not a
necessary criterion. Nevertheless, this conservative approach allows
interactions to be detected via a simple inexpensive syntactic test.
Essentially, we have kept the cost per node for UA-C low by
restricting the search space it considers, as shown in
Figure 14. UA-C only considers unambiguous plans that can
be generated via its ``conservative'' ordering strategy. UA-C is
still a partial-order planner, and it is complete, but it does not
consider all partially ordered plans or even all unambiguous
partially ordered plans.
Figure 14: Hierarchy of Plan Spaces
The same ``trick'' can be used for other languages as well, provided that we can devise a simple test to detect interacting operators. For example, in previous work (Minton et al., 1991b) we showed how this can be done for a language where operators can have variables in their preconditions and effects. In the general case, for a given UA plan and a corresponding TO plan, Steps 1,2, and 3 of the UA algorithm cost the same as the corresponding steps of the TO algorithm. As long as the plans considered by UA are unambiguous, Step 5 of the UA algorithm can be accomplished with an arbitrary linearization of the plan, in which case it costs at most O(e) more than Step 5 of the TO algorithm. Thus, the only possibility for additional cost is in Step 4. In general, if we can devise a ``local'' criterion for interaction such that the resulting plan is guaranteed to be unambiguous, then the ordering selection step can be accomplished in polynomial time. By ``local'', we mean a criterion that only considers operator pairs to determine interactions; i.e., it must not examine the rest of the plan.
Although the theoretical advantages that UA has over TO can be preserved for more expressive languages, there is a cost. The unambiguous plans that are considered may have more orderings than necessary, and the addition of unnecessary orderings can increase the size of UA's search tree. The magnitude of this increase depends on the specific language, domain, and problem being considered. Nevertheless, we can guarantee that UA's search tree is never larger than TO's.
The general lesson here is that the cost of plan extension is not solely dependent on the expressiveness of the operator language, it also depends on the nature of the plans that the planner considers. So, although the extension of partially ordered plans is NP-hard for languages with conditional effects, if the space of plans is restricted (e.g., only unambiguous plans are considered) then this worst-case situation is avoided.