

![0_image_0.png](0_image_0.png)

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 (Hoffmann & Brafman, 2004) 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.

## 4.2 Single Graph Heuristics (Sg)

The simplest approach for using planning graphs for belief space planning heuristics is to use a "classical" planning graph. To form the initial literal layer from the projected belief state, we could either sample a single state (denoted SG1) or use an aggregate state (denoted SGU ). For example, in CBTC (see Figure 5) assuming regression search with BSP = BSI , the initial level L0 of the planning graph for SG1 might be: