一种融合改进A*与改进DWA算法的运动规划方法

一种融合改进a*与改进dwa算法的运动规划方法
技术领域
1.本发明属于智能无人车领域，具体涉及一种融合改进a*与改进dwa算法的运动规划方法。


背景技术：

2.近年来，随着信息技术的快速发展，人们的日常生活和工作都离不开智能化科技，人们逐渐进入快捷简便的智能化时代。无人车代替人工在工业生产、勘测搜寻、服务行业、物流产业等领域的应用逐渐成为主流。为了提高无人车在导航过程中的快速和稳定，提高路径规划的效率和轨迹规划的速度及稳定性非常重要，因此提出了一种融合改进a*与改进dwa算法的运动规划方法。


技术实现要素：

3.本发明的目的是提高无人车在导航过程中的快速和稳定。
4.为了解决上述技术问题，本发明专利的技术方案如下：一种融合改进a*与改进dwa算法的运动规划方法，该方法包括：
5.载入预定义的栅格地图；
6.基于无人车当前所处位置和所述栅格地图，确定目标点位置，结合改进的a*算法进行路径规划，生成初始路径节点；
7.基于上述生成的初始路径进行路径关键点提取，生成最终路径节点；
8.根据改进dwa算法生成最优的轨迹和速度，输出最优路径。
9.优选地，所述栅格地图分辨率为1m，栅格地图尺寸为a*b，其中a、b分别表示栅格地图中每行、每列的栅格的个数，其中，每个栅格表示一种区域，包括可行区域和不可行区域。
10.优选地，所述初始路径节点的规划过程包括：确定所述无人车所处当前位置与目标点，扩展传统a*算法的搜索邻域为16邻域，并将启发函数改为曼哈顿距离函数，生成代价函数值最小的无碰撞路径节点。
11.优选地，所述最终路径节点的规划过程包括：根据生成的初始路径节点，起始点加入关键节点序列，从起始点开始按顺序连接路径节点，直到连接的路径线段经过障碍物，那么选取该节点的上一个路径节点加入关键点序列，此路径节点作为新的起始点，继续与剩余的路径节点顺序相连，判断是否经过障碍物，直到找到目标点。生成的关键点序列就是最终路径节点。
12.优选地，所述改进dwa算法为在传统dwa算法评价函数中增加局部目标点评价函数，并根据局部目标点评价函数值的大小改进障碍物距离评价函数，该局部目标点为最终路径节点。通过改进的评价函数选择最优的轨迹和速度，输出最优路径。
13.优选地，所述的改进a*算法，所述的16邻域搜索为扩展当前栅格节点周围16个不同方向的栅格节点。
14.优选地，所述的改进a*算法，所述改进的a*算法函数包括：f(n)＝k1*g(n)+k2*h
(n)，其中，f(n)是扩展节点的代价值，g(n)是扩展节点与起始节点的实际距离，h(n)是扩展节点距离目标节点的估计距离，采用曼哈顿距离函数进行计算，k1、k2为不同代价函数的权重。
15.优选地，所述的改进a*算法，判断连接的两个路径节点是否经过障碍物的步骤包括：以开始节点的栅格中心为起点，以1/2栅格为步长选取连接线段上的点，当点既在横轴上又在纵轴上时，选段不占据任何栅格；当点在纵轴上时，线段占据该点左右两个栅格；当点在横轴上时，线段占据该点上下两个栅格；当点在栅格内部时，线段占据该栅格。根据线段占据的栅格里是否有障碍物栅格即可判断路径是否经过障碍物。
16.优选地，所述的改进dwa算法，所述局部目标点评价函数为goal_dist(v,w)，表示当前位置距离局部目标点的距离。所述改进的障碍物评价函数为dist(v,w)/((2-goal_dist(v,w))/2)，dist(v,w)为传统的障碍物评价函数。
17.与现有技术相比较，本发明提出的一种无人车在遵循全局路径最优的同时快速朝目标点运动并且能够在动态环境中躲避障碍物的运动规划方法，该方法可以提高路径规划的效率，减少无人车的运动时间，提高机器人避障的稳定性。
附图说明
18.图1为本方法实施的流程图：
19.图2为邻域表示，(a)为八邻域，(b)为十六邻域。
20.图3为路径规划仿真对比：(a)为传统a*算法；(b)为基于关键点提取的改进a*。
21.图4融合算法导航仿真对比：
22.(a)为传统dwa；(b)为基于目标评价函数的改进dwa；c
23.图5实物导航图：(a)为传统方法；(b)为本方法。
24.图6为关键点提取流程。
25.图7为硬件平台构成。
26.图8为实验框架。
27.图9为导航框架ros-navigation。
具体实施方式
28.以下结合附图和实施例对本发明进行详细说明。
29.如图1所示，本发明是一种融合改进a*与改进dwa算法的运动规划方法。在路径规划方面，针对传统a*算法搜索效率低、拐点多、路径冗余的问题，提出了基于路径关键点提取的改进a*算法，扩展传统a*算法的搜索邻域，改进传统a*算法的启发函数，并提出一种路径关键点提取的方法。在轨迹规划方面，针对传统动态窗口法转向频繁和轨迹不平滑的问题，提出了基于目标评价函数优化的改进dwa算法，对该算法的评价函数进行优化，增加目标点距离评价函数，动态调节障碍物距离评价函数的系数。将改进后的a*算法与改进后的dwa算法进行融合，实现无人车的运动规划。
30.一种融合改进a*与改进dwa算法的运动规划方法，该方法包括：
31.载入预定义的栅格地图；
32.基于无人车当前所处位置和所述栅格地图，确定目标点位置，结合改进的a*算法
进行路径规划，生成初始路径节点；
33.基于上述生成的初始路径进行路径关键点提取，生成最终路径节点；
34.根据改进dwa算法生成最优的轨迹和速度，输出最优路径。
35.所述栅格地图分辨率为1m，栅格地图尺寸为a*b，其中a、b分别表示栅格地图中每行、每列的栅格的个数；每个栅格表示一种区域，包括可行区域和不可行区域。
36.所述初始路径节点的规划过程包括：确定所述无人车所处当前位置与目标点，扩展传统a*算法的搜索邻域为16邻域，并将启发函数改为曼哈顿距离函数，生成代价函数值最小的无碰撞路径节点。
37.所述最终路径节点的规划过程包括：根据生成的初始路径节点，起始点加入关键节点序列，从起始点开始按顺序连接路径节点，直到连接的路径线段经过障碍物，那么选取该节点的上一个路径节点加入关键点序列，此路径节点作为新的起始点，继续与剩余的路径节点顺序相连，判断是否经过障碍物，直到找到目标点；生成的关键点序列就是最终路径节点。
38.所述改进dwa算法为在传统dwa算法评价函数中增加局部目标点评价函数，并根据局部目标点评价函数值的大小改进障碍物距离评价函数，该局部目标点为最终路径节点；通过改进的评价函数选择最优的轨迹和速度，输出最优路径。
39.所述的16邻域搜索为扩展当前栅格节点周围16个不同方向的栅格节点。
40.所述改进的a*算法函数包括：f(n)＝k1*g(n)+k2*h(n)，其中，f(n)是扩展节点的代价值，g(n)是扩展节点与起始节点的实际距离，h(n)是扩展节点距离目标节点的估计距离，采用曼哈顿距离函数进行计算，k1、k2为不同代价函数的权重。
41.判断连接的两个路径节点是否经过障碍物的步骤包括：以开始节点的栅格中心为起点，以1/2栅格为步长选取连接线段上的点，当点既在横轴上又在纵轴上时，选段不占据任何栅格；当点在纵轴上时，线段占据该点左右两个栅格；当点在横轴上时，线段占据该点上下两个栅格；当点在栅格内部时，线段占据该栅格；根据线段占据的栅格里是否有障碍物栅格即可判断路径是否经过障碍物。
42.所述局部目标点评价函数为goal_dist(v,w)，表示当前位置距离局部目标点的距离；所述改进的障碍物评价函数为dist(v,w)/((2-goal_dist(v,w))/2)，dist(v,w)为障碍物评价函数。
43.本发明提出了一种无人车在遵循全局路径最优的同时快速朝目标点运动并且能够在动态环境中躲避障碍物的运动规划方法，该方法可以提高路径规划的效率，减少无人车的运动时间，提高机器人避障的稳定性。
44.如图2所示，a*算法的搜索邻域由8邻域优化为16邻域，扩展了节点搜索的角度，使得搜索时间更短，路径更短，拐点更少。
45.不同栅格地图下四种邻域搜索方法对比
46.47.启发函数改进：
48.传统启发函数：
49.改进启发函数：h(n)＝w1*|x
g-xn|+w2*|y
g-yn|
50.不同栅格地图下启发函数改进前后对比
51.关键点提取流程如图6所示。
52.传统a*算法与优化后的a*算法结果对比
[0053][0054]
融合算法：
[0055]
实验一：静态环境
[0056][0057]
实验二：未知静态障碍物环境
[0058][0059]
实验三：动态未知障碍物环境
[0060][0061][0062]
硬件平台构成如图7所示。
[0063]
实验框架如图8所示。
[0064]
导航框架ros-navigation如图9所示。
[0065]
在导航开始前，需要使用激光雷达进行建图。本文选取了cartographer算法建立二维栅格地图，作为导航的地图输入。在导航过程中，使用自适应的蒙特卡洛定位(amcl)算法给机器人精确定位，提高导航的准确度。使用ros-navigation导航框架实现机器人的自主导航。首先在系统自带的可视化工具rviz上确定一个目标点，全局路径规划器会根据发布的目标点和已知的起点以及地图的已知信息规划出一条无碰撞的最优路径，局部规划器接收到该路径后，根据速度采样结果规划出局部轨迹以及此时机器人需要行进的速度，将计算出的线速度和角速度发送给底层控制器。此后根据机器人当前位置和规划频率不断进行全局路径规划和局部路径规划直到到达目标点为止，即完成了一次自主导航实验。
[0066]
实验一：1)室内静态导航
[0067][0068]
2)室内动态导航
[0069][0070]
实验二：1)室外静态导航
[0071][0072]
2)室外动态导航
[0073]

