Single Planning Graph Heuristics ($SG$ )

Like, the relaxed plan for the single unmodified planning graph, we cannot aggregate state distances because all notion of separate states is lost in forming the initial literal layer, thus we only compute heuristics that do not aggregate state distances.

No State Aggregation:

• Max In classical planning, the maximum cost literal is used to get a max heuristic, but we use formulas to describe our belief states, so we take the maximum cost clause as the cost of the belief state to find the max heuristic $h^{SG}_{max}$ . The maximum cost clause of the belief state, with respect to a single planning graph, is:

  $$h^{SG}_{max}(BS_i) = \max\limits_{C\in{\kappa(BS_i)}} cost(C)$$

  
  
  where the cost of a clause is:

  $$cost(C) = \min\limits_{l\in{C}} \min\limits_{k: l \in {\cal L}_k}k$$

  
  
  Here we find the cheapest literal as the cost of each clause to find the maximum cost clause. This is an underestimate of the closest state to our current belief state.

• Sum Like the classical planning sum heuristic, we can take the sum $h^{SG}_{sum}$ of the costs of the clauses in our belief state to estimate our belief state distance

  $$h^{SG}_{sum}(BS_i) = \sum\limits_{C\in{\kappa(BS_i)}} cost(C)$$

  
  

  This heuristic takes the summation of costs of literals in the closest estimated state in the belief state, and is inadmissible because there may be a single action that will support every clause, and we could count it once for each clause.

• Level When we have mutexes on the planning graph, we can compute a level heuristic $h^{SG}_{level}$ (without mutexes the level heuristic is equivalent to the max heuristic). The level heuristic maintains the admissibility of the max heuristic but improves the lower bound by considering what level of the planning graph all literals in a constituent are non-pairwise mutex. The level heuristic is computed by taking the minimum among the $\hat{S} \in \hat{\xi}(BS_i)$ , of the first level ($lev({S})$ ) in the planning graph where literals of $\hat{S}$ are present with none of them marked pairwise mutex. Formally:

  $$h^{SG}_{level}(BS_i) = \min\limits_{\hat{S}\in \hat{\xi}(BS_i)}lev(\hat{S})$$