We group many heuristics and planners into the group because they are not using , , or 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,
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
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, because has four states consistent with its complete representation:
(
inP1
inP2
clog
arm)
(
inP1
inP2
clog
arm)
(inP1
inP2
clog
arm)
(inP1
inP2
clog
arm).
Notice, this may be uninformed for because two of the states in are not reachable, like: (inP1 inP2 clog arm). If there are packages, then there would be unreachable states represented by . 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.