That is, T1 can refer to all variables, T2 can refer to all variables except ~x0
1 T3 can refer to
all variables except ~x0
$$\vec{x_{1}}\qquad\quad\vec{x_{2}}$$
2 and so on.
As shown by Ranjan et al. (1995) the computation time used to calculate the preimage is

a convex function of the number of partitions. The reason for this is that, for some number

of partitions, further subdivision of the partitions will not reduce the total complexity,

fully chosen such that it consists of a conjunction of subexpressions that only refer to a small

subset of next state variables. This representation allows us to sort out the subexpressions

in conjunctive partitions with near optimal sizes that satisfy the above requirements.

The three universal planning algorithms discussed are all based on an iteration of preimage calculations. The iteration corresponds to a parallel backward breadth-rst search starting at the goal states and ending when all initial states are included in the set of visited

states (see Figure 7). The main dierence between the algorithms is the way the preimage

is dened.

universal planning algorithms, computing preimages Pre1, Pre2 and Pre3.

the reduction of the complexity of each obdd operation.

because the complexity introduced by the larger number of obdd operations is higher than The representation of the logical expression for each relation A F and I has been care6. Obdd-based Universal Planning Algorithms We rst describe two prior algorithms for obdd-based universal planning and discuss which kind of domains they are suitable for. We then present new algorithm called optimistic planning that is suitable for some domains not covered by the prior algorithms.

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

Figure 7: An illustration of the parallel backward breadth-rst search used by obdd-based

## 6.1 Strong And Weak Preimages

Cimatti et al. (1998a) introduces two dierent kinds of preimages called strong and weak preimages A strong preimage is dened by:

Denition 3 (Strong Preimage) Given an NFA M = (Q; ;  and a set of states V 
Q, the strong preimage of V is the set of states s j s 2 Q ^ 9i 2 :  s; i  V .

one action i where all the transitions from s associated with i lead into V Consider the

Thus, for a state s belonging to the strong preimage of a set of states V , there exists at least

$$\mathbf{\dot{}}t$$
$\mathbf{U}^{\star}$
$\mathbf{S}$