Automatic OBDD-based Generation of Universal Plans in Non-Deterministic Domains

Most real world environments are non-deterministic. Automatic plan formation in non-deterministic domains is, however, still an open problem. In this paper we present a practical algorithm for the automatic generation of solutions to planning problems in non-deterministic domains. Our approach has the following main features. First, the planner generates Universal Plans, and exploits the compactness of OBDD`s (Ordered Binary Decision Diagrams) to express in a practical way plans of extremely large size. Second, the planner generates plans which are guaranteed to achieve the goal in spite of non-determinism, if such plans exist. Otherwise, the planner generates plans which encode iterative trial-and-error strategies (e.g. try to pick up a block until succeed), which are guaranteed to achieve the goal under the assumption that if there is a non-deterministic possibility for the iteration to terminate, this will not be ignored forever. Third, the implementation of the planner is based on symbolic model checking techniques, which allow to explore efficiently very large state spaces. The experimental results are very promising