Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (1): 22-24.DOI: 10.3778/j.issn.1002-8331.2009.01.006

• 博士论坛 • Previous Articles     Next Articles

Shrink planning graph algorithm based on domain information mining

CHAI Xiao-long   

  1. Department of Mathematics and Computing Science,Guangdong University of Business Studies,Guangzhou 510320,China
  • Received:2008-07-09 Revised:2008-08-18 Online:2009-01-01 Published:2009-01-01
  • Contact: CHAI Xiao-long

领域信息提取的缩规划图算法

柴啸龙   

  1. 广东商学院 数学与计算科学学院,广州 510320
  • 通讯作者: 柴啸龙

Abstract: The traditional technique of graph planning has a bottle-neck of efficiency when the algorithm dealing with the large scale problem.The reason is that almost all intelligence planning problems are NP hard,and the calculating quantity is a blow to the algorithm by degrees.Some improvements of the graph planning techniques are made in this paper as follows.First,the domain information mining is used in the algorithm.Second,the shrink planning graph also with the corresponding algorithm are presented based on the heuristic function from domain information.The algorithm can rank the different expanding branch,and prune some expanding branch with little hope.A related experiment of planning shows that the tactic is work.

Key words: intelligence planning, planning graph, shrink planning graph, heuristic information, domain knowledge

摘要: 传统的图规划技术在处理规模较大的智能规划问题时,由于计算量的递增爆炸,导致算法在规划问题上容易出现效率瓶颈。对图规划技术进行了一些改进:(1)加入领域信息的动态提取和使用;(2)提出了缩规划图的概念和算法,通过引入基于领域信息的启发式函数,对不同的扩展分支进行优选排序,剪除一些执行希望小甚至不合理的扩展分支,从而提高了系统执行效率。实验表明该策略是有效的。

关键词: 智能规划, 规划图, 缩规划图, 启发式信息, 领域信息