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
.