###
Journal of Software:2014.25(8):1743-1760

面向结构的基于学习的规划方法
陈蔼祥,姜云飞,柴啸龙,边芮,陈清亮
(广东财经大学 数学与统计学院, 广东 广州 510320;中山大学 软件研究所, 广东 广州 510275;广东财经大学 公共管理学院, 广东 广州 510320;暨南大学 计算机系, 广东 广州 510632)
Structure-Oriented Learning-Based Planning Method
CHEN Ai-Xiang,JIANG Yun-Fei,CHAI Xiao-Long,BIAN Rui,CHEN Qing-Liang
(School of Mathematics and Statistics, Guangdong University of Finance and Economics, Guangzhou 510320, China;Software Research Institute, Sun Yat-Sen University, Guangzhou 510275, China;School of Public management, Guangdong University of Finance and Economics, Guangzhou 510320, China;Department of Computer, Ji'nan University, Guangzhou 510632, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2838   Download 2433
Received:May 27, 2013    Revised:October 11, 2013
> 中文摘要: 近年来,规划中的学习问题重新受到了关注.如何通过学习机制改善现有规划器,使其能够可靠而令人信服地超越现有非学习的规划器的能力,仍然是一个尚未解决的难题.提出了面向规划问题和解的结构的基于学习的规划技术.该方法将先验知识表示成“子问题-规划片段”的形式.每次规划器成功找到解以后,根据问题的初始状态和目标状态,构造规划对象的初始子状态和目标子状态,构成子问题,并从规划解中抽取该子问题对应的规划片段.这些先验知识将被唯一记录并保存成先验知识库.新问题的求解首先从先验知识库中检索与当前求解问题相关的先验知识;然后,将这些先验知识经过例化、合并步骤后编码成句子;最后,将这些句子连同问题编码得到的句子作为SAT 求解器的输入,实现最终解的确定.实验使用了IPC 中的基准测试例子进行测试.实验结果表明,SOLP 算法求解速度与传统非学习的规划器相比具有明显优势,最佳情况下可达约80%的效率提升.
Abstract:The goal of reliably outperforming non-learning planners via learning is still to be achieved. A novel structure-oriented learning-based planning method (SOLP) is presented. SOLP anaylyses the structure knowledge, decomposes the planning problem into initial sub-state and goal sub-state, its solution into plan fragment, when planner finds out a solution successfully. The structure knowledge from previous experiment, or prior knowledge, will be saved in domain. When encountering new problem, SOLP firstly recalls the prior problem structure equivalent or similar to the current problem and the corresponding plan fragment from the domain file, then instantiates the learned prior knowledge as ground knowledge, and finally, encodes the ground knowledge as a satisfiability clause. These clauses, together with the set of clauses from the problem, form the input of the algorithm. SOLP calls the SAT Solver to determine the final solution. An experiment is conducted to test the algorithm in several different domains from IPC to demonstrate the efficiency and effectiveness of the new approach. The results show that, the speed of SOLP has obvious advantage than that of non-learning planner, with up to 80% improvement in extreme case.
文章编号:     中图分类号:    文献标志码:
基金项目:国家重点基础研究发展计划(973)(2005CB321902,2010CB328103);国家自然科学基金(60773201,61003056);广东省自然科学基金(10451032001006140);广州市科技和信息化局应用基础研究计划(2010Y1-C641);广东省教育厅高校优秀青年创新人才培育项目(LYM10081,LYM_0065);中央高校基本科研业务费专项资金(21612414);广东省教育厅科技创新项目(2013kjcx0086);广东财经大学自然科学研究项目(11BS52001) 国家重点基础研究发展计划(973)(2005CB321902,2010CB328103);国家自然科学基金(60773201,61003056);广东省自然科学基金(10451032001006140);广州市科技和信息化局应用基础研究计划(2010Y1-C641);广东省教育厅高校优秀青年创新人才培育项目(LYM10081,LYM_0065);中央高校基本科研业务费专项资金(21612414);广东省教育厅科技创新项目(2013kjcx0086);广东财经大学自然科学研究项目(11BS52001)
Foundation items:
Reference text:

陈蔼祥,姜云飞,柴啸龙,边芮,陈清亮.面向结构的基于学习的规划方法.软件学报,2014,25(8):1743-1760

CHEN Ai-Xiang,JIANG Yun-Fei,CHAI Xiao-Long,BIAN Rui,CHEN Qing-Liang.Structure-Oriented Learning-Based Planning Method.Journal of Software,2014,25(8):1743-1760