timing constraints are met. Finally, Hoey and his colleagues (1999) use algebraic decision diagrams to tackle the problem of stochastic planning.

## 9. Conclusions And Future Work

In this paper we presented a new approach to conformant planning, based on the use of Symbolic Model Checking techniques.  The algorithm is very general, and applies to complex planning domains, with uncertainty in the initial condition and in action effects, which can be described as finite state automata. The algorithm is based on a breadthfirst, backward search, and returns conformant plans of minimal length, if a solution to the planning problem exists.  Otherwise, it terminates with failure.  The algorithm is designed to take full advantage of the symbolic representation based on BDDs. The implementation of the approach in the CMBP system has been highly optimized, in particular in the crucial step of termination checking. We performed an experimental comparison of our approach with the state of the art conformant planners CGP, QBFPLAN and GPT. CMBP is strictly more expressive than Q BFPLAN and C GP .  On all the problems for which a comparison was possible, CMBP outperformed its competitors in terms of run times, sometimes by orders of magnitude. Thanks to the use of symbolic data structures, CMBP is able to deal efficiently with problems with large numbers of initial states and action outcomes. On the other hand, the qualitative behavior of CGP and GPT seems to depend heavily on the enumerative nature of their algorithms. Differently from GPT, CMBP is independent of the effectiveness of the heuristic used to drive the search.

The research presented in this paper will be extended in the following directions. First, we are investigating an alternative approach to conformant planning, where the breadthfirst style of the sear is given up. These teniques appear to be extremely promising —
preliminary experiments have led to speed ups of up to two orders of magnitude over the results presented in this paper for problems which admit a solution. Second, we will tackle the problem of conditional planning under partial observability, under the hypothesis that a limited amount of information can be acquired at run time. As conformant planning, this problem can be seen as search in the belief space. However, it appears to be significantly complicated by the need for dealing with run-time observation and conditional plans. Finally, we are considering the extension of the domain construction of the planner with more expressive input language, such as C, and invariant detection techniques.

## Acknowledgements

Fausto Giunchiglia provided continuous encouragement and feedback on this work.  We thank Piergiorgio Bertoli, Blai Bonet, Marco Daniele, Hector Geffner, Enrico Giunchiglia, Jussi Rintanen, David Smith, Paolo Traverso, Dan Weld for valuable discussions on conformant planning and various comments on this paper. David Smith provided the code of CGP, a large number of examples, and the time-out meanism used in the experimental evaluation. Jussi Rintanen made QBFPLAN available under Linux.