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.
Håkan L. S. Younes