应用于机器人路径规划的A―star算法研究

[摘 要]移动机器人自主寻路技术是当前科技发展的热点领域，本文针对传统的A-star算法搜索出的路径不易于机器人的运动控制、搜索速度慢提出了一种改进的路径规划方法。该方法在栅格化环境地图中进行路径搜索，对传统的算法的搜索策略和启发函数进行了优化。实验仿真结果表明了新方法的有效性。

[关键词]机器人；路径规划；A-star算法

中图分类号：TP242 文献标识码：A 文章编号：1009-914X（2016）20-0218-01

1 引言

科学技术日新月异，移动机器人的应用范围越来越广。路径规划是移动机器人实现自主导航的关键技术之一[1-5]。按照移动机器人对环境的认知程度，可以将路径规划分为基于先验信息的全局路径规划和基于传感器信息的局部路径规划。A-star算法是全局路径规划的经典算法之一；然而，传统A-star算法在搜索过程中也存在自身的缺陷，如搜索出的路径不易于机器人运动控制、搜索速度慢等。本文针对复杂环境下A-star算法的缺陷进行了启发函数和搜索策略的改进。

2 A-star算法概述

A-star算法作为一种启发式搜索算法的优势就在于从当前搜索节点搜索下一步节点时，由一个启发函数来引导选择代价最小的节点作为下一步搜索节点。这样减少了搜索空间，提高了效率。A-star算法中代价函数如下：

1.1

上式1.1中，表示从起始点经过节点n到达目标点的最低代价的估计值，它由两部分组成：一部分为，是从起始点到当前点的实际代价值；表示从当前点到目标点的估计代价值，称为启发函数。

A-star算法的应用关键在与启发函数和Open、Close列表的设置，好的启发函数可以加快搜索速度，合理的Open、Close列表设置能节省存储空间。Open列表用于存放未被检测过的位置点，Close列表用于存放已被检测完毕的位置点。

3 改进的搜索策略

首先， A-star算法的搜索核心是启发函数，启发函数使其避免了盲目性搜索的繁杂性。传统的A-star算法所使用的启发函数是经典的Manhattan距离或欧几里得距离。

分析A-star算法的搜索过程可知，当启发函数（是最终真实路径的距离）时，此时搜索范围较大，运行效率低下，搜索时间长；当启发函数时，算法的搜索过程将按照最理想的路径点一步步往下搜索，但是现在情况不能满足该种情况的要求；当时，搜索范围较小，运行效率较高，搜索时间较短，但是搜索出的路径不是最短的所以，为了得到较高的运行效率和最优的路径，我们应当选取启发函数的值接近于。因为A-star算法在进行下一步搜索时，只能搜索与其当前位置相临接的位置点，并不是任意、盲目地选取下一点。如图1所示，根据以上分析，本文结合Manhattan距离和欧式距离设置的启发函数如下式。

当时，代价函数改写为

当时，代价函数改写为

上式1.4中，和分别表示机器人当前节点与目标节点之间横坐标和纵坐标的差值，。

其次，在栅格环境中运用传统A-star算法进行路径搜索时，得出的结果会出现经过障碍物顶尖的情况，这在实际情况中是不允许的。分析算法在选取下一点的搜索原理可知，出现该情况的原因是在栅格环境中往左上、左下、右上、右下方向进行搜索时搜索的限制条件没有将与机器人当前位置相邻区域的环境情况考虑在内。本文对搜索过程做如下改进：

①机器人当前位置为，进行下一步的搜索，如果下一步位置为则执行②；如果下一步位置为则执行③；如果下一步位置为则执行④；如果下一步位置为则执行⑤；否则执行⑥；

②判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

③判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

④判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑤判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑥计算此点的、、值。

⑦更新搜索节点。

4 实验仿真与结论

基于以上优化方法，本文在MATLAB2014b中进行了仿真，假设移动机器人的运动环境已知，为栅格化环境模型。图2为改进后的A-star算法仿真得出的路径规划结果，黑色为障碍物，白色为可行区域，其他颜色表示比较危险的可行区域。

与的传统A-star算法相比较，改进后的A-star算法搜索时间减少了0.04s，搜索的节点数减少了4.9%，路径的关键节点数减少了50%，并且路径没有过障碍物顶尖的现象，改进后的A-star算法会优先选择远离障碍物的安全区域规划路径，最终生成的路径更加符合机器人的运动控制。说明改进后的A-star算法是可行的。

机器人路径规划是一个经典研究领域，在当前复杂的生产、生活背景下，一方面对机器人的实时性提出了更高的要求，另一方面对规划出的路径安全性、与人相容性有了提出了更高的性能指标要求。本文充分考虑了机器人对实时性和安全性的要求，提出了改进的A-star路径规划方法，提高了搜索速度，降低了碰撞发生的可能性，并通过仿真实验验证了新方法的有效性。

参考文献

[1] 蔡自兴，贺汉根。未知环境中移动机器人导航控制理论与方法[M]。北京：科学出版社，2009.

[2] 王殿君。基于改进A*算法的室内移动机器人路径规划[J]。清华大学学报（自然科学版）。2012，Vol.52， No.8.

[3] 马喜峰， 张雷. 基于对称极多项式曲线的移动机器人平滑路径生成[J]. 机器人， 2005， 27（5）： 450-459.

[4] 翁敏，毋河海，杜清运，李林燕.基于道路网络知识的启发式层次路径寻找算法[J].武汉大学学报信息科学版.2006，31（4）：360-363.

[5] Roland S， Iiiah R N， Davide Scaramuzza， Introduction to Autonomous Mobile Robot[M]. USA： The MIT Press， 2012

作者信息：杨兴，硕士研究生，专业机械电子工程，研究方向移动机器人，