%0 Journal Article %J Artificial Intelligence %D 2009 %T Task decomposition on abstract states, for planning under nondeterminism %A Kuter,Ugur %A Nau, Dana S. %A Pistore,Marco %A Traverso,Paolo %K Binary decision diagrams %K Hierarchical task-network (HTN) planning %K Planning in nondeterministic domains %X Although several approaches have been developed for planning in nondeterministic domains, solving large planning problems is still quite difficult. In this work, we present a new planning algorithm, called Yoyo, for solving planning problems in fully observable nondeterministic domains. Yoyo combines an HTN-based mechanism for constraining its search and a Binary Decision Diagram (BDD) representation for reasoning about sets of states and state transitions.We provide correctness theorems for Yoyo, and an experimental comparison of it with MBP and ND-SHOP2, the two previously-best algorithms for planning in nondeterministic domains. In our experiments, Yoyo could easily deal with problem sizes that neither MBP nor ND-SHOP2 could scale up to, and could solve problems about 100 to 1000 times faster than MBP and ND-SHOP2. %B Artificial Intelligence %V 173 %P 669 - 695 %8 2009/04// %@ 0004-3702 %G eng %U http://www.sciencedirect.com/science/article/pii/S0004370208001987 %N 5–6 %R 10.1016/j.artint.2008.11.012