###

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

*h*_{add}(

*q*) =

.

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
*h*_{add}(*a*) = 1 + *h*_{add}(*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:

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:
The additive heuristic cost function for POCL plans can now be defined
as follows:

*h*_{add}(

) =

*h*_{add}(

*q*)

As with the cost function for conjunction, the above definition can
easily lead to overestimation of the number of actions needed to
complete a plan, since possible reuse is ignored. We propose a remedy
for this below.
The cost of ground literals can be efficiently computed through
dynamic programming. We take conditional effects into account in the
cost computation. If the effect *q* is conditioned by *p* in action
*a*, we add
*h*_{add}(*p*) to the cost of achieving *q* with *a*.
We only need to compute the cost for ground literals once during a
preprocessing phase, leaving little overhead for evaluating plans
during the planning phase. When working with lifted actions, there is
extra overhead for unification. It should also be noted that all
lifted literals are independently matched to ground literals without
considering interactions between open conditions of the same action.
For example, two preconditions `(a ?x)` and `(b ?x)` of
the same action can be unified to ground literals with different
matchings for the variable `?x`.

Håkan L. S. Younes

2003-08-26