特征谓词知识树分解策略的研究

搜索空间约减是智能规划研究中的重要内容之一.谓词知识树是一种特殊的树状结构,它表达了规划领域中实现同一谓词的所有动作.在规划求解过程中,这些动作的前提条件通常是不能同时得到满足的.因此,提出了知识树的分解原理以及基于特征前提的知识树分解策略,并给出了相应的分解算法.对任意一个规划领域,利用该分解算法可将知识树分解成若干个较小规模的知识子树,使其对具体规划状态具有更强的针对性.在规划求解过程中使用知识子树可以避免一些不必要的动作搜索,提高规划效率.实验结果表明分解算法是有效的.

Research on Decomposition Strategy for Knowledge Tree of Characteristic Predicate

Search space reduction is an essential issue in the AI planning. The knowledge tree of predicate is a special tree structure, which shows all actions to achieve the same predicate in a planning domain. The planning tree of predicate is constructed by the knowledge trees of predicates recursively, which can reflect the degree of difficulty to achieve a predicate for a planning domain at the current planning state. The size of the knowledge tree will affect the efficiency of the planning tree generation directly, thus it will further affect the planning efficiency. However, not all preconditions of these actions in the knowledge tree can be satisfied at the same time in planning process usually. Therefore, this paper proposes a principle of knowledge tree decomposition as well as a strategy of decomposing knowledge tree based on the characteristics preconditions, and gives the corresponding decomposition algorithm. For any domain, using the algorithm, knowledge tree of predicate can be decomposed into a number of smaller knowledge sub trees which are more targeted to the specific state. The use of knowledge sub trees in planning process can avoid some unnecessary searching of actions and improve the planning efficiency. Finally, the experiment results show that decomposition algorithm is efficient.