The max, sum, and level heuristics for the are similar to the analogous multiple graph heuristics. The main difference with these heuristics for the is that it is much easier to compute positive interaction measures than independence measures. The reason positive interaction is easier to compute is that we find the cost of a clause for all states in our belief state at once, rather than on each of multiple planning graphs. Like before, we do not consider heuristics that do not aggregate state distances.

**Positive Interaction Aggregation:**

**Max**The max heuristic for the finds the maximum clause cost across clauses of the current belief state . The cost of a clause is the first level it becomes reachable. Formally:

**Sum**The sum heuristic for the sums the individual levels where each clause in is first reachable. Formally:

**Level**The level heuristic is the index of the first level where is reachable. Formally:

**Independence Aggregation:** All heuristics mentioned for positive
interaction aggregation can be augmented to take the summation of
costs for each state in our belief state. This may be inefficient
due to the fact that we lose the benefit of having a
by
evaluating a heuristic for each state of our
, rather than all
states at once as in the positive interaction aggregation. In such
a case we are doing work similar to the multiple graph heuristic
extraction, aside from the improved graph construction time. The
positive interaction aggregation is able to implicitly calculate the
maximum over all worlds for most of the heuristics, whereas for the
sum heuristic we need to explicitly find a cost for each world. We
denote the sum heuristics as:
,
,
and
.