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 $\mathcal {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_add(q) = $$\left\{\vphantom{\begin{array}{ll} 0 & \mbox{if $q$\ unifies with... ...thcal{GA}(q) \neq \emptyset$}\\ \infty & \mbox{otherwise} \end{array}}\right.$$$$\begin{array}{ll} 0 & \mbox{if $q$\ unifies with a literal that h... ...{if $\mathcal{GA}(q) \neq \emptyset$}\\ \infty & \mbox{otherwise} \end{array}$$.

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:

h_add($$\exists$$x.$$\phi$$) = h_add($$\phi$$)

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_add($$\bigwedge_{i}^{}$$$$\phi_{i}^{}$$) = $$\sum_{i}^{}$$h_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 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:

h_add($$\bigvee_{i}^{}$$$$\phi_{i}^{}$$) = $$\min_{i}^{}$$h_add($$\phi_{i}^{}$$)

The additive heuristic cost function for POCL plans can now be defined as follows:

h_add($$\pi$$) = $$\sum_{{\stackrel{q}{\longrightarrow}\!a_i\in\mathcal{OC}(\pi)}}^{}$$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.