技术特征：
1.一种融合改进a*与改进dwa算法的运动规划方法，其特征在于，该方法包括：载入预定义的栅格地图；基于无人车当前所处位置和所述栅格地图，确定目标点位置，结合改进的a*算法进行路径规划，生成初始路径节点；基于上述生成的初始路径进行路径关键点提取，生成最终路径节点；根据改进dwa算法生成最优的轨迹和速度，输出最优路径。2.根据权利要求1所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述栅格地图分辨率为1m，栅格地图尺寸为a*b，其中a、b分别表示栅格地图中每行、每列的栅格的个数；每个栅格表示一种区域，包括可行区域和不可行区域。3.根据权利要求1所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述初始路径节点的规划过程包括：确定所述无人车所处当前位置与目标点，扩展传统a*算法的搜索邻域为16邻域，并将启发函数改为曼哈顿距离函数，生成代价函数值最小的无碰撞路径节点。4.根据权利要求1所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述最终路径节点的规划过程包括：根据生成的初始路径节点，起始点加入关键节点序列，从起始点开始按顺序连接路径节点，直到连接的路径线段经过障碍物，那么选取该节点的上一个路径节点加入关键点序列，此路径节点作为新的起始点，继续与剩余的路径节点顺序相连，判断是否经过障碍物，直到找到目标点；生成的关键点序列就是最终路径节点。5.根据权利要求1所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述改进dwa算法为在传统dwa算法评价函数中增加局部目标点评价函数，并根据局部目标点评价函数值的大小改进障碍物距离评价函数，该局部目标点为最终路径节点；通过改进的评价函数选择最优的轨迹和速度，输出最优路径。6.根据权利要求3所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述的16邻域搜索为扩展当前栅格节点周围16个不同方向的栅格节点。7.根据权利要求3所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述改进的a*算法函数包括：f(n)＝k1*g(n)+k2*h(n)，其中，f(n)是扩展节点的代价值，g(n)是扩展节点与起始节点的实际距离，h(n)是扩展节点距离目标节点的估计距离，采用曼哈顿距离函数进行计算，k1、k2为不同代价函数的权重。8.根据权利要求4所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，判断连接的两个路径节点是否经过障碍物的步骤包括：以开始节点的栅格中心为起点，以1/2栅格为步长选取连接线段上的点，当点既在横轴上又在纵轴上时，选段不占据任何栅格；当点在纵轴上时，线段占据该点左右两个栅格；当点在横轴上时，线段占据该点上下两个栅格；当点在栅格内部时，线段占据该栅格；根据线段占据的栅格里是否有障碍物栅格即可判断路径是否经过障碍物。9.根据权利要求5所述的融合改进a*与改进dwa算法的运动规划方法，其特征在于，所述局部目标点评价函数为goal_dist(v,w)，表示当前位置距离局部目标点的距离；所述改进的障碍物评价函数为dist(v,w)/((2-goal_dist(v,w))/2)，dist(v,w)为障碍物评价函数。

技术总结
本发明公开了一种融合改进A*与改进DWA算法的运动规划方法，在路径规划方面，针对传统A*算法搜索效率低、拐点多、路径冗余的问题，提出了基于路径关键点提取的改进A*算法，扩展传统A*算法的搜索邻域，改进传统A*算法的启发函数，并提出一种路径关键点提取的方法。在轨迹规划方面，针对传统动态窗口法转向频繁和轨迹不平滑的问题，提出了基于目标评价函数优化的改进DWA算法，对该算法的评价函数进行优化，增加目标点距离评价函数，动态调节障碍物距离评价函数的系数。该方法可以提高路径规划的效率，减少无人车的运动时间，提高机器人避障的稳定性。稳定性。稳定性。


技术研发人员：刘梦茜
受保护的技术使用者：北京化工大学
技术研发日：2023.05.25
技术公布日：2023/9/23