### 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 (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

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

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:

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:

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 overestimation of the actual cost of a conjunctive goal (i.e. the heuristic is not admissible). The cost of a disjunction is taken to be the cost of the disjunct with minimal cost: