Combining the Expressivity of UCPOP with the Efficiency of Graphplan
Combining the Expressivity of UCPOP with the Efficiency of Graphplan
复制标题
DOI：
10.1007/3-540-63912-8_88
复制
发表时间：
1997-09
期刊：
影响因子：
--
通讯作者：
B. Gazen;Craig A. Knoblock
中科院分区：
文献类型：
--
作者：
B. Gazen;Craig A. Knoblock
最近有大量的工作在新的方法来有效地生成计划的系统，如图形计划和SAT计划。然而，这些系统只提供了一个贫穷的表示语言相比，其他规划师，如UCPOP，ADL，或Prodigy。这使得使用这些新的规划器来表示规划问题变得困难。本文解决了这个问题，提供了一个完全自动化的一套转换UCPOP域表示到Graphplan表示。这组转换扩展了Graphplan表示语言，包括析取、否定、全称量化、条件效应和公理。我们在UCPOP 4.0发行版附带的18个测试域和41个问题上测试了生成的规划器。具有新预处理器的Graphplan能够解决测试集中的每个问题和困难问题（即，那些需要超过一秒的CPU时间），它可以解决他们明显快于UCPOP。虽然UCPOP无法在100，000个节点的搜索限制内解决7个测试问题（需要414到980 CPU秒），但带有预处理器的Graphplan在15 CPU秒内解决了所有问题（包括预处理时间）。
There has been a great deal of recent work on new approaches to efficiently generating plans in systems such as Graphplan and SATplan. However, these systems only provide an impoverished representation language compared to other planners, such as UCPOP, ADL, or Prodigy. This makes it difficult to represent planning problems using these new planners. This paper addresses this problem by providing a completely automated set of transformations for converting a UCPOP domain representation into a Graphplan representation. The set of transformations extends the Graphplan representation language to include disjunctions, negations, universal quantification, conditional effects, and axioms. We tested the resulting planner on the 18 test domains and 41 problems that come with the UCPOP 4.0 distribution. Graphplan with the new preprocessor is able to solve every problem in the test set and on the hard problems (i.e., those that require more than one second of CPU time) it can solve them significantly faster than UCPOP. While UCPOP was unable to solve 7 of the test problems within a search limit of 100,000 nodes (which requires 414 to 980 CPU seconds), Graphplan with the preprocessor solved them all in under 15 CPU seconds (including the preprocessing time).