need to extend their syntactic form. Our objective is to have a label represent which sources of uncertainty (arising from the source belief state or effects) causally support the labelled item. We also introduce a graph layer Ok to represent outcomes and how they connect effects and literals.

It might seem natural to describe the labels for outcomes in terms of their affected literals, but this can lead to trouble. The problem is that the literals in effect outcomes are describing states at a different time than the literals in the projected belief state. Further, an outcome that appears in two levels of the graph is describing a random event at different times. Using state literals to describe all labels will lead to confusion as to which random events (state uncertainty and effect outcomes at distinct steps) causally support a labelled item. A pathological example is when we have an effect whose set of outcomes matches one-to-one with the states in the source belief state. In such a case, by using labels defined in terms of state literals we cannot distinguish which random event (the state uncertainty or the effect uncertainty) is described by the label.

We have two choices for describing effect outcomes in labels. In both choices we introduce a new set of label variables to describe how a literal layer is split. These new variables will be used to describe effect outcomes in labels and will not be confused with variables describing initial state uncertainty. In the first case, these variables will have a one-to-one matching with our original set of literals, but can be thought of as time-stamped literals. The number of variables we add to the label function is on the order of 2F per level (the number of fluent literals - assuming boolean fluents). The second option is to describe outcomes in labels with a new set of fluents, where each interpretation over the fluents is matched to a particular outcome. In this case, we add on the order of log |Ok| variables, where Ok is the k th outcome layer. It would actually be lower if many of the outcomes were from deterministic effects because there is no need to describe them in labels. The former approach is likely to introduce fewer variables when there are a lot of non-deterministic effects and they affect quite a few of the same literals. The latter will introduce fewer variables when there are relatively few non-deterministic effects whose outcomes are fairly independent.

With the generalized labelling, we can still say that an item is reachable from the source belief state when its label is entailed by the source belief state. This is because even though we are adding variables to labels, we are implicitly adding the fluents to the source belief state. For example, say we add a fluent v to describe two outcomes of an effect. One outcome is labelled v, the other ¬v.

We can express the source belief state BSP that is projected by the LUG with the new fluent as BSP ∧ (v ∨ ¬v) = BSP . An item labelled as BSP ∧ v will not be entailed by the projected belief state (i.e. is unreachable) because only one outcome causally supports it. If both outcomes support the item, then it will be reachable.

Given our notion of reachability, we can determine the level from which to extract a relaxed plan. The relaxed plan procedure does not change much in terms of its semantics other than having the extra graph layer for outcomes. We still have to ensure that literals are causally supported in all worlds they are labelled with in a relaxed plan, whether or not the worlds are from the initial state uncertainty or supporting non-deterministic effects.

## 9. Conclusion

With the intent of establishing a basis for belief state distance estimates, we have:
- Discussed how heuristic measures can aggregate state distance measures to capture positive interaction, negative interaction, independence, and overlap.