Labelled Uncertainty Graph ($LUG$ )

The max, sum, and level heuristics for the $LUG$ are similar to the analogous multiple graph heuristics. The main difference with these heuristics for the $LUG$ 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 $h^{LUG}_{m-max}$ for the $LUG$ finds the maximum clause cost across clauses of the current belief state $BS_i$ . The cost of a clause is the first level it becomes reachable. Formally:

  $$h^{LUG}_{m-max}(BS_i) = \max\limits_{C \in \kappa(BS_i)}\left(\min\limits_{k: BS_P \models \ell_k^*(C)} k\right)$$

  
  
  
  

• Sum The sum heuristic $h^{LUG}_{m-sum}$ for the $LUG$ sums the individual levels where each clause in $\kappa(BS_i)$ is first reachable. Formally:

  $$h^{LUG}_{m-sum}(BS_i) = \sum\limits_{C \in \kappa(BS_i)}\left(\min\limits_{ k: BS_P \models \ell_k^*(C)} k\right)$$

  
  
  
  
• Level The level heuristic $h^{LUG}_{m-level}$ is the index of the first level where $BS_i$ is reachable. Formally:

  $$h^{LUG}_{m-level}(BS_i) = \min\limits_{ k: BS_P \models \ell_k^*(BS_i) } i$$

  
  
  
  

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 $LUG$ by evaluating a heuristic for each state of our $BS_P$ , 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: $h^{LUG}_{s-max}$ , $h^{LUG}_{s-sum}$ , and $h^{LUG}_{s-level}$ .