Task decomposition on abstract states, for planning under nondeterminism

TitleTask decomposition on abstract states, for planning under nondeterminism
Publication TypeJournal Articles
Year of Publication2009
AuthorsKuter U, Nau DS, Pistore M, Traverso P
JournalArtificial Intelligence
Pagination669 - 695
Date Published2009/04//
ISBN Number0004-3702
KeywordsBinary decision diagrams, Hierarchical task-network (HTN) planning, Planning in nondeterministic domains

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.