LUG simultaneously, the MG approach requires, not backtracking, but reproduction of planning graphs for other possible worlds.

Finally, C**AltAlt** and **P OND** are also related to, and an adaptation of the work on reachability heuristics for classical planning, including **AltAlt** (Nguyen et al., 2002), FF (Hoffmann & Nebel, 2001) and HSP-r (Bonet & Geffner, 1999). C**AltAlt** is the conformant extension to **AltAlt** that uses regression search (similar to HSP-r) guided by planning graph heuristics. **P OND** is similar to FF
in that it uses progression search with planning graph heuristics.

## 8.2 Extension To Non-Deterministic Actions

While the scope of our presentation and evaluation is restricted to planning with initial state uncertainty and deterministic actions, some of the planning graph techniques can be extended to include non-deterministic actions of the type described by Rintanen (2003a). Non-deterministic actions have effects that are described in terms of a set of outcomes. For simplicity, we consider Rintanen's conditionality normal form, where actions have a set of conditional effects (as before) and each consequent is a mutually-exclusive set of conjunctions (outcomes) - one outcome of the effect will result randomly. We outline the generalization of our single, multiple, and labelled planning graphs to reason with non-deterministic actions.

Single Planning Graphs: Single planning graphs, that are built from approximate belief states or a sampled state, do not lend themselves to a straight-forward extension. A single graph ignores uncertainty in a belief state by unioning its literals or sampling a state to form the initial planning graph layer. Continuing with the single graph assumptions about uncertainty, it makes sense to treat non-deterministic actions as deterministic. Similar to how we approximate a belief state as a set of literals to form the initial literal layer or sample a state, we can assume that a non-deterministic effect adds all literals appearing in the effect or samples an outcome as if the action were deterministic
(i.e. gives a set of literals). Single graph relaxed plan heuristics thus remain unchanged.

Multiple Planning Graphs: Multiple planning graphs are very much like Conformant GraphPlan
(Smith & Weld, 1998). We can generalize splitting the non-determinism in the current belief state into multiple initial literal layers to splitting the outcomes of non-deterministic effects into multiple literal layers. The idea is to root a set of new planning graphs at each level, where each has an initial literal layer containing literals supported by an interpretation of the previous effect layer. By interpretations of the effect layer we mean every possible set of joint effect outcomes. A set of effect outcomes is possible if no two outcomes are outcomes of the same effect. Relaxed plan extraction still involves finding a relaxed plan in each planning graph. However, since each planning graph is split many times (in a tree-like structure) a relaxed plan is extracted from each "path of the tree".

We note that this technique is not likely to scale because of the exponential growth in redundant planning graph structure over time. Further, in our experiments CGP has enough trouble with initial state uncertainty. We expect that we should be able to do much better with the LUG.

Labelled Uncertainty Graph: With multiple planning graphs we are forced to capture non–
determinism through splitting the planning graphs not only in the initial literal layer, but also each literal layer that follows at least one non-deterministic effect. We saw in the LUG that labels can capture the non-determinism that drove us to split the initial literal layer in multiple graphs. As such, these labels took on a syntactic form that describes subsets of the states in our source belief state. In order to generalize labels to capture non-determinism resulting from uncertain effects, we