The Research And Implementation On Goal-Directed Flexible Graphplan Algorithm

Nowadays, intelligent planning is a very hot branch in AI because of its wideapplication in high-technology fields such as autonomous robots, spacecraft, naturallanguage understanding, knowledge inference, human-machine interaction, data mining etc.Some problems in theory and in practice are international puzzles, but a lot of famousscholars home and abroad still devote themselves to the research. Specially, professorA.L.Blum and professor M.L.Furst provided the Graphplan algorithm, which causedrevolutionary progress in the intelligent planning.Recently, intelligent planning develops rapidly. Besides research on improvement ofefficiency further, a lot of work has been done to extend the range of problems handled byplanning algorithms and to improve the quality of plans. The Graphplan planner hasenjoyed considerable success as a planning algorithm for STRIPS domains planningproblems. However, it is argued that this framework is too rigid to capture the full subtletyof many real problems, which leads to no solution found or low-quality solution. In general,the real-world planning problems are complex. If not preprocessed, most are hard to settle.In addition, because of the variety of the planning problems, it is unrealistic to handle all ofthem in a uniform way. Hence, specialized planning algorithms are tailored to differentplanning problems.This paper makes research on a kind of complex planning problems—— flexibleplanning problems. The following original researches are carried out:The paper systematically reviews the history of intelligent planning, thoroughly statesresearch in the Graphplan framework, objectively shows the current state and suggestsareas for future research.The paper applies a novel intelligent planning algorithm. In contrast to the existingmethods, the algorithm expands the flexible planning graph backwards from the goal setand searches a valid plan forwards, perfects the approach of backward flexible mutexinference, and avoids a complicated process of satisfaction degree propagation. Themethod takes into account user's requirement and taste, strives to improve comprehensivequality of a plan, makes the solution plan more suitable for the needs, and handles theplanning problems much closer to the real world. Therefore, the method has its advantageover previous ones in application.Based on the algorithm, GDFGP(Goal-Directed Flexible Graphplan) planning systemhas been developed. And its availability has been validated by a set of problems from theRescue domain.Because of the dependency of intelligent planning, our research has wide applicationoutlook on robotology, intelligent user interface design, natural language understanding,multi-agent systems etc.