The Research On Goal-Directed Temporal Graphplan Algorithm

Nowadays, intelligent planning is a very hot branch in AI because of its wide application in high-technology fields such as autonomous robots, spacecraft, natural language understanding, knowledge inference, human-machine interaction, data mining etc. Some problems in theory and in practice are international puzzles, but a lot of famous scholars home and abroad still devote themselves to the research. Specially, professor A.L.Blum and professor M.L.Furst provided the Graphplan algorithm, which caused revolutionary progress in the intelligent planning. Recently, the researching of intelligent planning develops at very fast speed. The third ICAPS convened in 2002, temporal and numerical planning problems are mainly considered in the conference. Temporal planning problems are difficult in planning domains, but they approach the real world problems, so more and more researchers give attention to them. Some planners for temporal planning problems are developed, which are based on Graphplan, such as TGP, TPSY and LPGP.The temporal planning algorithms based on Graphplan have some advantages, and they also have some restriction. For example, the searching algorithms begin at the initial state, and search all propositions which are likely to be true. In these situations, if there are irrelevant propositions to goals in initial state or the planning graph is oversize because of the overabundance actions for initial state, the performance of the algorithm will descend rapidly. To solve this problem, we propose a new algorithm for temporal planning problems.This paper makes research on a kind of complex planning problems------temporal planning problems. The following original researches are carried out:The paper systematically reviews the history of intelligent planning, thoroughly states research in the Graphplan framework, objectively shows the current state and suggests areas for future research.The paper applies a novel intelligent planning algorithm. In contrast to the existing methods, the algorithm expands the temporal planning graph backwards from the goal set and searches a valid plan forwards, perfects the approach of backward flexible mutex inference, The method makes the solution plan more quickly for the search, and handles the planning problems much closer to the real world. Therefore, the method has its advantage over previous ones in application.Because of the dependency of intelligent planning, our research has wide application outlook on robotology, intelligent user interface design, natural language understanding, multi-agent systems etc.