First, let us identify how it is that UA can make better use of
certain heuristics than TO. In the UA planning algorithm, step
4 arbitrarily orders interacting plan steps. Similarly, Step 4 of
TO arbitrarily chooses an insertion point for the new step. It
is easy to see, however, that some orderings should be tried before
others in a heuristic search. This is illustrated by
Figure 9, which compares UA and TO on a
particular problem. The key in the figure describes the relevant
conditions of the library operators, where preconditions are indicated
to the left of an operator and added conditions are indicated to the
right (there are no deletes in this example). For brevity, the
initial step and final step of the plans are not shown. Consider the
plan in 
with unordered steps 
and 
. When
UA introduces 
to achieve precondition p of , Step 4
of UA will order with respect to , since these steps
interact. However, it makes more sense to order before ,
since achieves precondition q of . This illustrates a
simple planning heuristic that we refer to as the min-goals
heuristic: ``prefer the orderings that yield the fewest false
preconditions''. This heuristic is not guaranteed to produce the
optimal search or the optimal plan, but it is commonly used. It is the
basis of the ``resolve conflicts'' critic that Sacerdoti employed in
his blocksworld examples.
Figure 9: Comparison of UA and TO on an example.
Notice, however, that TO cannot exploit this heuristic as
effectively as UA because it prematurely orders
with respect to . Due to this inability to postpone an
ordering decision, TO must choose arbitrarily between the plans
and 
, before the impact of
this decision can be evaluated.
In the general case, suppose h is a heuristic that can be applied to
both partially ordered plans and totally ordered plans. Furthermore,
assume h is a ``useful'' heuristic; i.e., if h rates one
plan more highly than another, a planner that explores the more highly
rated plan first will perform better on average. Then, UA will
have a potential advantage over TO provided that h satisfies
the following property: for any UA plan U and corresponding
TO plan T, 
; that is, a partially ordered plan
must be rated at least as high as any of its linearizations. (Note
that for unambiguous plans, the min-goals heuristic satisfies this
property since it gives identical ratings to a partially ordered plan
and its linearizations.)
UA has an advantage over TO because if UA is expanding plan U and TO is expanding a corresponding plan T, then h will rate some child of U at least as high as the most highly rated child of T. This is true since every child of T is a linearization of some child of U, and therefore no child of T can be rated higher than a child of U. Furthermore, there may be a child of U such that none of its linearizations is a child of T, and therefore this child of U can be rated higher than every child of T. Since we assumed that h is a useful heuristic, this means that UA is likely to make a better choice than TO.