TitlePlan aggregation for strong cyclic planning in nondeterministic domains
Publication TypeJournal Article
Year of Publication2014
AuthorsAlford, R, Kuter, U, Nau, D, Goldman, RP
JournalArtificial Intelligence
Volume216
Pagination206-232
KeywordsAutomated Planning, Nondeterministic Actions, Strong Cyclic Solutions
Abstract

We describe a planning algorithm, NDP2, that finds strong-cyclic solutions to nondeterministic planning problems by using a classical planner to solve a sequence of classical planning problems. NDP2 is provably correct, and fixes several problems with prior work. We also describe two preprocessing algorithms that can provide a restricted version of the symbolic abstraction capabilities of the well-known MBP planner. The preprocessing algorithms accomplish this by rewriting the planning problems, hence do not require any modifications to NDP2 or its classical planner. In our experimental comparisons of NDP2 (using FF as the classical planner) to MBP in six different planning domains, each planner outperformed the other in some domains but not others. Which planner did better depended on three things: the amount of nondeterminism in the planning domain, domain characteristics that affected how well the abstraction techniques worked, and whether the domain contained unsolvable states.

Full Text
pdf: 
https://www.nrl.navy.mil/itd/aic/sites/www.nrl.navy.mil.itd.aic/files/pdfs/Alford2014AIj.pdf
NRL Publication Release Number: 
14-1231-2124