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

Mostreal worldenvironmentsare non-deterministic. Automaticplan formation in non-deterministic dommns is, however, still an open problem. In this paper wepresent a practical algorithmfor the automatic generation of solutions to planning problemsin nondeterministic domains. Ourapproachhas the following mainfeatures. First, the planner generates Universal Plans. Second, it generatesplans whichare guaranteed to achievethe goal in spite of non-determinism, if such plans exist. Otherwise, the planner generates plans whichencodeiterative trial-and-error strategies (e. g. try to pick up a blockuntil succeed), whichare guaranteedto achievethe goal underthe assumption that if there is a non-deterministic possibilityfor the iteration to terminate, this will not be ignoredforever. Third, the implementation of the planneris basedon symbolic modelcheckingtechniqueswhichhavebeendesignedto exploreefficiently large state spaces. Theimplementation exploits the compactness of ORDDS (OrderedBinary DecisionDiagrams) to express in a practical way universalplans of extremely large size. *

Authors

• Alessandro Cimatti

Keywords

No keywords are indexed for this paper.