Multiple Graph Heuristics ($MG$ )

Single graph heuristics are usually uninformed because the projected belief state $BS_P$ often corresponds to multiple possible states. The lack of accuracy is because single graphs are not able to capture propagation of multiple world support information. Consider the CBTC problem where the projected belief state is $BS_I$ and we are using a single graph $SG^U$ . If DunkP1 were the only action we would say that $\neg$ arm and $\neg$ clog can be reached at a cost of two, but in fact the cost is infinite (since there is no DunkP2 to support $\neg$ arm from all possible worlds), and there is no strong plan.

To account for lack of support in all possible worlds and sharpen the heuristic estimate, a set of multiple planning graphs $\Gamma$ is considered. Each $\gamma \in \Gamma$ is a single graph, as previously discussed. These multiple graphs are similar to the graphs used by CGP [30], but lack the more general cross-world mutexes. Mutexes are only computed within each graph, i.e. only same-world mutexes are computed. We construct the initial layer ${\cal L}^{\gamma}_{0}$ of each graph $\gamma$ with a different state $S \in {\cal M}(BS_P)$ . With multiple graphs, the heuristic value of a belief state is computed in terms of all the graphs. Unlike single graphs, we can compute different world aggregation measures with the multiple planning graphs.

While we get a more informed heuristic by considering more of the states in ${\cal M}(BS_P)$ , in certain cases it can be costly to compute the full set of planning graphs and extract relaxed plans. We will describe computing the full set of planning graphs, but will later evaluate (in Section 6.4) the effect of computing a smaller proportion of these. The single graph $SG^1$ is the extreme case of computing fewer graphs.

To illustrate the use of multiple planning graphs, consider our example CBTC. We build two graphs (Figure 6) for the projected $BS_P$ . They have the respective initial literal layers:

${\cal L}^{1}_{0} = \{$ arm, clog, inP1, $\neg$ inP2$\}$ and

${\cal L}^{2}_{0} = \{$ arm, clog, $\neg$ inP2, inP2$\}$ .

In the graph for the first possible world, $\neg$ arm comes in only through DunkP1 at level 2. In the graph for the second world, $\neg$ arm comes in only through DunkP2 at level 2. Thus, the multiple graphs show which actions in the different worlds contribute to support the same literal.

Figure 6: Multiple planning graphs for CBTC, with relaxed plan components bolded. Mutexes omitted.

A single planning graph is sufficient if we do not aggregate state measures, so in the following we consider how to compute the achievement cost of a belief state with multiple graphs by aggregating state distances.

Positive Interaction Aggregation: Similar to GPT [6], we can use the worst-case world to represent the cost of the belief state $BS_i$ by using the $h^{MG}_{m-RP}$ heuristic. The difference with GPT is that we compute a heuristic on planning graphs, where they compute plans in state space. With this heuristic we account for the number of actions used in a given world, but assume positive interaction across all possible worlds.

The $h^{MG}_{m-RP}$ heuristic is computed by finding a relaxed plan $RP_{\gamma}$ on each planning graph $\gamma \in \Gamma$ , exactly as done on the single graph with $h^{SG}_{RP}$ . The difference is that unlike the single graph relaxed plan $SG^U$ , but like $SG^1$ , the initial levels of the planning graphs are states, so each relaxed plan will reflect all the support needed in the world corresponding to $\gamma$ . Formally:

$$h^{MG}_{m-RP}(BS_i) = \max\limits_{\gamma\in{\Gamma}}\left(\sum\limits_{j = 0}^{b_{\gamma}-1} \mid{{\cal A}^{RP_\gamma}_{j}}\mid \right)$$

where $b_{\gamma}$ is the level of $\gamma$ where a constituent of $BS_G$ was first reachable.

Notice that we are not computing all state distances between states in $BS_P$ and $BS_i$ . Each planning graph $\gamma$ corresponds to a state in $BS_P$ , and from each $\gamma$ we extract a single relaxed plan. We do not need to enumerate all states in $BS_i$ and find a relaxed plan for each. We instead support a set of literals from one constituent of $BS_i$ . This constituent is estimated to be the minimum distance state in $BS_i$ because it is the first constituent reached in $\gamma$ .

For CBTC, computing $h^{MG}_{m-RP}(BS_G)$ (Figure 6) finds:

${RP}_1 =$

${\cal A}^{RP_1}_{0} = \{$ inP1$_p$ , Flush$\}$ ,

${\cal E}^{RP_1}_{0} = \{\varphi^0($ inP1$_p)$ , $\varphi^0($ Flush$)$ },

${\cal L}^{RP_1}_{1} = \{$ inP1$, \neg$ clog$\}$ ,

${\cal A}^{RP_1}_{1} = \{\neg$ clog$_p$ , DunkP1$\}$ ,

${\cal E}^{RP_1}_{1} = \{\varphi^0(\neg$ clog$_p)$ , $\varphi^1($ DunkP1$)$ },

${\cal L}^{RP_1}_{2} = \{\neg$ arm$, \neg$ clog$\}$

