
## 4.1 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, h0 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 (Bonet & Geffner, 2000) 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 (Bertoli et al., 2001b), KACMBP planner (Bertoli
& Cimatti, 2002), YKA planner (Rintanen, 2003b), 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, hcard(BSG**) = 4** because BSG has four states consistent with its complete representation:
ξ(BSG) = (¬inP1 ∧¬inP2∧¬clog ∧¬arm) ∨ (¬inP1 ∧ inP2 ∧¬clog ∧¬arm) ∨
(inP1 ∧¬inP2 ∧¬clog ∧¬arm) ∨ (inP1 ∧ inP2 ∧¬clog ∧¬arm).

Notice, this may be uninformed for BSG because two of the states in ξ(BSG) are not reachable, like: (inP1 ∧ inP2 ∧¬clog ∧¬arm). If there are n packages, then there would be 2 n−1 unreachable states represented by ξ(BSG). 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: Rintanen (2004) 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