基于定向加权A~*算法的自主移动机器人路径规划

0引言

路径规划作为自主移动机器人研究重点,如何才能按照指定路径高效运动成为研究热门。最短路径作为路径规划问题的核心,一切运动都是以最短距离、最省时、最快速地完成任务为目标。启发式搜索算法作为最短路径问题研究的经典算法得到广泛应用。

启发式搜索是一种智能控制算法它模拟人脑的认知模式即利用问题拥有的启发信息来引导搜索,减小搜索范围、降低问题复杂度。启发式搜索算法包括深度优先、广度优先和最佳优先。A*算法是一种最佳优先的启发式搜索算法虽然其在应用中有较好的效果但同时也存在折点多、横穿障碍物、运行时间长、累计转折角度大等问题。针对这些缺点本文提出一种定向加权A*算法。

1传统A*算法

A*算法是一种典型的启发式搜索算法其搜索方向分为四方向搜索和八方向搜索:其中四方向搜索是指以起点开始同时向起点的垂直水平四个方向进行搜索找出代价估计值最小的节点作为下次搜索的起点,以此类推直到找到目标点。八方向搜索是在四方向搜索的基础上加人左上、左下、右上、右下四个方向进行搜索其搜索过程及运算方法都与四方向搜索相同。具体搜索方向图如图l所示。
基于定向加权A~*算法的自主移动机器人路径规划
A*算法是从起点开始搜索代价值最小的节点为下一次搜索的起点,一直到搜索到目标点]这样搜索可以从一开始保证代价估计值是最小的,最终形成的路径代价值也同样最小。具体过程为:通过估价函数f(n)来估计当前点到终点的距离,并且决定搜索的方向,当搜索失败时会寻找别的路径,因此A*算法的成功与否主要取决于估价函数An),其中估价函数表示为:

f(n)=g(n)+h(n) (1)

这里的f(n)是从初始状态经由状态n到目标状态的代价估计g(n)是在状态空间中从初始状态到状态n的实际代价h(n)是从状态n到目标状态的最佳路径的估计代价。h(n)含有启发信息,它决定A*算法的搜索效率;g(n)是实际距离的代价其所占的权重影响算法的折点数。只有当g(n)和h(n)达到一个合适的值时算法才能达到最优。

距离代价函数g(n):常见的评估距离的函数有三种:曼哈顿距离、欧氏距离和切比雪夫距离(4-15],以上三种距离评估方法都是针对二维平面中的两个点(x1,y1)和(x2,y2)在没有障碍物的时候三种距离代价评估得出来的效果基本一致,存在障碍物时三种方法就略有差别了。
曼哈顿距离:
基于定向加权A~*算法的自主移动机器人路径规划
欧氏距离:
基于定向加权A~*算法的自主移动机器人路径规划
切比雪夫距离:
基于定向加权A~*算法的自主移动机器人路径规划
通过三种距离公式的分析:本次A*算法改进选用欧氏距离为距离代价函数g(n),主要原因为:1)本次算法改进主要以实际距离为基础而欧氏距离最能代表实际情况中两点间的距离。2)本次改进算法是以最短路径为目标因此切比雪夫距离不适用。3)本次改进算法是通过把搜索方向分类进行改进,一级搜索为竖直方向和水平方向的四个方向在这个四方向上欧氏距离和曼哈顿距离是一致的,二级搜索为左上、左下、右上和右下的四个方向,在这个四方向上欧氏距离测得的距离代价比曼哈顿距离测得的距离代价值小更能满足本次改进的要求。

A*算法具体步骤如下:

1)首先根据实际情况建立仿真栅格地图,确定障碍物和起始点的位置。

2)假设起始点S,目标点G,开始创建两个列表开启列表Open表关闭列表Closed表同时初始化Closed表。

3)把起始节点s放入开启列表Open表。

4)查找开启列表Open表中的节点,假如开启列表Open表为空则说明搜索失败没有找到最优路径。

5)假如开启列表Open表不为空从开启列表Open表中选取最小代价(n)对应的节点n。

