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_{\mathrm{add}}(\bigvee_{i}\phi_{i})=\operatorname*{min}_{i}h_{\mathrm{add}}(\phi_{i})$$
i
The additive heuristic cost function for POCL plans can now be defined as follows:

$$h_{\mathrm{add}}(\pi)=\sum_{\stackrel{q}{\longrightarrow}a_{i}\in{\mathcal{O C}}(\pi)}h_{\mathrm{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** hadd(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.

## 3.1.2 Accounting For Positive Interaction

The additive heuristic does not take reuse of actions (other **than the dummy action** a0)
into account, so it often overestimates the actual number of **actions needed to complete** a plan. The need to take positive interaction into account in **order to obtain a more**
accurate heuristic estimate has been recognized in both state space planning (Nguyen & Kambhampati, 2000; Hoffmann & Nebel, 2001; Refanidis & Vlahavas, 2001) and plan space planning (Nguyen & Kambhampati, 2001). For IPC3 we used a slight modification of the additive heuristic to address the issue of action reuse:

$$h_{\mathrm{add}}^{\mathrm{r}}(\pi)=\sum_{\stackrel{q}{\longrightarrow}a_{i}\in\mathcal{O}\mathcal{C}(\pi)}{\left\{\begin{array}{l l}{0}&{{\mathrm{if~}\exists a_{j}\in\mathcal{A}\mathrm{~s.t.~an~effect~of~}a_{j}{\mathrm{~unifies~with~}}q}\\ {}&{{\mathrm{and~}}a_{i}\prec a_{j}\not\in\mathcal{O}}\end{array}\right.}$$

The underlying assumption for this heuristic cost function **is that an open condition** q
−→ai that can possibly be resolved by linking to the effect of an existing action aj **will not give**
rise to a new action when resolved. This can of course lead to an overly optimistic estimate of the number of actions required to complete the plan. The modified heuristic is still not admissible, however, since the same cost value as before is used for open conditions that cannot be linked to effects of existing actions. In other words, we only account for possible reuse of existing actions and not potential actions.

To illustrate the difference between hadd(π**) and** h r add(π**) consider a planning domain**
with two action schemas A1 and A2, where A1 has no preconditions and A2 **has a single**