| 本文已被：浏览 5413次 下载 7540次 |
码上扫一扫！ |
|
|
| 智能规划中的可纳子目标排序 |
|
梁瑞仕1,2, 姜云飞1, 边芮1,3, 吴向军1,4
|
|
1.中山大学 信息科学与技术学院,广东 广州 510275;2.电子科技大学 中山学院 计算机学院,广东 中山 528402;3.广东商学院 公共管理学院,广东 广州 510320;4.中山大学 软件学院,广东 广州 510275
|
|
| 摘要: |
| 提出了一种称为可纳子目标排序(admissible subgoal ordering,简称ASO)的排序关系,给出了可纳排序的形式化定义并讨论其对增量式规划的重要性.随后介绍了原子依赖关系理论和原子依赖图技术,能够在多项式时间内近似求解可纳子目标排序关系.最后给出了一种计算可纳子目标序列的算法.其所有思想已经在规划系统ASOP 中实现.通过在国际规划大赛标准测试领域问题上的实验,其结果表明,该方法能够有效地求解大规模的规划问题,并能极大地改善规划性能. |
| 关键词: 智能规划 子目标排序 可纳排序关系 增量式规划 原子依赖图技术 |
| DOI：10.3724/SP.J.1001.2011.03778 |
| 分类号: |
| 基金项目:国家自然科学基金(60773201, 60970042); 电子科技大学中山学院博士科研启动基金(410YKQ03) |
|
| Admissible Subgoal Ordering for Automated Planning |
|
LIANG Rui-Shi1,2, JIANG Yun-Fei1, BIAN Rui1,3, WU Xiang-Jun1,4
|
|
1.School of Information Science and Technology, Sun Yat-Sen University, Guangzhou 510275, China;2.School of Computer, Zhongshan Institue, University of Electronic Science and Technology of China, Zhongshan 528402, China;3.School of Public Management, Guangdong University of Business Studies, Guangzhou 510320, China;4.School of Software, Sun Yat-Sen University, Guangzhou 510275, China
|
| Abstract: |
| 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. |
| Key words: AI planning subgoal ordering admissible ordering relation incremental planning fact dependency graph technique |