6)把节点n从开启列表Open表中取出来放入关闭列表Closed表中。

7)查看节点n是否是目标节点G,如果是则搜索成功退出如果不是转步骤8)。

8)把节点n的八个方向对应的子节点全部扩展出来假如子节点为m则计算n的每一个子节点m对应的每一个代价值f(m)。

9)选取出子节点中对应的最小代价值假设f(p)是所有代价f(m)中最小的代价值则以f(p)对应p节点为下一个搜索节点。

10)重复步骤5)~9)直到找到的节点是目标节点G则完成算法搜索得到最优路径反之算法搜索失败重新规划仿真栅格地图,确定障碍物和起始节点的位置进行二次搜索。
根据 A* 算法的原理对传统 A* 算法进行仿真实现,具体实现的仿真图如图 2。
基于定向加权A~*算法的自主移动机器人路径规划
其中三角形(△)代表起点,圆形(O)代表目标点,黑色方格代表障碍物图中每一个栅格代表一个单位(1cm)。通过对传统A*算法的仿真实现发现其存在横穿障碍物和折点多的问题图2(a)是对传统A*算法进行八方向搜索实现的仿真图通过仿真图可以看出在搜索过程中A*算法的八个方向搜索存在与实际不符的搜索路径,因为它只是针对当前位置的八个方向进行搜索,不去考虑实际情况能否通过。以图2(a)为例可以看出在实际情况下机器人是不可通过,但是由于A*算法八个方向搜索的特性在仿真中出现了横穿障碍物运动的路径。基于八个方向的这种与实际不符的搜索过程提出对A*算法进行四个方向搜索的算法实现。以图2(b)为例改进后的四个方向搜索运动很好地避免了横穿障碍物的问题但是却存在折点多的问题基于此提出一种定向加权A*算法来克服传统A*算法的不足。

2算法改进

经过对传统A*算法的理论分析以及仿真验证,发现其存在横穿障碍物和折点多等问题,为此本文提出一种定向加权A*算法来对其进行改进,定向加权A*算法顾名思义分为两部分:定向和加权其中定向是对其搜索方向进行设定,加权是对其实际代价距离值进行加权实现最后将二者结合来实现算法的改进。

2.1算法定向

通过传统A*算法的仿真实现可以发现其八个方向搜索从三角形(△)起点到目标点(O)的距离总共为27.8cm(每个小格子代表1cm斜边取1.4cm),折点数为12个,四个方向搜索从起点到目标点的距离总共为30cm,折点数为13个,通过对比发现在距离和折点数上八个方向搜索都优于四个方向搜索因此本次定向是在八个方向搜索的基础上进行定向改进。

具体步骤如下:首先把八个方向进行分级以水平和垂直四个方向为一级搜索方向以左上、左下、右上、右下四个方向为第二级搜索方向。一级搜索方向上没有障碍物时开始进行二级搜索以此类推直到找到目标点;当一级方向上有障碍物时则不进行二级对应的搜索如图1(b)所示。

应用算例:如图1(b)所示,A方向存在障碍物影响机器人运动则不会朝A方向运动的同时也不会对E和F两个方向进行搜索这样也就不会在E和F两个方向上产生位移;同理如果B方向上有障碍物则不会在F和G两个方向上进行搜索这样就可以有效地避免A和B方向上都有障碍物时机器人还会进行F方向运动所产生的碰撞障碍物的危险。C和D方向也同理即可实现定向有效地解决了八个方向搜索中存在移动机器人横穿障碍物运动的问题。经过定向改进后实现的仿真图如图3所示。
基于定向加权A~*算法的自主移动机器人路径规划
通过定向的仿真图可以看出有效地解决了机器人横穿障碍物的问题但是折点数依然是12个,折点多这个问题还没得到改善,为了改善折点多的缺点进一步提出距离加权来进行改进。

2.2算法单轴加权

