Non Planning Graph-based Heuristics ($NG$ )

We group many heuristics and planners into the $NG$ group because they are not using $SG$ , $MG$ , or $LUG$ planning graphs. Just because we mention them in this group does not mean they are not using planning graphs in some other form.

No Aggregation: Breadth first search uses a simple heuristic, $h_0$ where the heuristic value is set to zero. We mention this heuristic so that we can gauge the effectiveness of our search substrates relative to improvements gained through using heuristics.

Positive Interaction Aggregation: The GPT planner [6] measures belief state distance as the maximum of the minimum state to state distance of states in the source and destination belief states, assuming optimistic reachability as mentioned in Section 3. GPT measures state distances exactly, in terms of the minimum number of transitions in the state space. Taking the maximum state to state distance is akin to assuming positive interaction of states in the current belief state.

Independence Aggregation: The MBP planner [3], KACMBP planner [1], YKA planner [28], and our comparable $h_{card}$ heuristic measure belief state distance by assuming every state to state distance is one, and taking the summation of the state distances (i.e. counting the number of states in a belief state). This measure can be useful in regression because goal belief states are partially specified and contain many states consistent with a goal formula and many of the states consistent with the goal formula are not reachable from the initial belief state. Throughout regression, many of the unreachable states are removed from predecessor belief states because they are inconsistent with the preconditions of a regressed action. Thus, belief states can reduce in size during regression and their cardinality may indicate they are closer to the initial belief state. Cardinality is also useful in progression because as belief states become smaller, the agent has more knowledge and it can be easier to reach a goal state.

In CBTC, $h_{card}(BS_G) = 4$ because $BS_G$ has four states consistent with its complete representation:

$\xi(BS_G) =$ ($\neg$ inP1 $\wedge \neg$ inP2 $\wedge \neg$ clog $\wedge \neg$ arm) $\vee$ ($\neg$ inP1 $\wedge$ inP2 $\wedge \neg$ clog $\wedge \neg$ arm) $\vee$
(inP1 $\wedge \neg$ inP2 $\wedge \neg$ clog $\wedge \neg$ arm) $\vee$ (inP1 $\wedge$ inP2 $\wedge \neg$ clog $\wedge \neg$ arm).

Notice, this may be uninformed for $BS_G$ because two of the states in $\xi(BS_G)$ are not reachable, like: (inP1 $\wedge$ inP2 $\wedge \neg$ clog $\wedge \neg$ arm). If there are $n$ packages, then there would be $2^{n-1}$ unreachable states represented by $\xi(BS_G)$ . Counting unreachable states may overestimate the distance estimate because we do not need to plan for them. In general, in addition to the problem of counting unreachable states, cardinality does not accurately reflect distance measures. For instance, MBP reverts to breadth first search in classical planning problems because state distance may be large or small but it still assigns a value of one.

Overlap Aggregation: [29] describes n-Distances which generalize the belief state distance measure in GPT to consider the maximum n-tuple state distance. The measure involves, for each n-sized tuple of states in a belief state, finding the length of the actual plan to transition the n-tuple to the destination belief state. Then the maximum n-tuple distance is taken as the distance measure.

For example, consider a belief state with four states. With an n equal to two, we would define six belief states, one for each size two subset of the four states. For each of these belief states we find a real plan, then take the maximum cost over these plans to measure the distance for the original four state belief state. When n is one, we are computing the same measure as GPT, and when n is equal to the size of the belief state we are directly solving the planning problem. While it is costly to compute this measure for large values of n, it is very informed as it accounts for overlap and negative interactions.

The CFF planner [17] uses a version of a relaxed planning graph to extract relaxed plans. The relaxed plans measure the cost of supporting a set of goal literals from all states in a belief state. In addition to the traditional notion of a relaxed planning graph that ignores mutexes, CFF also ignores all but one antecedent literal in conditional effects to keep their relaxed plan reasoning tractable. The CFF relaxed plan does capture overlap but ignores some subgoals and all mutexes. The way CFF ensures the goal is supported in the relaxed problem is to encode the relaxed planning graph as a satisfiability problem. If the encoding is satisfiable, the chosen number of action assignments is the distance measure.