VHPOP uses the *A*^{*} algorithm
(Hart, Nilsson, & Raphael, 1968) to search
through plan space. The *A*^{*} algorithm requires a search node
evaluation function
*f* (*n*) = *g*(*n*) + *h*(*n*), where *g*(*n*) is the cost of
getting to *n* from the start node (initial plan) and *h*(*n*) is the
estimated remaining cost of reaching a goal node (complete plan). We
want to find plans containing few actions, so we take the cost of a
plan to be the number of actions in it. For a plan
= ,,, we
therefore have
*g*() = ||.

The original implementations of SNLP and UCPOP used
*h*_{f}() = |()| as the heuristic cost
function, i.e. the number of flaws in a plan.
Schubert and Gerevini (1995) consider
alternatives for
*h*_{f}(), and present empirical data
showing that just counting the open conditions (
*h*_{oc}() = |()|) often gives better results. A big problem,
however, with using the number of open conditions as an estimate of
the number of actions that needs to be added is that it assumes a
uniform cost per open condition. It ignores the fact that some open
conditions can be linked to existing actions (thus requiring no
additional actions), while other open conditions can be resolved only
by adding a whole chain of actions (thus requiring more than one
action).

Recent work in heuristic search planning has resulted in more informed heuristic cost functions for state space planners. We have in previous work (Younes & Simmons, 2002) adapted the additive heuristic--first proposed by Bonet et al. (1997) and subsequently used in HSP (Bonet & Geffner, 2001b)--for plan space search and also extended it to handle negated and disjunctive preconditions of actions as well as actions with conditional effects and lifted actions. The heuristic cost function used by VHPOP at IPC3 was a variation of the additive heuristic where some reuse of actions is taken into account, coupled with the tie-breaking rank (introduced in Younes & Simmons, 2002) based on estimated remaining planning effort.

- The Additive Heuristic for POCL Planning
- Accounting for Positive Interaction
- Estimating Remaining Effort

2003-08-26