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 $\pi$ with two open conditions p and q that both hold in the initial conditions. The heuristic cost for $\pi$ 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 $\pi$ and $\pi{^\prime}$ in case f ($\pi$) = f ($\pi{^\prime}$). Consider an alternative plan $\pi{^\prime}$ with the same number of actions as $\pi$ but with a single open condition p. This plan has heuristic cost 0 as does the plan $\pi$, but the estimated effort is only 1, so $\pi{^\prime}$ 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 h_add and h_add^r. Estimated effort helps reduce the number of generated and explored plans in all cases but one (when using h_add^r 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 h_add and h_add^r 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	*