作　　者： ; ;

机构地区： 中山大学信息科学与技术学院软件研究所

出　　处： 《计算机学报》 2007年第12期2061-2073,共13页

摘　　要： 动作的派生前提和动作删除效果的"连锁反应"是处理派生规划问题中的难点问题,基于激活集的方法是一种简单、有效的方法,但是激活集的计算时间往往过多,文中提出一种新的方法来计算激活集.LPG-td规划系统所提出的激活集是与状态有关的并且需要在规则图上反复计算,而文中提出的激活集是与状态无关的,通过规则分裂来对规则集进行"基化",使得寻找激活集的时间逐渐地由指数级降为线性级.实现了一个新的能够处理派生规划问题的规划系统LPGSIAS,通过对基准问题的求解,表明LPGSIAS比LPG-td在大部分情况下更高效.与状态无关的激活集可以方便地转化为与状态有关的激活集,文中通过提出一种求解与状态无关的激活集的改进方法来加快对派生规划问题的求解速度. The ability to deal with derived preconditions and the chain-reacting in deletion effects of actions in a derived planning domain is both practically and theoretically important. The method based on activation sets is a simple and effective way to deal with derived preconditions of actions; however, the calculation of activation sets is often time-consuming. This paper proposes a new way to calculate activation sets efficiently. Unlike the activation sets introduced first by LPG-td planner, which are closely related to the current state, activation sets that the authors define are state-independent, which means they are stable and have nothing to do with the state. In order to reduce the total time of searching activation sets, the rule set can be grounded out automatically by the technology of rule-splitting. As a result, it is possible that the complexity of calculating is reduced to linear from exponential. The proposed techniques are implemented in a new planner, called LPG^SIAS, and some experiments on benchmark problems show that it is more efficient than LPG-td planner in most cases. To sum up, the authors＇ work is to present the concept of state-independent activation sets of a derived fact and an efficient method to search activation sets so that a derived planning problem may be quickly solved.

关 键 词： 智能规划 派生规划问题 激活集 基化

领　　域： [自动化与计算机技术] [自动化与计算机技术]