GP——基于规划图的遗传规划算法

GP:Genetic Planning Algorithm Based on Planning Graph

图规划是智能规划领域近年来出现的一种新的规划方法,对智能规划的发展有着重要的影响.图规划的规划产生过程分为两个主要步骤,首先用动作的前提条件和效果产生一个谓词和动作交错出现的图———规划图,然后在规划图中抽取规划解.而第二步往往更为困难和耗时.文章依据遗传算法对规划图提出一种新的解抽取方法,以一种简明、直观的形式给出染色体的编码方式,并在此基础上定义了各种遗传操作算子,将遗传算法引入图规划算法,充分利用遗传算法的并行全局搜索能力实现规划解的搜索.实验表明,在求解大规模的规划问题时,文中的遗传规划算法在求解速度和找到的规划解的质量两方面均显示出优越性.

In recent years, a new planning algorithm, graphplan, 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 levels containing proposition nodes and action levels containing action nodes. Secondly, a valid plan is extracted from the planning graph. However the searching of the planning graph is very difficult and cost. In this paper, a way of coding chromosome based on the planning graph is given, and the genetic operators are defined. Accordingly the genetic algorithm is introduced to search for the planning. The experiment shows that the genetic planning is advantage in solving the large planning problem because the genetic algorithm is parallel and global in searching.