基于A*算法与人工势场法无人车路径规划的改进探索

    张皞宇 杨刘一 陈旭淼

    

    

    

    摘要：针对静态地图全局路径规划问题提出了一种改进的A*算法。根据激光雷达扫描从而获取地图数据再建立栅格地图环境模型，再使用A*算法进行初步的路径规划。其次，针对A*算法规划的路径靠近障碍物以及转向角度偏大的缺陷，提出将A*算法与人工势场法相结合，在行驶阶段中通过建立车辆与障碍物之间的斥力场使得行驶路径远离障碍物。当目标车辆行驶到一定范围内，通过人工势场法的引导将车辆准确引导至目标地点，同时解决转折角度过大等问题，让车辆的行驶路线更加平滑，经仿真实验，测试和证实了本文算法的可行性。

    关键词：A*算法;人工势场法;路径规划

    中图分类号：TP311? ? ? 文献标识码：A

    文章编号：1009-3044（2021）17-0233-03

    开放科学（资源服务）标识码（OSID）：

    1 引言

    避障路径规划和跟踪控制是智能车辆研究領域的热点之一，其中避障路径规划经过多年的发展，已经积累了许多的研究成果，包括A*、蚁群算法、人工势场法，多项式规划等[1]。

    A*算法通过启发函数能够快速锁定目标方向进行路径规划。能在已知地图中有效地规划最优路径，但实际导航中需与局部规划算法结合[2]。

    传统的A*算法中有依旧存在如：路径紧贴障碍物和转向角度过大和不满足车辆运动学等问题[3]。

    针对上述问题，本文通过对传统A*实施改进，加入了人工势场法并对车辆模型进行简化，通过人工势场法的引力场的引力得出汽车的目标姿态角，从而改进传统A*算法中的转向角过大的问题。同样对障碍物与目标车辆附加了斥力场，通过人工势场法中斥力场的作用解决了路径紧贴障碍物的问题。

    2 A*算法与人工势场法

    2.1 A*算法

    A*算法是一种典型的启发式搜索计算方式，其中可在一定程度上避免无效搜索路径，有较好的搜索效率。在深度优先、广度优先和最佳优先3种启发式搜索算法中，A*算法归属于最佳优先类。在A*中通过评估函数进行引导搜索与决定的方向。其公式表示为：

    [f（n）=g（n）+h（n）]? ? ? ? ? ? ? ? ? ? ? ? ? （1）

    [f（n）]表示从起始点到目标点的估价函数;[g（n）]是在从起始点到节点[n]的移动代价;[h（n）]是从节点[n]到目标节点估计代价，通过上述函数可以得到每个函数的价值，通过选取价值最低的节点来进行最优节点的选取，从而直接决定了算法能否进行最优路径的查找。

    2.2 人工势场法

    人工势场法是由Khatib提出，通过设置假想力的概念促使目标进行移动[4]。该方法将控制对象、目标点、障碍物看作质点，目标点对控制对象形成引力场，障碍物对控制对象形成斥力场。通过产生的引力场与斥力场的合力从而引导控制对象的行动。此过程是将控制对象在实际环境中的运动过程虚拟为电荷在受力场中的运动。

    同样，在驾驶环境中，不可通过的部分设置为与控制对象相同的电荷，即可产生斥力场，可以在目标地点设置相反电荷来形成引力场。由此来控制目标的行走路径。有着结构简单，实时性强，规划路径简单且路径平滑等优点。

    3 本文算法

    3.1.环境模型

    在小车机器人工作中，对地图的构建是关键。在通过URG-04LX-UG01激光雷达扫描得到数据，规划由本算法过栅格地图的方式进行表现，通过栅格法将小车可通过的区域和不可通过的区域在栅格地图中做出呈现。

    在算法中每个栅格的状态位两种分别为可通过与不可通过。在算法中分别由0与1进行表示。在栅格地图中分别由白色（可通过）和黑色（不可通过表示）。

    其中在栅格地图中的栅格大小会影响后续对于路径规划的效果。当栅格偏大时，能够减小运算量与规划时间，但会导致规划的路线过于粗糙使得行走的路线增加;当栅格偏小时，使得行走的路程准确率增高，让规划时间大幅度上升。由此，栅格地图的大小需要更具实际情况进行设定，包含场地与实验对象的考量。

    3.2算法实现

    3.2.1 A*的路径选取

    将实验对象的场地用栅格地图进行表示后，可以根据栅格地图的信息得到实验对象的地图环境：

    [M={Mi，i=0，1，2，3}]? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

    其中[M0]为实验对象起始点，[M1]为可通过区域，[M2]为不可通过区域，[M3]为目标区域。

    A*算法在静态环境中进行路径规划实验时具有较好的实时性，从而可迅速高效地求解最优路径[5]。在A*算法设计中，本文采用欧式距离作为启发式函数：

    [h（n）=（xi-xn）2-（yi-yn）2]? ? ? ? ? ? ? ? ? ? ? （3）

    其中起始点在栅格地图中横坐标为[xi]，起始点在栅格地图中纵坐标[yi]。终点在栅格地图中横坐标[xn]，终点在栅格地图中纵坐标[yn]。

    其中图1为A*算法的实例：

    3.2.2 行驶阶段

    在行驶阶段中，为解决传统A*算法中出现的规划路径贴近障碍物边缘导致不符合正常汽车行驶情况。本文算法中将人工势场法加入，通过给障碍物添加负电荷，形成斥力场在行驶过程中，目标车辆受到障碍物的斥力随着距离减小使得斥力越大。因此，势能和距离成反比。公式如下：

    [F=-grad（kl），l≤lmax0，其他]? ? ? ? ? ? ? ? ? ? ? （4）

    其中[F]代表目标车辆受到的斥力，[k]代表相应系数，[l]代表目标车辆与障碍物的距离，[lmax]为势场作用的最大范围。

    同样通过斥力场的产生的斥力作用，解决在路径紧贴障碍物这一不符合汽车行驶的情况。

    由于本文在地图扫描阶段中采用URG-04LX-UG01激光雷达，此雷达扫描范围为240°（图2）。故本文提出在目标汽车后方120°人工添加假想障碍物（图3），从而在人工势场法斥力场计算给予目标汽车一个斥力使得汽车在引力场和斥力场计算中能够获得一个向前行驶的斥力。

    3.2.3局部阶段

    因在环境模型中将地图通过栅格的表达方式，故当实验对象进入目的地栅格时，则进入局部规划阶段。在局部规划阶段中，本算法通过人工势场法中的应力场对小车机器人进行引导。

    在目标汽车的引导阶段中，会出现需要使目标阶段转向的情况，此时则需要对目标的转向角与姿态角进行计算。在本文算法中为将目标四轮车辆简化为两轮车辆。从而进行相应的计算。

    通过引力场的牵引力，在计算出小车每时刻的姿态角，其中计算转向角[u]的公式为：

    [u=tan-1[Lv（λ（θr-θ）+θr）]]? ? ? ? ? ? ? ? ? （5）

    其中[L]为车辆轴距，[v]为车辆速度，[θ]为车辆姿态角，[θr]为目标姿态角，[λ]是转向系数。

    其中在确定转向角之前，需要确定目标姿态角，该姿态角等于人工势场法中合力的角度。

    基于应力场的特性，可以让小车的转向曲线更加平滑，符合实际的汽车运动情况。

    4实验结果

    为验证算法的可行性和有效性，进行了计算机仿真实验，使用Matlab软件对汽车目标做出规划与到达地点的行驶，并对转向角度进行测试。其中地图的扫描构建采用URG-04LX-UG01激光雷达。所用小车如图4所示：

    由于在仿真中，车辆的行驶默认为匀速驾驶，在到达目标地点时，由于出现了转向，匀变行驶使得在到达指定地点时出现些许误差。通过多次测试，与设定的目标点偏差如图5在10mm之内：

    在行驶过程中目标汽车的转向角和姿态角变化如图6、图7所示。

    5 结论

    通過将A*算法和人工势场法相结合，能够较好地对汽车目的地进行路径规划。同时由于人工势场法的引入，能更好地调整汽车目标转向角，使得在转向操作时角度更加合理，从而达到汽车行驶为平滑路径的效果。在与目标汽车障碍物建立斥力场，规避了路线紧贴障碍物，使其更符合实际行驶需要。通过一系列的仿真实验，证明了本算法的可行性。

    参考文献：

    [1] 杨博，张缓缓，江忠顺.智能车辆的避障路径规划与跟踪控制仿真分析[J/OL].中国测试：1-8[2020-11-11].http：//kns.cnki.net/kcms/detail/51.1714.TB.20201016.1753.015.html.

    [2] 孙炜，吕云峰，唐宏伟，等.基于一种改进A*算法的移动机器人路径规划[J].湖南大学学报（自然科学版），2017，44（4）：94-101.

    [3] 马飞，杨皞屾，顾青，等.基于改进A*算法的地下无人铲运机导航路径规划[J].农业机械学报，2015，46（7）：303-309.

    [4] KHATIB O.Real-time obstacle avoidance for manipulators and? and mobile robots[J].The International Journal of Robotics Research，1986，5（1）：90-98.

    [5] 王维，裴东，冯璋.改进A*算法的移动机器人最短路径规划[J].计算机应用，2018，38（5）：1523-1526.

    【通联编辑：光文玲】