智能规划中的可纳子目标排序  

Admissible Subgoal Ordering for Automated Planning

作　　者：梁瑞仕[1,2] 姜云飞[1] 边芮[1,3] 吴向军[1,4] 

机构地区：[1]中山大学信息科学与技术学院,广东广州510275 [2]电子科技大学中山学院计算机学院,广东中山528402 [3]广东商学院公共管理学院,广东广州510320 [4]中山大学软件学院,广东广州510275

出　　处：《软件学报》2011年第5期914-928,共15页Journal of Software

基　　金：国家自然科学基金(60773201;60970042);电子科技大学中山学院博士科研启动基金(410YKQ03)

摘　　要：提出了一种称为可纳子目标排序(admissible subgoal ordering,简称ASO)的排序关系,给出了可纳排序的形式化定义并讨论其对增量式规划的重要性.随后介绍了原子依赖关系理论和原子依赖图技术,能够在多项式时间内近似求解可纳子目标排序关系.最后给出了一种计算可纳子目标序列的算法.其所有思想已经在规划系统ASOP中实现.通过在国际规划大赛标准测试领域问题上的实验,其结果表明,该方法能够有效地求解大规模的规划问题,并能极大地改善规划性能.This paper proposes an ordering relation named Admissible Subgoal Ordering （ASO）. The definition of ASO is formalized, and its relative importance for incremental planning is discussed. Then, this paper introduces the notion of dependency relations over facts, and develops fact dependency graph technique that can approximate admissible ordering relations in polynomial time. Finally, an algorithm to compute subgoals sequence with admissible orderings is presented. All the ideas presented in the paper are implemented in the planning system ASOP, and the effectiveness of the techniques is demonstrated on the benchmarks of International Planning Competitions （IPC）. The results show that these techniques can efficiently solve large planning problems and lead to a greater improvement in planning performance.

关 键 词：智能规划 子目标排序 可纳排序关系 增量式规划 原子依赖图技术 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]