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.

## 3.1.1 The Additive Heuristic For Pocl Planning

The key assumption behind the additive heuristic is subgoal **independence. We give a**
recursive definition of the additive heuristic for POCL planning, starting at the level of literals and working towards a definition of heuristic cost for a partial plan.

Given a literal q, let GA(q**) be the set of ground actions having an effect that unifies**
with q. The cost of the literal q **can then be defined as**

$$h_{\mathrm{add}}(q)=\left\{\begin{array}{ll}0&\mbox{if$q$unifies with a literal that holds initially}\\ \min_{a\in\mathcal{A}(q)}h_{\mathrm{add}}(a)&\mbox{if$\mathcal{G}\mathcal{A}(q)\neq\emptyset$}\\ \infty&\mbox{otherwise}\end{array}\right.$$
.
A positive literal q **holds initially if it is part of the initial conditions. A negative literal** ¬q holds initially if q **is not part of the initial conditions (the closed-world assumption). The**
cost of an action a is

## Hadd(A**) = 1 +** Hadd(**Prec**(A)),

where Prec(a) is a propositional formula in negation normal form representing the preconditions of action a**. A propositional formula is in negation normal form if negations only**
occur at the level of literals. Any propositional formula can be transformed into negation normal form, and this is done for action preconditions by VHPOP **while parsing the domain**
description file.

Existentially quantified variables in an action precondition can be treated as additional parameters of the action. The cost of an existentially quantified precondition can then simply be defined as follows:
hadd(∃x.φ) = hadd(φ)
We can deal with universally quantified preconditions by making them fully instantiated in a preprocessing phase, so in order to complete the definition of heuristic cost for action preconditions we only need to add definitions for the heuristic cost of conjunctions and disjunctions. The cost of a conjunction is the sum of the cost **of the conjuncts:**

$$h_{\mathrm{add}}({\bigwedge_{i}\phi_{i}})=\sum_{i}h_{\mathrm{add}}(\phi_{i})$$

The summation in the above formula is what gives the additive **heuristic its name. The** definition is based on the assumption that subgoals are independent, which can lead to