作　　者： ; ; ; ;

机构地区： 电子科技大学中山学院

出　　处： 《计算机学报》 2012年第8期1620-1633,共14页

摘　　要： 前向启发式搜索和放宽规划方法被很多领域无关的规划器所采用,被认为是一种有效的规划范型.FF规划器利用放宽规划图计算状态的启发式估值,并提取有利动作集合进行前向搜索的剪枝.但过大的有利动作集合造成了过多的消耗.文中提出了一种新的高质量的领域无关剪枝策略.该策略根据放宽规划图的动作层和命题层之间的关系,提取出所谓的直接效用动作集合,此集合之外的其它动作都被剪枝.直接效用动作集合比FF的有利动作集合更加精简,更具启发性,能指导前向搜索集中在那些离目标更近的状态.根据直接效用动作作者开发了一种新的lookahead搜索邻居,并应用在改进后的增强型爬山搜索算法中,使得前向搜索具备良好的前瞻性.当增强型爬山法失败时,采取一种从局部极小值重启完备搜索的策略以保持系统完备性.通过对国际规划大赛基准问题的测试表明,基于该剪枝策略及前向搜索算法实现的前向规划系统有效地缩小了搜索空间,搜索的节点数目比FF的有利动作策略明显要少,搜索效率有显著的提升. Forward-chaining heuristic search combining with relaxed planning approach is considered as an effective planning paradigm and widely adopted in many domain-independent planners, such as FF. Relaxed Planning Graph is used in FF planning system to compute heuristic estimate and extract helpful actions for further pruning the forward search space. This paper presents a new and high-quality domain-independent pruning strategy for forward-chaining planning. The strategy extracts directly-used actions from relaxed planning graph based on the relations between action layers and proposition layers. Then other actions out of the set of directly-used actions are pruned. The set of directly-used actions is more reduced and more informative than the set of helpful actions, and thus the search can focus on those promising states closer to goal. We also develop an extended lookahead search neighborhood based on directly-used actions and incorpo- rate it into the modified EHC algorithm which is used in FF. This makes forward search more foresighted. Moreover, when EHC fails, a new search restarting strategy from local minimal is applied in order to preserve completeness and improve search effort. Experiments in the STRIPS benchmark domains of IPC show that our pruning strategy along with the algorithms decreases the search space effectively, with less search nodes and clear better performance than the helpfulaction pruning strategy used in the state-of-the-art planner FF.

关 键 词： 前向规划 启发式搜索 领域无关剪枝策略 前向搜索邻居 完备搜索

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