In the preceding sections, we have shown that a partial-order planner can be more efficient simply because its search tree is smaller. With some search strategies, such as breadth-first search, this size differential obviously translates into an efficiency gain. With other strategies, such as depth-first search, the size differential translates into an efficiency gain, provided we make additional assumptions about the solution density and distribution.
However, it is often claimed that partial-order planners are more efficient due to their ability to make more informed ordering decisions, a rather different argument. For instance, Sacerdoti (1975) argues that this is the reason that NOAH performs well on problems such as the blocksworld's ``Sussman anomaly''. By delaying the decision of whether to stack A on B before or after stacking B on C, NOAH can eventually detect that a conflict will occur if it stacks A on B first, and a critic called ``RESOLVE-CONFLICTS'' can then order the steps intelligently.
In this section, we show that this argument can be formally described in terms of our two planners. We demonstrate that UA does in fact have a potential advantage over TO in that it can exploit certain types of heuristics more readily than TO. This advantage is independent of the fact that UA has a smaller search space. Whether or not this advantage is significant in practice is another question, of course. We also describe some experiments where we evaluate the effect of a commonly-used heuristic on our blocksworld problems.