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

Structure-Oriented Learning-Based Planning Method

近年来,规划中的学习问题重新受到了关注.如何通过学习机制改善现有规划器,使其能够可靠而令人信服地超越现有非学习的规划器的能力,仍然是一个尚未解决的难题.提出了面向规划问题和解的结构的基于学习的规划技术.该方法将先验知识表示成"子问题-规划片段"的形式.每次规划器成功找到解以后,根据问题的初始状态和目标状态,构造规划对象的初始子状态和目标子状态,构成子问题,并从规划解中抽取该子问题对应的规划片段.这些先验知识将被唯一记录并保存成先验知识库.新问题的求解首先从先验知识库中检索与当前求解问题相关的先验知识;然后,将这些先验知识经过例化、合并步骤后编码成句子;最后,将这些句子连同问题编码得到的句子作为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.