Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.artint.2008.11.012 | Artif. Intell. |
Keywords | Field | DocType |
new planning algorithm,binary decision diagram,observable nondeterministic domain,experimental comparison,correctness theorem,htn-based mechanism,planning problem,task decomposition,large planning problem,abstract state,previously-best algorithm,nondeterministic domain,state transition,hierarchical task network | Hierarchical control system,Observable,Planning algorithms,Nondeterministic algorithm,Correctness,Binary decision diagram,Algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
173 | 5-6 | 0004-3702 |
Citations | PageRank | References |
18 | 0.77 | 40 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ugur Kuter | 1 | 1264 | 74.54 |
Dana S Nau | 2 | 4290 | 531.46 |
Marco Pistore | 3 | 3021 | 181.74 |
Paolo Traverso | 4 | 3483 | 223.80 |