林尔敏，张逢春蔡莉莎（.海南软件职业技术学院，海南琼海，57400；.海口市高级技工学校，海南海口，5700）



图规划在路径规划中的应用

林尔敏1，张逢春2蔡莉莎1
（1.海南软件职业技术学院，海南琼海，571400；2.海口市高级技工学校，海南海口，570102）

摘要：随着科学技术的不断发展，机器人研究成为当今的热门话题，人们趋向于用机器人替代人类去完成一些危险的工作。而路径规划是机器人研究的难点之一。本文以机器人的运输问题为例，介绍了图规划的算法，以及如何利用图规划技术对路径规划问题进行求解。

关键词：图规划；路径规划

the application of graph planning in path plannng

0　引言

随着科技的发展，智能能规划已经成为当今的热门学科，基于规划图的规划算法—图规划（Graphplan）深受规划界的广泛关注，像Blackbox、FF等著名的规划器都采用了图规划的算法。使用图规划可以将问题空间规划化，能够减少重复搜索，缩短时间。利用图规划的技术来解决规划问题，就可以将寻迹问题转变为有规整的状态空间的宽度优先搜索算法，很好的缩短了规划时间。本文将图规划技术应用在机器人的路径规划系统中，以求达到缩短规划时间的目的。

1　图规划算法的研究

图规划的主要思想是利用图的方法来解决规划问题。将规划问题转化成规划图，这个规划图在时间上满足规划存在的条件，即满足同层命题节点，动作节点之间的互斥关系。然后进行规划解的提取，对已经生成的规划图实施一个向后的链式搜索，试图寻得所求的规划解，如果无法找到所需要的解，我们将对前面生成的规划图进行进一步的扩展，再次循环执行图扩展与规划解的提取，直到找到所需要的解或是无解返回。……