Task decomposition on abstract states, for planning under nondeterminism
Task decomposition on abstract states, for planning under nondeterminism
复制标题
DOI：
10.1016/j.artint.2008.11.012
复制
发表时间：
2009-04
期刊：
影响因子：
--
通讯作者：
U. Kuter;Dana S. Nau;M. Pistore;P. Traverso
中科院分区：
文献类型：
--
作者：
U. Kuter;Dana S. Nau;M. Pistore;P. Traverso
尽管已经开发了几种用于非确定性领域规划的方法，但解决大型规划问题仍然相当困难。在这项工作中，我们提出了一种新的规划算法，称为 Yoyo，用于解决完全可观察的非确定性域中的规划问题。 Yoyo 结合了基于 HTN 的机制来约束其搜索，并结合了二元决策图 (BDD) 表示来推理状态集和状态转换。我们提供了 Yoyo 的正确性定理，并对其与 MBP 和 ND-SHOP2（这两种先前在非确定性领域中进行规划的最佳算法）进行了实验比较。在我们的实验中，Yoyo 可以轻松处理 MBP 和 ND-SHOP2 无法扩展的问题规模，并且解决问题的速度比 MBP 和 ND-SHOP2 快约 100 到 1000 倍。
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.