...

Backstrom (1993) formalizes the problem of removing unnecessary orderings in order to produce a ``least-constrained'' plan. He shows that the problem is polynomial if one defines a least-constrained plan as a plan in which no orderings can be removed without impacting the correctness of the plan. Backstrom also shows that the problem of finding a plan with the fewest orderings over a given operator set is a much harder problem; it is NP-hard.

...

There is a unique last deleter in U. This follows from our requirement that for any operator in our language, the deleted conditions must be a subset of the preconditions. If two unordered steps delete the same condition, then that condition must also be a precondition of both operators. Hence, the two steps interact and will be ordered by UA.

...

The reader may question why maps U to all its linearizations in that share common derivation ancestry, as opposed to simply mapping U to all its linearizations in . The reason is that our planners are not systematic, in the sense that they may generate two or more plans with the same operator sequence. We can distinguish such plans by their derivational history. For example, suppose two instantiations of the same operator sequence exist within a but they correspond to different plans in . relies on their different derivations to determine the appropriate correspondence.

...

We assume that the size of the operators (the number of preconditions and effects) is bounded by a constant for a given domain.

...

Since Steps 3 and 4 are nondeterministic, we need to be clear about our terminology. We say that Step 3 is executed once each time a different operator is chosen, and Step 4 is executed once for each different combination of orderings that is selected.

...

For perspicuity, we ignore the fact that the number of nodes explored by the two planners on the last level may differ if the planners stop when they reach the first solution.

...

Since the depth-limit is equal to the length of the shortest solution, an iterative deepening (Korf, 1985) approach would yield similar results. Additionally, we note that increasing the depth-limit past the depth of the shortest solution does not significantly change the outcome of these experiments.

...

This definition of solution density is ill-defined for infinite trees, but we assume that a depth-bound is always provided, so only a finite subtree is explicitly enumerated.

...

In our experiments, a nondeterministic goal selection procedure was used with our planners, which meant that the solution density could vary from run to run. We compared the average solution density over 25 trials for each problem to obtain our results.

...

Even if the solutions are distributed randomly amongst the leaves of the trees with uniform probability (as opposed to being distributed ``perfectly uniformly''), there will be some clusters of nodes. Therefore, TO will have a small disadvantage. To see this, let us suppose that each leaf of both and is a solution with equal probability p. That is, if has leaves, of which are solutions, and has leaves, of which are solutions, then . In general, if k out of N nodes are solutions, the expected number of nodes that must be tested to find a solution is when and approaches as k (and N) approaches . (This is simply the expected number of samples for a binomial distribution.) Therefore, since , the expected number of leaves explored by TO is greater than or equal to the expected number of leaves explored by UA, by at most a factor of 2.

...

The iterative sampling strategy was depth-limited in exactly the same way that our depth-first strategy was. We note, however, that the performance of iterative sampling is relatively insensitive to the actual depth-limit used.

...

In Section 9.2, we discuss planners that are ``less-committed'' than UA. For such planners, the advantage due to heuristics might be more pronounced since they ``delay'' their decisions even longer than UA.

...

Instead of exploring only those plan extensions with the fewest goals at each choice point, an alternative strategy is to assign each extension a probability that is inversely correlated with the number of goals, and pick accordingly. Given a depth bound, this strategy has the advantage of being asymptotically complete. We used the simpler strategy here for pedagogical reasons.

...

For simplicity, the modifications used to create UA-C are not very sophisticated. As a result, UA-C's space may be larger than it needs to be in some circumstances, since it aggressively commits to specializations. A more sophisticated set of modifications is possible; however, the subtlies involved in efficiently planning with dependency conditions (Pednault, 1988; Penberthy & Weld, 1992; Collins & Pryor,1992) are largely irrelevant to our discussion.

...

In fact, Step 4b be implemented so that the time cost is O(e), using the graph traversal techniques described in Section 6. As a result the UA-C implementation and the corresponding TO-C implementation have the same time cost per node for this new language as they did for the original language, O(e) and O(n), respectively.

...

We use Tweak for this comparison because, like UA and TO, it is a formal construct rather than a realistic planner, and therefore more easily analyzed.