Multiple Planning Graph Heuristics ($MG$ )

Similar to the various relaxed plan heuristics for the multiple graphs, we can compute a max, sum, or level heuristic on each of the multiple planning graphs and aggregate them with a maximum or summation to respectively measure positive interaction or independence. The reason we cannot aggregate the individual graph heuristics to measure overlap is that they are numbers, not sets of actions. Measuring overlap involves taking the union of heuristics from each graph and the union of numbers is not meaningful like the union of action sets from relaxed plans. Like before, there is no reason to use multiple graphs if there is no state distance aggregation.

Positive Interaction Aggregation:

• Max The max heuristic $h^{MG}_{m-max}$ is computed with multiple planning graphs to measure positive interaction in the $h^{MG}_{m-max}$ heuristic. This heuristic computes the maximum cost clause in $\kappa(BS_i)$ for each graph $\gamma \in \Gamma$ , similar to how $h^{SG}_{m-max}(BS_i)$ is computed, and takes the maximum. Formally:

  $$h^{MG}_{m-max}(BS_i) = \max\limits_{\gamma\in{\Gamma}}\left(h^{\gamma}_{max}(BS_i)\right)$$

  
  
  The $h^{MG}_{m-max}$ heuristic considers the minimum cost, relevant literals of a belief state (those that are reachable given a possible world for each graph $\gamma$ ) to get state measures. The maximum is taken because the estimate accounts for the worst (i.e., the plan needed in the most difficult world to achieve the subgoals).

• Sum The sum heuristic that measures positive interaction for multiple planning graphs is $h^{MG}_{m-sum}$ . It computes the summation of the cost of the clauses in $\kappa(BS_i)$ for each graph $\gamma \in \Gamma$ and takes the maximum. Formally:

  $$h^{MG}_{m-sum}(BS_i) = \max\limits_{\gamma\in{\Gamma}}\left(h^{\gamma}_{sum}(BS_i)\right)$$

  
  
  The heuristic considers the minimum cost, relevant literals of a belief state (those that are reachable given the possible worlds represented for each graph $\gamma$ ) to get state measures. As with $h^{MG}_{m-max}$ , the maximum is taken to estimate for the most costly world.

• Level Similar to $h^{MG}_{m-max}$ and $h^{MG}_{m-sum}$ , the $h^{MG}_{m-level}$ heuristic is found by first finding $h^{\gamma}_{level}$ for each graph $\gamma \in \Gamma$ to get a state distance measure, and then taking the maximum across the graphs. $h^{\gamma}_{level}(BS_i)$ is computed by taking the minimum among the $\hat{S} \in \hat{\xi}(BS_i)$ , of the first level $lev^{\gamma}(\hat{S})$ in the planning graph $\gamma$ where literals of $\hat{S}$ are present with none of them marked mutex. Formally:

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

  
  
  and

  $$h^{MG}_{m-level}(BS_i) = \max\limits_{\gamma\in{\Gamma}}(h^{\gamma}_{level}(BS_i))$$

  
  

  Note that this heuristic is admissible. By the same reasoning as in classical planning, the first level where all the subgoals are present and non-mutex is an underestimate of the true cost of a state. This holds for each of the graphs. Taking the maximum accounts for the most difficult world in which to achieve a constituent of $BS_i$ and is thus a provable underestimate of $h^{*}$ . GPT's max heuristic [6] is similar to $h^{MG}_{m-level}$ , but is computed with dynamic programming in state space rather than planning graphs.

Independence Aggregation: All heuristics mentioned for Positive Interaction Aggregation can be augmented to take the summation of costs found on the individual planning graphs rather than the maximum. We denote them as: $h^{MG}_{s-max}$ , $h^{MG}_{s-sum}$ , and $h^{MG}_{s-level}$ . None of these heuristics are admissible because the same action may be used in all worlds, but we count its cost for every world by using summation.