Plan Selection Heuristic

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 $\pi$ = $\langle$$\mathcal {A}$,$\mathcal {L}$,$\mathcal {O}$,$\mathcal {B}$$\rangle$ we therefore have g($\pi$) = |$\mathcal {A}$|.

The original implementations of SNLP and UCPOP used h_f($\pi$) = |$\mathcal {F}$($\pi$)| as the heuristic cost function, i.e. the number of flaws in a plan. Schubert and Gerevini (1995) consider alternatives for h_f($\pi$), and present empirical data showing that just counting the open conditions ( h_oc($\pi$) = |$\mathcal {OC}$($\pi$)|) 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.