智能规划中基于路标的启发式搜索方法研究

Planning has been one of the closest topics that relate the theories of Artificial Intelligence to practical applications. As an exploration of the planning problem structure, landmark is widely used in the research field of planning recently. This project will focus on the guidance power of landmarks for heuristic search planning method, improve the heuristic evaluation with the features of landmark and provide kinds of effective heuristic strategies for planning algorithms by extracting implicit information from flexible orders between landmarks. The research contexts mainly include: 1)to make use of propositional landmarks for simplifying the planning problem to propose a heuristic evaluation method based on the constraint of propositional landmarks; 2)to update the layers of relax planning graph and solve the relaxed problem incrementally under guidance of orders between landmarks; 3)to design a landmark-directed lookahead search method, construct lookahead plans for the respective propositional landmarks, which are used to explore the search space more strongly; 4)to apply a landmark-based pruning method in the random-walk procedure, checking the control power of landmarks to the search direction; 5)to describe the semantics of the plans using the orders in which the plan achieves the landmarks and generate diverse plans according to the constraint of landmark orders. The research will promote to explore the heuristic ability of landmark information deeply and develop the practical applications of planning systems, which will provide theoretical foundations for the extension of planning research to sophisticated real world problems.

智能规划是人工智能理论与实际应用结合最为紧密的研究课题之一。路标是对规划问题结构的开发，近年来广泛应用于智能规划领域。本课题将深入研究路标在启发式搜索规划方法中的指导作用，利用路标信息完善启发式评估过程，并重点挖掘灵活多变的路标排序关系所隐含的信息，为搜索算法提供更丰富的启发式策略，主要包括：1)从简化规划问题的角度使用命题路标，进一步约束路标切割启发式评估过程；2)利用路标排序关系改进放松规划图的层次结构，引导放松规划问题的增量求解；3)设计以路标为导向的前瞻搜索方法，针对路标构造前瞻路径，加强对搜索空间的探索力度；4)在随机游走过程中应用路标剪枝方法，检验路标对搜索方向的控制能力；5)利用路标排序关系刻画规划解的执行语义，在路标排序的约束下计算多样化的规划解集。本课题的研究将有助于充分发挥路标信息的启发作用，扩展规划系统的实际应用能力，为其向复杂的现实世界问题拓展奠定理论基础。

智能规划（Planning）一直活跃在人工智能领域的最前沿，随着智能规划的研究逐渐向真实世界问题拓展，问题结构的开发与利用对于规划求解能力的影响也更加明显。路标可以看作是对规划问题结构特征的开发，是近年来智能规划领域的研究热点。路标是每条规划解都必须实现的一系列子目标，这一重要特性为规划求解过程提供了大量有价值的信息。在路标信息的启示下，根据以往规划求解的经验知识不断修正规划方法、设计更有效的启发式搜索策略是一个重要的研究趋势。本课题围绕着路标对搜索过程的指导作用，对基于启发式搜索的规划方法和自动推理方法展开了研究，提出一系列适合于问题结构特征的更灵活的搜索策略，主要包括：1)从简化规划问题的角度使用命题路标，进一步约束启发式评估过程；利用路标排序关系改进放松规划图的层次结构，引导放松规划问题的增量求解；2）在构造随机游走序列的过程中融入路标信息，通过提高路标支持动作的选择概率来实现，使得每一步的动作选择范围更有针对性，一次性获取到一段有效的规划解序列；3）基于随机局部搜索的扩展规则推理方法是扩展规则领域不完备推理框架的一个大胆尝试，填补了不完备推理方面的空白，为自动推理方法在知识编译和智能规划等领域的应用奠定了理论基础；4）在医学图像处理、网格地图等实际问题中应用规划算法进行建模和求解，对规划算法的实际应用能力进行了拓展，也为智能规划及相关领域带来了新的研究问题。本课题的研究进一步挖掘了规划问题中路标的优秀特性，充分发挥了路标信息的启发作用，扩展了规划系统的实际应用能力，为其向复杂的现实世界问题拓展奠定理论基础。