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

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



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

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

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

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

the application of graph planning in path plannng

0　引言

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

1　图规划算法的研究

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

本文以机器人运输问题为例如图1所示介绍基于图规划路径规划算法。

图1　机器人运输问题

任务描述：利用机器人将两个包裹从M地运往N地。初始状态机器人和包裹A，包裹B在M地。目标状态机器人和包裹A，包裹B在N地。

图规划问题的问题描述：采用STRIPS问题域描述方法。

图规划的算法表示：图规划主要由两个阶段组成：图扩展与规划解的提取。

1.1 图的扩展

机器人运输完整规划图如图2所示，第一列由运输问题的初始状态组成，成为命题列。第二列为动作列，若在操作集合中能够找到它的前提在上一步命题列中的操作，则表示这个操作可以实例化，实例化后得到一个动作节点，这些动作节点组成动作列。第三列为命题列，由上一步的所有动作例添加效果后构成，其中也包括no-op动作，命题列生成后要对该命题列进行搜索看是否存在目标命题，若出现目标命题并且任意两个命题都不互斥，则规划图的扩展结束。若无则继续扩展规划图。将相连的命题列与动作列用实现和虚线连接起来，其中实线表示添加效果，用虚线表示删除效果。

1.2解的提取

如图2所示时间步4的命题列中机器人运输问题的目标状态全部出现，并且任意两个命题都不互斥。规划图的扩展结束，进行有效解的搜索。对于“at A N”，我们选择在时间步3动作列中支持它的动作“pickup A N”；同样对于“at B N”，我们选择在时间步3动作列中支持它的动作“putdown B N”。 “putdown A N”与“putdown B N”不相冲突。

接着执行目标集合创建的步：在时间步3的命题列中将“putdown A N”的前提“in A P”、“at P N”与“putdown B N”的前提放在一个集合中即得到次目标集合：｛“in A P”、“in B P”、“atP N”｝. （1.1）

对上面得到的次目标集合继续搜索支持动作。

选法1：从图2中可以看到对于次目标“in A P”，可以有两种不同的选择，如果选择支持动作no-op支持；同样对于次目标“in B P”和“in P N”，都选择支持动作no-op支持；这三个选定的动作互不冲突，得到次目标集合：

｛“in A P”、“in B P”、“at P N”｝（1.2）

对比式1.1与式1.2中，这两个次目标集是相同的，但是他们又处于不同的时间步，所以接下来在寻找支持工作时就会碰到不同的情况。支持“in A P”的动作“pickup A M”与支持“in B P”的动作“pickup B M”不冲突，但是支持“at P N”的动作“move M N”却与“pickup A M”、“pickup B M”冲突，所以此选择无解退回。

选法2：对次次目标“in A P”，可以有两种不同的选择，如果选择支持动作no-op支持；对于次目标“in B P”，在他的两个两种不同的选择中选择支持动作no-op支持；这次对于次目标“in P N”，在他的两个两种不同的选择中选择支持动作“move M N”支持。这次选择的这三个动作不相冲突，所以我们可以在此选择上执行目标集合创建步，得到次目标集合

｛“in A P”、“in B P”、“at P N”、“fuel P”｝（1.3）

继续用以上方法搜索直至出现初始状态搜索结束，得出有效规划解：

时间步1为“pickup A M”和“pickup B M”

时间步2为“move M N”

时间步3为“putdown A N”和“putdown B N”

2　基于图规划的路径规划系统的设计

基于图规划的智能小车路径规划系统主要由电机驱动、寻迹、避障、单片机、火源传感器、风扇、电源七个模块组成。

本系统的主要设计思路：分为硬件方面的设计与软件方面的设计。硬件方面：利用红外对地图上的路面情况进行探测，确定前走的区域，利用火源传感器检测火源信号。然后将检测到的两种信号进行处理，送给单片机控制模块进行运算，再将输出的信号提供给驱动电机模块以驱动电机转动，达到控制小车运动的目的。软件方面：将路径规划问题抽象出来，利用STRIPS规则将规划问题转化为规划图的形式，然后在规划图中实施一个由后向前的链式搜索提取规划解，最后将得到的规划解传送给STC89C52，从而控制小车能够按照求得的规划解行走以达到提高路径搜索的目的。

3　小结

测试环境：设计行驶地图，在地图上任意设置障碍物和火源的位置，让小车从起始点出发，避开障碍物到达火源位置。经过实验证明利用图规划系统进行的路径规划速度明显高于传统的基于传感器路径规划的速度，由此可见基于图规划系统可以很好的提高路径搜索的效率。

参考文献

［1］ 李和香，董少英.图规划在排课系统中的应用［J］. 自动化与信息工程，2007，02：26-28.

［2］谷文祥，殷明治，徐丽等.智能规划与规划识别［M］.北京：科学出版社，2010.

［3］刘吉颖，方思行. AI规划的回顾与展望［J］. 中山大学学报论丛，2000，05：78-81.

［4］ 李天际，姜云飞. 图规划及其扩展的分析和研究［J］. 计算机科学，2001，07：69-73.

［5］姜云飞［J］.译.自动规划：理论和实践［M］.北京：清华大学出版社，2008.

图2　机器人运输规划图

2015年海南省高等学校科学研究项目（Hnky2015-76）

Lin Ermin1，Zhang Fengchun2，Cai Lisha1
（1.Hainan Software Profession Institute QionghaiHainan 571400China；2.Haikou advanced technical school Haikou 570102China）

Abstract：With the development of science and technology，Robotics research is a hot topic，people tend to use robots to do some dangerous work instead of people.The path planning is one of the difficulties of robotics research，in this paper，by the example of the robot's transportation problem，introduced the algorithm of Graphplan，and how to use the technology of Graphplan to solve the problem of Path planning.

Keywords：Graphplan；Path planning

基金项目：2016年海南软件职业技术学院科学研究项目（Hr201602）