and ${RP}_2 =$

${\cal A}^{RP_2}_{0} = \{$ inP2$_p$ , Flush$\}$ ,

${\cal E}^{RP_2}_{0} = \{\varphi^0($ inP2$_p)$ , $\varphi^0($ Flush$)$ },

${\cal L}^{RP_2}_{1} = \{$ inP2$, \neg$ clog$\}$ ,

${\cal A}^{RP_2}_{1} = \{\neg$ clog$_p$ , DunkP2$\}$ ,

${\cal E}^{RP_2}_{1} = \{\varphi^0(\neg$ clog$_p)$ , $\varphi^1($ DunkP2$)$ },

${\cal L}^{RP_2}_{2} = \{\neg$ arm$, \neg$ clog$\}$ .

Each relaxed plan contains two actions and taking the maximum of the two relaxed plan values gives $h^{MG}_{m-RP}(BS_G) = 2$ . This aggregation ignores the fact that we must use different Dunk actions each possible world.

Independence Aggregation: We can use the $h^{MG}_{s-RP}$ heuristic to assume independence among the worlds in our belief state. We extract relaxed plans exactly as described in the previous heuristic and simply use a summation rather than maximization of the relaxed plan costs. Formally:

$$h^{MG}_{s-RP}(BS_i) = \sum\limits_{\gamma\in{\Gamma}}\left(\sum\limits_{j = 0}^{b_{\gamma}-1} \mid{{\cal A}^{RP_\gamma}_{j}}\mid \right)$$

where $b_{\gamma}$ is the level of $\gamma$ where a constituent of $BS_G$ was first reachable.

For CBTC, if computing $h^{MG}_{s-RP}(BS_G)$ , we find the same relaxed plans as in the $h^{MG}_{m-RP}(BS_G)$ heuristic, but sum their values to get 2 + 2 = 4 as our heuristic. This aggregation ignores the fact that we can use the same Flush action for both possible worlds.

State Overlap Aggregation: We notice that in the two previous heuristics we are either taking a maximization and not accounting for some actions, or taking a summation and possibly accounting for extra actions. We present the $h^{MG}_{RPU}$ heuristic to balance the measure between positive interaction and independence of worlds. Examining the relaxed plans computed by the two previous heuristics for the CBTC example, we see that the relaxed plans extracted from each graph have some overlap. Notice, that both ${\cal A}^{RP_1}_{0}$ and ${\cal A}^{RP_2}_{0}$ contain a Flush action irrespective of which package the bomb is in - showing some positive interaction. Also, ${\cal A}^{RP_1}_{1}$ contains DunkP1, and ${\cal A}^{RP_2}_{1}$ contains DunkP2 - showing some independence. If we take the layer-wise union of the two relaxed plans, we would get a unioned relaxed plan:

$RP_{U} =$

${\cal A}^{RP_U}_{0} = \{$ inP1$_p$ , Flush$\}$ ,

${\cal E}^{RP_U}_{0} = \{\varphi^0($ inP1$_p)$ , $\varphi^0($ inP2$_p)$ , $\varphi^0($ Flush$)$ },

${\cal L}^{RP_U}_{1} = \{$ inP1, inP2$, \neg$ clog$\}$ ,

${\cal A}^{RP_U}_{1} = \{\neg$ clog$_p$ , DunkP1, DunkP2$\}$ ,

${\cal E}^{RP_U}_{1} = \{\varphi^0(\neg$ clog$_p)$ , $\varphi^1($ DunkP1$)$ , $\varphi^1($ DunkP2$)$ },

${\cal L}^{RP_U}_{2} = \{\neg$ arm$, \neg$ clog$\}$ .

This relaxed plans accounts for the actions that are the same between possible worlds and the actions that differ. Notice that Flush appears only once in layer zero and the Dunk actions both appear in layer one.

In order to get the union of relaxed plans, we extract relaxed plans from each $\gamma\in{\Gamma}$ , as in the two previous heuristics. Then if we are computing heuristics for regression search, we start at the last level (and repeat for each level) by taking the union of the sets of actions for each relaxed plan at each level into another relaxed plan. The relaxed plans are end-aligned, hence the unioning of levels proceeds from the last layer of each relaxed plan to create the last layer of the $RP_{U}$ relaxed plan, then the second to last layer for each relaxed plan is unioned and so on. In progression search, the relaxed plans are start-aligned to reflect that they all start at the same time, whereas in regression we assume they all end at the same time. The summation of the number of actions of each action level in the unioned relaxed plan is used as the heuristic value. Formally:

$$h^{MG}_{RPU}(BS_i) = \sum\limits_{j = 0}^{b-1} \mid{{\cal A}^{RP_U}_{j}}\mid$$

where $b$ is the greatest level $b_{\gamma}$ where a constituent of $BS_G$ was first reachable.

For CBTC, we just found $RP_U$ , so counting the number of actions gives us a heuristic value of $h^{MG}_{RPU}(BS_G) = 3$ .