1、第 33 卷第 2 期2023年6月Vol.33 No.2Jun.2023湖 南 工 程 学 院 学 报（自 然 科 学 版）Journal of Hunan Institute of Engineering（Natural Science Edition）收稿日期：2022-06-29基金项目：湖南省自然科学基金资助项目（2023JJ50029）；湖南省教育厅一般项目（22C0427）；湖南工程学院青年科研项目（21015）.作者简介：肖岳平（1994-），男，硕士，研究方向：机器人系统.肖岳平，阳倩，苏焱鸿，黄守鹏（湖南工程学院 电气与信息工程学院，湘潭 411104）摘要：针对移动机器人
2、在全局路径规划中不能进行动态实施避障、在局部路径规划中效率低等一系列问题.本文基于Gazebo的3D仿真环境，引入权重系数控制A*（A-star）算法的启发函数，减少全局规划路径的拐点，获取全局最优路径，提高算法效率；并选取全局最优路径上动态变化点作为DWA（Dynamic Window Approach）的关键点进行动态避障.仿真实验结果表明：基于改进A*与DWA的融合算法，既保证全局路径规划最优，且调整速度权值，并兼顾安全性和高效性.关键词：改进A*算法；路径规划；DWA算法；Gazebo环境开发中图分类号：TP242文献标识码：A文章编号：1671-119X（2023）02-0030-0
3、8基于改进A*与DWA算法融合的路径规划仿真设计0 引言随着高新技术的不断创新与发展，移动机器人已经在人类日常生活中占有重要的地位.而在移动机器人研究领域中，路径规划是科学家们重点关注与研究的对象1.对于当前机器人路径规划的算法，可以分为全局路径规划算法和局部路径规划算法2.全局路径规划算法常用于静态环境，实时性略差3；局部路径规划算法则适用于动态环境，注重移动机器人的动态避障能力4.因此，移动机器人如何在实时避障的同时找到一条最优路径，对路径规划算法的研究显得至关重要5.本文在改进了全局路径规划A*算法6的基础上融合了局部路径规划算法 DWA（dynamic window approach）
4、7，仿真实验结果表明：该算法可以保证路径规划的安全性和高效性.1 仿真设计思路为了更加直观体现该算法的优越性，本文先基于Gazebo的3D环境创建模型和搭建环境，再使用改进的A*与DWA融合算法进行路径仿真设计.设计思路如图1所示.基于Gazebo的3D仿真环境开发模型创建环境搭建经典A*算法改进高效率获取全局最优路径融合DWA算法选取全局中的动态点进行处理对融合算法进行路径规划仿真图1 设计思路流程图DOI:10.15987/ki.hgbjbz.2023.02.010第2期2 改进A*算法2.1 经典*算法概述经典 A*算法是一种静态路网中求解最短路径最有效的直接搜索方法8，在 CARDON
5、A 等9提出的算法的基础上，加入了启发式函数，使其在搜索到下一个节点时，可以把当前所知的步数或环境等信息引入，对当前状态进行估计，判断当前节点在最佳路径上的可能性10，对于可能性大的节点，下一步进行优先扩展，以此来提高算法搜索效率.经典A*算法引入目标点到当前点的估计代价，根据估计代价决定路径搜索方向，提高了算法效率11.其评价函数表示为：f(n)=g(n)+h(n)（1）式（1）中，n代表当前节点；f(n)表示的是移动机器人在当前节点的评价函数，用来选取最优路径；g(n)是从起点到终点的移动代价；h(n)表示从结点 n 到目标结点的评估代价12，也叫启发函数.根据启发函数的选择不同，最终得到
6、的 A*算法的f(n)也有比较大的差距.经典 A*算法的缺陷是在计算最优路径的时候将会访问大量的节点，此时算法的内存占用会较大，同时计算时间也会比较长，算法效率差13.A*算法流程图如图2所示.2.2 基于启发函数的优化方案由经典A*算法的评价函数不难看出，A*算法的核心思想在于启发函数h(n)的设计，因此，启发函数的选择在一定程度上决定了A*算法的性能和寻路质量.按经典启发函数h(n)寻找最优路径，会使所需搜索的节点过多，降低搜索效率.改进的A*算法通过引入一个h(n)的权重系数w(n)，来控制A*算法的启发函数，如式（2）所示.f(n)=g(n)+w(n)h(n)（2）其中w(n)1，由公
7、式可以知道，通过改变w(n)的值来影响搜索过程中h(n)对 A*算法的影响，并且可以看出，若w(n)越大，就更趋近于广度优先搜索算法，算法的效率就会越高.在实际应用过程中，我们可以灵活选取w(n)的值，以提高A*算法的适应性.开始把起始点和障碍物节点分别加入开放列表和封闭列表中将该栅格周围的栅格加入开放列表中保存路径结束N跳过该栅格继续扩展其他栅格Y判断开放列表是否为空？判断当前栅格是否为目标点？判断当前栅格是否在封闭列表里？N计算代价函数值f(n)=g(n)+h(n),从开发列表中选择f(n)最小的栅格加入封闭列表YYN图2 A*算法流程图2.3 关键点选取方案经典A*算法搜索的路径节点位于
8、栅格地图每个栅格的中心位置，然后依次连接构成路径，存在一些冗余的共线节点和转折点.若以此路径导航行驶，机器人在每个不必要的转折点处都需要改变航向角，这些多余动作会直接影响机器人的正常运行.在实际的导航过程中，机器人较顺畅地移动可以减少误差的产生，更利于精准地完成工作.因此，针对这一问题，利用一种关键点选取策略优化经典A*算法规划的全局路径，只保留必要的路径节点，提肖岳平，等：基于改进A*与DWA算法融合的路径规划仿真设计312023年湖南工程学院学报（自然科学版）高路径的高效性.关键点选取策略的具体实施步骤如下：设路径节点集为Pk|k=1,2,3,.,n，且已知每个节点的坐标信息.P1表示路径
9、的起始点；Pn表示路径的目标点.从 P1开始，求解向量?P1P2和向量?P2P3，并判断两向量之间的夹角大小.分为两种情况：（1）若夹角大小为零，说明P1、P2、P3三个路径节点在同一条直线上，则为冗余的共线节点，需剔除.（2）若夹角大小不为零，说明P1、P2、P3三个路径节点不在同一条直线上，则求解线段方程L（P1P3），并判断该线段的预设安全距离范围内是否存在障碍物.若不存在障碍物，则 P2为冗余转折点，需剔除；若存在障碍物，则P2为必要转折点，需保留.由于冗余点的剔除会造成原有的路径节点集发生变化，因此，在重复上述步骤的同时，需不断更新剔除冗余点之后的路径节点集，并依次计算检验所有的路径
10、节点.最终，通过关键点选取策略剔除冗余点，保留必要的路径节点，优化得到一条只包含起始点、关键点和目标点的全局导航路径.3 改进A*与DWA算法融合改进A*算法得到了只包含起始点、关键点和目标点的导航路径，但无法避开环境中出现的未知障碍物.DWA算法具有良好的局部避障能力，但只有一个最终目标点作为指引，容易陷入局部最优.因此，本文将两种算法融合，以提取的改进A*算法规划的全局路径关键点作为 DWA 算法的中间目标点，优化后的评价函数使局部路径规划遵循已规划的全局路径轮廓.通过融合导航算法，以实现移动机器人导航过程中的全局路径最优，同时兼具实时避障功能.算法的具体流程如图3所示.首先，采用改进A*
11、算法规划出一条全局路径，利用其优化的代价函数以及关键点选取策略对路径进行优化，并得到路径必要的关键节点.然后，以提取的路径关键点作为DWA算法的中间目标点，指引局部路径的规划.DWA 算法对移动机器人的速度进行采样，并模拟出各速度对应的移动轨迹，利用结合关键点信息的评价函数选取出最优的模拟移动轨迹，并以最优轨迹对应的速度控制机器人向目标点移动，从而实现改进A*算法和DWA算法的融合.最后，在融合导航算法下，移动机器人遵循全局路径轮廓依次接近或到达中间目标点，直至到达最终目标点.开始栅格地图与参数的初始化选取计算节点计算下一节点的F(n)、G(n)、H(n)更新访问节点访问完成？提取关键转折点与
12、运动方向一致？作为DWA算法的中间目标点机器人开始运动机器人速度采样模拟移动轨迹基于全局规划选取最优轨迹到达终点？结束NYNYNY图3 融合导航算法流程图4 仿真实验结果4.1 经典A*算法仿真实验在MATLAB 2017a中对经典A*算法进行仿真实验，通过程序可以设置栅格地图的大小，此处分别设置 1010 和 3030 的栅格地图进行验证，同时设置地图的障碍占比，在1010的地图中设置障碍占比为 30%，效果如图 4（a）所示；在 3030 的地图中设置障碍占比为40%，如图4（b）所示.通过仿真实验可以看出，无论是在简单还是复杂的情况下，经典A*算法都能有效地寻找出一条最佳路径14.32第
13、2期（a）1010栅格地图（b）3030栅格地图图4 经典A*算法仿真实验结果4.2 改进A*算法仿真实验在MATLAB 2017a中对改进A*算法进行仿真实验，优化前与优化后的仿真路径对比如图4所示.（a）优化前（b）优化后图4 改进A*算法仿真实验结果从仿真实验可以看出，通过经典A*算法仿真找出来的路径只是在数学上的最优路径，在最终的路径规划路线中有一些转弯是完全可以省去的，尽可能在不增加路程的情况下减少转弯的次数.仿真设置w(n)为2，A*算法和改进后的A*算法的数据对比，如表1所示.表1 A*算法与改进A*算法数据对比运算时间（s）转弯次数路径长度（格）A*算法22.2728改进A*算
14、法9.9328可以看出，改进后的A*算法运算时间比改进前快了12.3 s，转弯次数由7个降为了3个，算法效率明显高于改进前，同时路径长度并没有增加，很好地满足了实际需求.因此，改进后的A*算法缩短了运算时间，减少了转弯次数，提高了算法效率，具有一定的实际意义.4.3 融合算法仿真利用MATLAB 2017a对融合改进后的A*算法和DWA算法进行仿真实验.在改进的A*算法的实验基础上，增加了未知静态障碍物和未知动态障碍物，由此来验证融合后算法的准确性，仿真结果如图6所示.202468101214-202468101214-14121086420-214121086420-2机器人障碍物（a）（b
15、）202468101214-202468101214-14121086420-214121086420-2（c）（d）图6 融合算法仿真实验图6（a）是一个1616的栅格地图，黑色小圆点表示障碍物，黑色小三角形为机器人，白色部分为可通行区域，起始点的设置为（0，0），目标点的坐标设置为（10，10），评价函数中方向角比重为0.01，速度比重为 0.1，距离障碍物比重为 0.1；图 6（b）模拟全局路径上随机加入的未知静态障碍物，黑色线条为机器人通行轨迹，线条初始段表示开始进行局部动态路径规划，通过对不同速度进行采样，结合机器人运动模型得到可能的运行轨迹，并针对这些轨迹进行评价，进而选择一条合适
16、的路径；图6（c）为DWA 算法最终完成本次路径规划的结果，完成路径规划的时间为49.8 s；图6（d）为融合改进后的A*算法和DWA算法的规划路径，完成路径规划的时间为 29.5 s.通过实验可知，DWA 算法虽然能在动肖岳平，等：基于改进A*与DWA算法融合的路径规划仿真设计332023年湖南工程学院学报（自然科学版）态环境中进行避障，但是只能实现局部的避障功能，无法得到地图中的全局最优路径，而且在实验中当通过区域变复杂时，到达目标点的时间会变长甚至无法通过，使其陷入局部解.本文所提出的融合算法将动态窗口法与改进全局路径规划算法相结合，能在安全躲避障碍物的同时找到一条最优的路径.5 基于Gazebo的路径规划仿真把算法应用于移动机器人的路径规划仿真之前，需对仿真环境进行搭建.本文的仿真实验是基于Gazebo进行3D 仿真环境开发，包括机器人模型的创建、仿真环境的搭建、启动文件的设置、地图创建以及静态、动态环境路径规划算法验证.5.1 TurtleBot 3模型的创建在 Gazebo 中，通过编写 URDF（unified robotdescription format）脚本文件，建