
| Problem       | Initial   | Goal    | Fluents   | Causative   | Observational   | Optimal   | Optimal    |
|---------------|-----------|---------|-----------|-------------|-----------------|-----------|------------|
| States        | Literals  | Actions | Actions   | Parallel    | Serial          |           |            |
| Rovers1       | 1         | 1       | 66        | 88          | 0 {12}          | 5 {5}     | 5 {5}      |
| Rovers2       | 2         | 1       | 66        | 88          | 0 {12}          | 8 {7}     | 8 {7}      |
| Rovers3       | 3         | 1       | 66        | 88          | 0 {12}          | 10 {?}    | 10 {8}     |
| Rovers4       | 4         | 1       | 66        | 88          | 0 {12}          | 13 {?}    | 13 {10}    |
| Rovers5       | 16        | 3       | 71        | 97          | 0 {12}          | ? {?}     | 20 {?}     |
| Rovers6       | 12        | 3       | 119       | 217         | 0 {18}          | ? {?}     | ? {?}      |
| Logistics1    | 2         | 1       | 29        | 70          | 0 {10}          | 6 {6}     | 9 {7}      |
| Logistics2    | 4         | 2       | 36        | 106         | 0 {20}          | 6 {?}     | 15 {12}    |
| Logistics3    | 2         | 1       | 58        | 282         | 0 {21}          | 8 {?}     | 11 {8}     |
| Logistics4    | 4         | 2       | 68        | 396         | 0 {42}          | 8 {?}     | 18 {?}     |
| Logistics5    | 8         | 3       | 78        | 510         | 0 {63}          | ? {?}     | 28 {?}     |
| BT(n)         | n         | 1       | n+1       | n           | 0 {n}           | 1 {1}     | n {n-1}    |
| BTC(n)        | n         | 1       | n+2       | n+1         | 0 {n}           | 2n-1 {2}  | 2n-1 {n-1} |
| CubeCenter(n) | n 3       | 3       | 3n        | 6           | 0               | (3n-3)/2  | (9n-3)/2   |
| Ring(n)       | n3 n      | n       | 4n        | 4           | 0               | 3n-1      | 3n-1       |

Table 2: Features of test domains and problems - Number of initial states, Number of goal literals, Number of fluents, Number of causative actions, Number of Observational Actions, Optimal number of parallel plan steps, Optimal number of serial plan steps. Data for conditional versions of domains is in braces; plan lengths for conditional plans are maximum conditional branch length.

search, and CUDD (Brace et al., 1990) to represent belief states and actions. Even with deterministic actions it is possible to obtain cycles from actions with observations because we are planning in belief space. **P OND** constructs the search graph as a directed acyclic graph by employing a cyclechecking algorithm. If adding a hyper-edge to the search graph creates a cycle, then the hyper-edge cannot represent an action in a strong plan and is hence not added to the graph.

## 5.2 Domains

Table 2 shows some of the relative features of the different problems we used to evaluate our approach. The table shows the number of initial states, goal literals, fluents, actions, and optimal plan lengths. This can be used as a guide to gauge the difficulty of the problems, as well as our performance. Conformant Problems In addition to the standard domains used in conformant planning–such as Bomb-in-the-Toilet, Ring, and Cube Center, we also developed two new domains Logistics and Rovers. We chose these new domains because they have more difficult subgoals, and have many plans of varying length.

The Ring domain involves a ring of n rooms where each room is connected to two adjacent rooms. Each room has a window which can be open, closed, or locked. The goal is to have every window locked. Initially, any state is possible - we could be in any room and each window could be in any configuration. There are four actions: move right, move left, close the window in the current