Local Flaw Selection.

By retaining the LIFO order for selecting open conditions achievable in multiple ways, Schubert and Gerevini (1995) argue that the planner tends to maintain focus on a particular higher-level goal by regression, instead of trying to achieve multiple goals in a breadth-first manner. When some of the goals to achieve are independent, maintaining focus on a single goal should be beneficial. The problem with a LIFO-based flaw selection strategy, however, as pointed out by Williamson and Hanks (1996), is that it is highly sensitive to the order in which operator preconditions are specified in the domain description.

It is not necessary, however, to select the most recently added open condition in order to keep focus on the achievement of one goal. We can get the same effect by selecting any of the open conditions, but restrict the choice to the most recently added action. We therefore introduce a new flaw type, ``l'', representing local open conditions. A local open condition is one that belongs to the most recently added action that still has remaining open conditions. We can use any ordering criterion to select among local open conditions. Using this new flaw type, we can specify a local variant of LCFR:

LCFR-Loc    {n, s, l}LR

One would expect such a strategy to be less sensitive to precondition-order than a simple LIFO-based strategy. We can see evidence of this in Table 5, which also shows that the maintained goal focus achieved by local flaw selection strategies can help solve more problems compared to a global flaw selection strategy.

Table: Relative standard deviation for the number of generated plans ( $\sigma$/|$\mu$|) and the number of solved problems (n) over 20 instances of each problem with random precondition ordered. Low relative standard deviation indicates low sensitivity to precondition order. Results are shown for VHPOP using seven different flaw selection strategies. A memory limit of 512Mb was enforced, and h_add^r with estimated effort as tie-breaker was used as plan ranking heuristic.

Problem UCPOP LCFR LCFR-Loc MC MC-Loc      MW       MW-Loc 

$$\sigma \mu \sigma \mu \sigma \mu \sigma \mu \sigma \mu \sigma \mu \sigma \mu$$ n n n n n n n

DriverLog6 0.20 20 0.01 20 0.01 20 0.18 20 0.23 20 0.02 20 0.02 20

DriverLog7 0.23 20 0.10 20 0.32 20 0.13 18 0.25 20 - 0 0.05 20

DriverLog8 0.28 17 - 0 0.00 1 - 0 - 0 - 0 - 0

DriverLog9 0.62 7 0.00 10 0.45 14 - 0 0.01 20 - 0 0.01 20

DriverLog10 0.33 16 - 0 0.07 20 - 0 0.08 20 - 0 0.08 20

ZenoTravel6 0.27 20 0.03 7 0.22 20 - 0 0.00 20 - 0 0.00 20

ZenoTravel7 0.23 8 - 0 0.18 16 - 0 0.16 16 - 0 0.16 16

ZenoTravel8 0.29 11 - 0 0.15 19 - 0 0.18 20 - 0 0.18 20

ZenoTravel9 0.22 17 - 0 0.21 18 - 0 0.19 20 - 0 0.19 20

ZenoTravel10 0.26 18 - 0 0.22 17 - 0 0.15 19 - 0 0.15 19

Satellite6 0.20 19 - 0 0.02 20 - 0 0.02 20 - 0 0.02 20

Satellite7 0.54 9 - 0 0.03 20 - 0 0.07 20 - 0 0.07 20

Satellite8 0.35 8 - 0 0.02 20 - 0 0.07 4 - 0 0.07 4

Satellite9 0.34 7 - 0 0.00 1 - 0 0.00 1 - 0 0.00 1

Satellite10 0.32 9 - 0 0.01 20 - 0 - 0 - 0 - 0