Planning under uncertainty: moving forward
Dana S. Nau, Ugur Kuter · 2006
This dissertation describes a suite of new planning algorithms for planning under uncertainty with the assumption of full observability. The new algorithms are much more efficient than the previous techniques; in some cases, they find solutions exponentially faster than the previous ones. In particular, our contributions are as follows: (1) A method to take any forward-chaining classical planning algorithm, and systematically generalize it to work for planning in nondeterministic planning domains, where the likelihood of the possible outcomes of the actions are not known. In our experiments, ND-SHOP2, a generalization of the Hierarchical Task Network (HTN) planner SHOP2 [NAI +03], could find solutions in nondeterministic planning domains about two to three orders of magnitude faster than MBP [BCP+01], which uses symbolic model-checking techniques based on Binary Decision Diagrams (BDDs) [Bry92], and which was one of the best previous planners for such domains. (2) A way, called Forward State-Space Splitting (FS3), to take the search control (i.e., pruning) technique of any forward-chaining classical planner, such as TLPlan [BK00], TALplanner [KD01], and SHOP2 [NAI +03], and combine it with BDDs. The result of this combination is a suite of new planning algorithms for nondeterministic planning domains. In our experiments, FS3SHOP2 , one of the new algorithms that combines HTNs as in ND-SHOP2 with BDDs as in MBP, was never dominated by either MBP or ND-SHOP2: FS3SHOP2 could easily deal with problem sizes that neither MBP nor ND-SHOP2 could scale up to, and furthermore, it could solve problems about two or three orders of magnitude faster than the other two. (3) A way to incorporate the pruning technique of a forward-chaining classical planner into the previous algorithms developed for planning with MDPs. The modified algorithms in our experiments were about 10,000 times faster than the original ones on the largest problems the original ones could solve. On another set of problems that were more than 14,000 times larger than the original algorithms could solve, the modified ones took only about 1/3 second. The new planning techniques described here have good potential to be applicable to other research areas as well. In particular, this dissertation describes such potentials in Reinforcement Learning, Hybrid Systems Control, and Planning with Temporal Uncertainty. Finally, the closing remarks include a discussion on the challenges of using search control in planning under uncertainty and some possible ways to address those challenges. (Abstract shortened by UMI.)