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.