...decisions.

Various versions of this well-known algorithm have appeared in the literature [Weld, 1994, Russell & Norvig, 1995, Kambhampati, Knoblock & Yang, 1995]. The version we give corresponds most directly to that given by Williamson and Hanks (1996).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...z).

An alternative approach also treats cases in which E = F as threats; this is required to make the planner systematic, i.e., guaranteed never to generate the same node more than once [McAllester & Rosenblitt, 1991].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...repairs.

Conditional planners make use of an additional method of threat resolution--confrontation--but we ignore that within this paper [Peot & Smith, 1992, Etzioni, Hanks, Weld, Draper, Lesh & Williamson 1992]. Joslin (1996) provides a detailed account of generalizing the treatment of flaws to other types of planning decisions.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...same.

In the current version of UCPOP (v.4), the flaw selection strategy that is run by default is the DSep strategy, discussed just below. For historical reasons, we maintain the name DSep for that strategy, and use UCPOP for the older default strategy.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...strategy:

The LCFR strategy is similar to the branch-1/branch-n search heuristics included in the O-Plan system [Currie & Tate, 1991]. The contribution of our original work on this topic was to isolate this strategy and examine it in detail.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...(CSPs).

When planning problems are cast as CSPs in the planner Descartes [Joslin & Pollack, 1996, Joslin, 1996], this correspondence is even more direct.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...v.4.

Note that the experiments in both our earlier LCFR paper [Joslin & Pollack, 1994] and Gerevini and Schubert's (1996) ZLIFO paper were run using an earlier version (v.2) of UCPOP. As a result, the number of nodes produced in our experiments sometimes differs from what is reported in these other two papers. This appears to be largely due to the fact that UCPOP v.4 puts the elements of a new set of open conditions onto the flaw list in the reverse order of the way in which UCPOP v.2 does [Gerevini, 1997]. As discussed below in Sections -, we studied the influence of this ordering change by also collecting data using a modified version of UCPOP v.4 in which we reversed the order of conditions entered in the open list. While the resulting numbers are similar to those previously published, they are not identical, leading us to conclude that there are additional subtle differences between v.2 and v.4. However, because all the experiments on which we report here were run using the same version of UCPOP, we believe this to be a fair comparison of the strategies.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...%-overrun.

Because of the way in which UCPOP completes its basic iteration, it sometimes will go somewhat beyond the specified node limit before terminating the run. In such cases, we used the node limit value, rather than the actual number of nodes generated, in our computation of %-overrun.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...-.

To preserve readability, in Figure , we have used ``(1)'' to denote S+OC, ``(2)'' for S+OC+UC, and ``(3)'' for S+OC+UC+.1F.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...tasks.

The difficulty that LCFR-DSep encounters by greedily picking low-cost flaws might be reduced by doing a lookahead of several planning steps, to determine a more accurate repair cost. This is the approach taken in the branch-n mechanism in O-Plan [Currie & Tate, 1991]. Significant overhead can be involved in such a strategy, however.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...domains.

We have omitted the strategies that did very poorly, performing worse both on the node- and time-limit experiments than did any of the strategies graphed. Note that we ran the reverse-order experiments only with a node limit.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...faster.

In interpreting the Trains timing data, it is important to note that some of the strategies shown--notably UCPOP, UCPOP-LC, and Dunf, failed to solve Trains2 within either the node or the time limit.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.