GP-Genetic Planning Algorithm based on Planning Graph

A.-X. Chen, L.-H. Wu, Y.-F. Jiang, and X.-N. Zhang (PRC)


intelligent planning, planning graph, genetic algorithm.


In recent years, a new planning algorithm, graph plan, is presented and has a great impact on the development of intelligent planning. In graph planning, the algorithm has two main phases: Firstly, a directed, leveled graph with two kinds of nodes and three kinds of edges is constructed according to the preconditions and effects of actions, the levels of planning graph alternate between proposition lev els containing proposition nodes and action levels contain ing action nodes. Secondly, a valid plan is extracted from the planning graph. However the searching of the planning graph is very difficult and costly. In this paper, a way of coding chromosome based on the planning graph is given, and the genetic operators are defined. Accordingly the ge netic planer, which uses the genetic algorithm to search for the planning solution, is developed. The experiment shows that the genetic planer is better than other planers in solving the large planning problem.

Important Links:

Go Back