面向结构的基于学习的规划方法  

Structure-Oriented Learning-Based Planning Method

作　　者：陈蔼祥[1] 姜云飞[2] 柴啸龙[1] 边芮[3] 陈清亮[4] 

机构地区：[1]广东财经大学数学与统计学院,广东广州510320 [2]中山大学软件研究所,广东广州510275 [3]广东财经大学公共管理学院,广东广州510320 [4]暨南大学计算机系,广东广州510632

出　　处：《软件学报》2014年第8期1743-1760,共18页Journal of Software

基　　金：国家重点基础研究发展计划(973)(2005CB321902;2010CB328103);国家自然科学基金(60773201;61003056);广东省自然科学基金(10451032001006140);广州市科技和信息化局应用基础研究计划(2010Y1-C641);广东省教育厅高校优秀青年创新人才培育项目(LYM10081;LYM_0065);中央高校基本科研业务费专项资金(21612414);广东省教育厅科技创新项目(2013kjcx0086);广东财经大学自然科学研究项目(11BS52001)

摘　　要：近年来,规划中的学习问题重新受到了关注.如何通过学习机制改善现有规划器,使其能够可靠而令人信服地超越现有非学习的规划器的能力,仍然是一个尚未解决的难题.提出了面向规划问题和解的结构的基于学习的规划技术.该方法将先验知识表示成"子问题-规划片段"的形式.每次规划器成功找到解以后,根据问题的初始状态和目标状态,构造规划对象的初始子状态和目标子状态,构成子问题,并从规划解中抽取该子问题对应的规划片段.这些先验知识将被唯一记录并保存成先验知识库.新问题的求解首先从先验知识库中检索与当前求解问题相关的先验知识;然后,将这些先验知识经过例化、合并步骤后编码成句子;最后,将这些句子连同问题编码得到的句子作为SAT求解器的输入,实现最终解的确定.实验使用了IPC中的基准测试例子进行测试.实验结果表明,SOLP算法求解速度与传统非学习的规划器相比具有明显优势,最佳情况下可达约80%的效率提升.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.

关 键 词：问题结构 解结构 规划片段 结构知识学习 

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