### Estimating Remaining Effort

Not only do we want to find plans consisting of few actions, but we also want to do so exploring as few plans as possible. Schubert and Gerevini (1995) suggest that the number of open conditions can be useful as an estimate of the number of refinement steps needed to complete a plan. We take this idea a bit further.

When computing the heuristic cost of a literal, we also record the estimated effort of achieving the literal. A literal that is achieved through the initial conditions has estimated effort 1 (corresponding to the work of adding a causal link to the plan). If the cost of a literal comes from an action a, the estimated effort for the literal is the estimated effort for the preconditions of a, plus 1 for linking to a. Finally, the estimated effort of a conjunction is the sum of the estimated effort of the conjuncts, while the estimated effort of a disjunction is the estimated effort of the disjunct with minimal cost (not effort).

The main difference between heuristic cost and estimated effort of a plan is that estimated effort assigns the value 1 instead of 0 to literals that can be unified with an initial condition. To illustrate the difference, consider a plan with two open conditions p and q that both hold in the initial conditions. The heuristic cost for is 0, while the estimated effort is 2. The estimated effort is basically a heuristic estimate of the total number of open conditions that will have to be resolved before a complete plan is found, and it is used as a tie-breaker between two plans and in case f () = f (). Consider an alternative plan with the same number of actions as but with a single open condition p. This plan has heuristic cost 0 as does the plan , but the estimated effort is only 1, so would be selected first if estimated effort is used as a tie-breaker. Table 2 shows that using estimated effort as a tie-breaker can have a notable impact on planner performance for both hadd and haddr. Estimated effort helps reduce the number of generated and explored plans in all cases but one (when using haddr on problem rocket-ext-a).

Estimated effort is not only useful as a plan ranking heuristic, but also for heuristic flaw selection as we will soon see.

Table: The number of generated/explored plans for hadd and haddr 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.
 Problem hadd with effort haddr 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 *

Håkan L. S. Younes
2003-08-26