
| Problem      | hadd          | with effort   | h r add       | with effort   | RePOP         |
|--------------|---------------|---------------|---------------|---------------|---------------|
| gripper-8    | 1636 / 705    | 1089 / 449    | *             | *             | *             |
| gripper-10   | 3268 / 1359   | 1958 / 795    | *             | *             | *             |
| gripper-12   | 5879 / 2359   | 3224 / 1294   | *             | *             | *             |
| gripper-20   | 33848 / 12204 | 14386 / 5558  | *             | *             | *             |
| rocket-ext-a | 34917 / 25810 | 27846 / 20028 | 24507 / 15790 | 31213 / 20321 | 30110 / 17768 |
| rocket-ext-b | 27871 / 20034 | 27277 / 19363 | 15919 / 9000  | 10914 / 6705  | 85316 / 51540 |
| logistics-a  | 503 / 301     | 481 / 287     | 621 / 389     | 530 / 317     | 411 / 191     |
| logistics-b  | 857 / 488     | 713 / 404     | 694 / 402     | 584 / 326     | 920 / 436     |
| logistics-c  | 766 / 422     | 630 / 346     | 629 / 353     | 438 / 227     | 4939 / 2468   |
| logistics-d  | 3039 / 1398   | 2950 / 1384   | 2525 / 1300   | 1472 / 682    | *             |

Table 2: The number of generated/explored plans for hadd and h r add **both without and with**
estimated effort as a tie-breaker. The RePOP **column contains the numbers reported by Nguyen and Kambhampati (2001) for** RePOP **using the serial planning**
graph heuristic. These numbers are included only for the purpose of showing that there seems to be a qualitative difference between the RePOP **heuristic and the**
heuristics used by VHPOP**. An asterisk (*) means that no solution was found**
after generating 100000 plans. Flaws were selected in LIFO order.

## 3.2 Flaw Selection Strategies

In the original implementations of SNLP and UCPOP **threats are selected before open**
conditions. When there is more than one threat (or open condition) that can be selected, the one added last is selected first (LIFO order). Several alternative flaw selection strategies have been proposed in an attempt to improve the performance exhibited by POCL planners.

Peot and Smith (1993) show that the number of searched plans can be reduced by delaying the resolution of some threats. The most successful of the proposed delay strategies are DSep, which delays threats that can be resolved through separation, and DUnf, which delays threats that can be resolved in more than one way.

Joslin and Pollack (1994) suggest that all flaws should be treated uniformly, and that the flaw with the least number of refinements should be selected first. Their flaw selection strategy, LCFR, can be viewed as an instance of the most-constrained-variable heuristic used in simple search rearrangement backtracking (Bitner & Reingold, 1975; Purdom, 1983). The main disadvantage with LCFR is that computing the repair cost for every flaw can incur a large overhead for flaw selection. This can lead to longer planning times compared to when using the default UCPOP **strategy, even if the number of search nodes is significantly**
smaller with LCFR. A clever implementation of LCFR can, however, reduce the overhead for flaw selection considerably.

Schubert and Gerevini (1995) argue that a LIFO strategy for selecting open conditions helps the planner maintain focus on the achievement of a particular high-level goal. Their ZLIFO strategy is a variation of the DSep strategy, with the difference being that open conditions that cannot be resolved, or can be resolved in only one way, are selected before open conditions that can be resolved in more than one way. Gerevini and Schubert (1996) present results indicating that ZLIFO often needs to generate fewer plans than LCFR before a solution is found, and has a smaller overhead for flaw **selection. These results are**