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:
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 .