折点多在实际机器人运动中也就是意味着机器人运动时的转角多机器人要不停地进行转向这样在实际运动中很大程度上影响了机器人的运动效率,每一次转向不但影响时间,能耗也大,因此减少转角的次数对移动机器人运动来说是至关重要的。提出距离加权法对折点多的问题进行改进。

具体步骤如下:首先因为算法是在栅格中进行地图的构建是在点与点之间进行距离计算所以对各个点的x轴和y轴两个方向分别进行不同倍数的加权,仿真图如图4~6所示。

通过对比图4~6发现在对距离代价的各个方向进行不同的加权可以得到不同的搜索路径,同时X轴加权对路径规划减少折点起关键作用。通过仿真分析可以看出随着X轴权重的改变,可以得到不同的折点数,但是当X轴和Y轴的权重达到6倍后其x轴和y轴的权重对具体路径规划过程产生折点数的影响是相同的并且折点数较X轴进行5倍加权的折点数变多产生这一变故的原因是:随着权重的增加,规划路径中的距离代价远大于环境中的启发代价距离代价起到了主导总体代价的作用所以才会产生各个分量的代价影响相同折点数变多的问题。
基于定向加权A~*算法的自主移动机器人路径规划

基于定向加权A~*算法的自主移动机器人路径规划
2.3算法x轴和Y轴同时加权

对单个轴加权算法的实现发现其虽然可以减少折点数但是还存在路径不是最优的问题。其中以X轴进行5倍加权折点数最少距离值为24.2cm但是结合实际来分析其折点最少但距离却不是最短所以在单个轴加权的基础上进一步提出双轴加权。

具体计算步骤如下:对X轴和Y轴同时进行加权验证,仿真图如图7所示。

通过对比发现:当对整体距离不进行加权时其折点数是最多的12个,并且路径是最长的28.8cm;当对整体距离进行3倍加权时,其折点数是最少的3个,并且路径是最短的23.4cm;当加权为4倍时,其折点数是6个,并且路径为26.6cm。经过对折点数以及距离的最优进行分析得出结论:整体距离权重为3倍时是最优的路径规划。

3应用算例及仿真

在Matlab2014a上进行算法仿真实现其中起始点、目标点和障碍物都随机生成。在随机的起始点、目标点和障碍物中随机地确定了一张仿真地图对其进行算法的改进和实现。栅格的大小为20×20代表移动机器人路径规划区域的大小,黑色方格代表障碍物的位置。通过仿真可以发现每一次不同的搜索启发式信息搜索的位置都不同,这是由加权和定向所影响的迭代时间和过程导致的。

为了更好地验证定向加权A*算法的优越性本文以距离和折点的多少作为主要指标同时引入平滑度、算法运行时间、累计转折角度等对定向加权A*算法进行指标测试具体指标如表l所示。
基于定向加权A~*算法的自主移动机器人路径规划

基于定向加权A~*算法的自主移动机器人路径规划
实验结果表明改进后的定向加权A*算法在各项性能参数上都优于传统A*算法,本次对比主要以传统A·算法八方向搜索进行比较说明,定向加权A*算法较传统A*算法在路径距离上减少了4.4cm运行时间上减少了1.201s,折点数上减少了9个,累计转折角度减少了675°,相比之下各项部得到了提高同时也更加能适应客观需求。

4结语

A*算法是智能控制算法中的一个重要算法,但其本身也存在搜索效率低和多折点的问题。为实现高效率、低折点的最优算法定向加权改进法是通过对传统A*算法本身迭代过程进行条件约束达到最优.实验仿真对比以及备性能参数的比较说明定向加权A*算法不仅避免了实际中横穿障碍物的危险同时也解决了折点多、算法运行时间长的问题有效地降低了移动机器人规划路径的长度、累计转折角度,使算法各方面性能都得到了提高。

基于定向加权A~*算法的自主移动机器人路径规划-AGV吧
基于定向加权A~*算法的自主移动机器人路径规划
此内容为付费资源,请付费后查看
20积分
付费资源
© 版权声明
THE END
喜欢就支持一下吧
点赞8赞赏 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容