Chinese Journal of Computers   Full Text
Title	An Improved Method for Calculating Activation Sets of Action Derived Preconditions
Authors	JIANG Zhi-Hua1),2) JIANG Yun-Fei1)
Address	1)(Software Research Institute, School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510275) 2)(Department of Computer Science and Technology, Jinan University, Guangzhou 510632)
Year	2007
Issue	No.12(2061—2073)
Abstract &   Background	Abstract The ability to deal with derived preconditions and the chain-reacting in deletion effects of actions in a derived planning domain is both practically and theoretically important. The method based on activation sets is a simple and effective way to deal with derived preconditions of actions; however, the calculation of activation sets is often time-consuming. This paper proposes a new way to calculate activation sets efficiently. Unlike the activation sets introduced first by LPG-td planner, which are closely related to the current state, activation sets that the authors define are state-independent, which means they are stable and have nothing to do with the state. In order to reduce the total time of searching activation sets, the rule set can be grounded out automatically by the technology of rule-splitting. As a result, it is possible that the complexity of calculating is reduced to linear from exponential. The proposed techniques are implemented in a new planner, called LPGSIAS, and some experiments on benchmark problems show that it is more efficient than LPG-td planner in most cases. To sum up, the authors′ work is to present the concept of state-independent activation sets of a derived fact and an efficient method to search activation sets so that a derived planning problem may be quickly solved. keywords AI planning; derived planning domains; activation sets; ground out background The research work here belongs to Automated Planning, a branch of the field of Artificial Intelligence. The issue in this paper, derived planning problems, is a special type of planning problems. And unlike the general planning problems, the techniques of searching and reasoning are closely combined in solving derived planning problems. There are two primary methods for solving derived planning problems: Compiling away and activation sets based. The planning problems after compiling away can be solved by some classical planning systems; however, the plan time is increased sharply with the complexity of action models. The activation sets method was introduced first in 2003 by Gerevini et al. and implemented in a planner, called LPG-td, which joined in the International Planning Competition 2004 and outperformed other planners in the track of derived planning domains. A domain description doesn′t change in the activation sets method, and activation sets for a derived fact are calculated in the rule graph and applied in the action-rule graph for extracting solution actions. The main problem of this method is that the rule graph that is built based on the set of ground rules is often huge and calculating activation sets in it again and again is very time-consuming. In this paper, we propose an improved method for calculating activation sets efficiently. First, we present a new concept of activations sets which are state-independent, and describe the relationship between our concept and the one introduced by Gerevini et al. which is state-dependent. Then, one of the main contributions of this paper is that the rule set can be grounded out automatically by the technology of rule-splitting at plan-time, so that activation sets for some derived facts can be deduced instead of being calculated from the rule graph. The procedure of grounding out is based on the equivalence transformation of the rule set, that is to say, the original planning problem doesn′t change by any means. Besides, our method is implemented in a new planner, called LPGSIAS, and some experiments on benchmark problems show that it is more efficient than LPG-td planner in most cases. Our research work is supported by the National Natural Science Foundation (60173039), and the project is aimed at all sorts of hotspot issues and solving techniques in Automated Planning. The research team has gained a fruitful achievement in some research lines, such as non-deterministic planning, temporal planning, planning and learning, and so on. One of main trends of this field is to integrate multiple techniques together, such as searching and reasoning, and derived planning problems are an example of this trend. This paper and our earlier work (the literate ［11］) have developed some creative and significant methods. The difference between these work is, that the literate ［11］ has presented an efficient algorithm for calculating activation sets that are state-independent in a rule graph but all the calculations are done in a preprocessing phase. However, this paper proposes a mechanism that the rule set can be grounded out automatically by the technology of rule-splitting at plan-time, so that all of activation sets are calculated at plan-time if needed, and furthermore activation sets for some derived facts can be deduced during the procedure of grounding out, instead of being calculated from the rule graph. Therefore, the method in this paper is more flexible and efficient than previous work.