一种基于混合智能算法的移动机器人路径规划方法

1.本发明涉及机器人路径规划技术领域，尤其涉及一种基于混合智能算法的移动机器人路径规划方法。


背景技术：

2.随着自动化技术的发展，移动机器人已广泛应用于各个领域，如物流、医疗、服务等。在移动机器人的应用过程中，路径规划是一个非常重要的问题，常常需要考虑多种因素，如机器人的运动约束、环境的障碍物分布以及路径的长度和安全性等等。因此，单独使用某一种路径规划算法往往难以满足实际需求。
3.a-star算法是一种高效的搜索算法，可以找到最短路径。然而，规划的路径与障碍物顶点相交，安全性低，同时路径拐点多，不够平滑。dwa算法是一种考虑了机器人动力学和环境约束的路径规划算法，能够在保证机器人安全的前提下，寻找一条可行的路径。但是，dwa算法的搜索范围较窄，无法找到全局最优解，并且运行时间较长。


技术实现要素：

4.有鉴于此，本发明的目的在于提出一种基于混合智能算法的移动机器人路径规划方法，以解决现有算法的路径规划不够平滑，效率不足的问题。
5.基于上述目的，本发明提供了一种基于混合智能算法的移动机器人路径规划方法，包括以下步骤：s1、在标准a-star算法的评价函数中加入安全阈值函数，并在a-star算法中增加冗余节点剔除策略和路径平滑处理，得到改进a-star算法，使用改进a-star算法作为全局路径规划算法，得到全局最优路径；s2、在标准dwa算法的评价函数中增加曲率评价子函数和目标点距离函数，并依据与局部环境内所有障碍物的最短距离自适应调整速度评价函数权重系数，得到新的权重系数，得到改进dwa算法，使用改进dwa算法作为局部路径规划算法，得到局部最优路径；s3、在改进a-star算法生成的全局最优路径中选取局部目标点，为移动机器人运动提供指引；s4、选取最优模拟轨迹运行；s5、判断移动机器人是否运动到目标点，若否，则返回运行步骤s3和s4。
6.优选地，安全阈值函数用于根据安全阈值系数和当前节点距离最近障碍物的距离，评价安全阈值，其中障碍栅格由采用栅格法将地图等分得到，定义不与障碍栅格有任何相交的独立自由栅格的安全阈值系数为零。
7.优选地，冗余节点剔除策略包括：s11、剔除每一段路径中间的冗余节点，保留起始点，拐点和目标点；s12、从起点开始依次往后面的节点连线，进行节点连线与栅格障碍相交检测，若和当前节点的连线与障碍相交，保留当前节点的前一节点，该节点为下次往后连线的起点，
删除中间节点；s13、重复执行步骤s12，直至与目标点连线且不与障碍相交，输出优化后路径，策略结束。
8.优选地，路径平滑处理包括：使用基于三阶b样条曲线的平滑方法，通过在给定的数据点之间拟合一条连续的曲线得到平滑处理后的路径。
9.优选地，b样条曲线数学表达式为：；式中，为b样条曲线第i个控制点，n为控制点数量减去1，t为定义域内的参数，为第i个k阶b样条基函数，是对阶b样条基函数的线性组合，由递归公式计算：；式中，为第i个1阶b样条基函数，为定义域内参数轴上的节点。
10.优选地，曲率评价子函数用于根据机器人运动的角速度和线速度评价机器人运动轨迹在两个时刻间的曲率差。
11.优选地，距离函数用于基于dwa算法产生的模拟轨迹末端店到目标点的欧氏距离，对包含角速度和线速度的速度组进行评价。
12.优选地，得到的所述新的权重系数为：；式中，为标准dwa算法结合运动学模型最短时间通过障碍物密集区域的对应值，为通过狭窄通道且最安全的对应值，为减速阈值距离，与机器人最高线速度成正比，与线加速度成反比，为机器人与局部环境内障碍物的最短距离，为自适应调整的系数。
13.优选地，步骤s3进一步包括：针对步骤s1改进a-star算法输出的平滑曲线，选取曲线拐点处的曲率极大值点，作为改进dwa算法的局部目标点，为机器人运动提供指引。
14.优选地，步骤s5进一步包括：使用改进dwa算法作为移动机器人的运动控制，生成模拟运动轨迹，根据评价函数
选取最优轨迹对应的线速度和角速度作为下一周期的控制指令，机器人运动到最终目标点。
15.本发明的有益效果：（1）本发明提出的改进a-star算法的评价函数，规划出路径与障碍物保持一定距离，安全性提高，同时对路径进行了平滑优化。
16.（2）本发明在dwa算法中增加两个评价子函数，使机器人的运动更加平顺，并减少了机器人远离局部目标点的风险，同时可以根据局部障碍信息自适应调整移动机器人的运行速度，效率大大提升。
17.（3）使用matlab仿真验证了本发明所提的基于混合智能算法的移动机器人路径规划方法的有效性和优越性。
附图说明
18.为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
19.图1为本发明实施的基于混合智能算法路径规划方法流程图；图2为本发明节点连线与障碍相交检测示意图；图3为本发明剔除冗余节点策略示意图；图4为本发明的标准a-star算法和改进a-star算法路径规划仿真图；图5为本发明所使用移动机器人运动学模型；图6为本发明实施的混合算法路径规划仿真图；图7为改进前的融合仿真图；图8为改进前算法路径规划的仿真数据图；图9为本发明的改进后算法路径规划的仿真数据图。
具体实施方式
20.为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，对本发明进一步详细说明。
21.如图1所示，本说明书实施例提供一种基于混合智能算法的移动机器人路径规划算法，包括以下步骤：s1、在标准a-star算法的评价函数中加入安全阈值函数，并在a-star算法中增加冗余节点剔除策略和路径平滑处理，得到改进a-star算法，使用改进a-star算法作为全局路径规划算法，得到全局最优路径；标准a-star算法的评价函数定义为：，式中，n为路径中第n个节点，f(n)为第n个节点的总代价值，用来表示节点n的优先级，f(n)越小节点n优先级越高，g(n)为节点n距离起始点的实际代价值，h(n)为启发函数，表示节点n距离目标点的估计代价值。
22.为了使规划出的路径不会穿过障碍物顶点，与障碍物保持一定距离，提高安全性，在a*的评价函数中加入安全阈值函数，安全阈值函数定义为：；式中，为安全阈值系数（不与障碍栅格有任何相交的独立自由栅格，其安全阈值系数；其余情况），r为当前节点n距离最近障碍物的距离。
23.改进后的评价函数为：。
24.在a-star算法中增加冗余节点剔除策略，删除路径中多余的节点，减少路径转折次数，简化路径，以此来达到优化的目的。
25.节点连线与栅格障碍相交检测方法为：已知节点a、b的坐标信息，如图2所示，ab两点连线，将连线所覆盖的栅格坐标计算出来，遍历所有这些覆盖的栅格，依次检测断栅格是自由栅格还是障碍栅格（判断依据：障碍栅格的逻辑值为1，自由栅格的逻辑值为0），只要检测到一个障碍栅格，则说明连线与障碍发生相交，该路径不可行；若这些栅格全部为自由栅格，则说明连线与障碍不发生相交，该路径可行。
26.剔除冗余节点策略：第一步，剔除每一段路径中间的冗余节点，保留起始点，拐点和目标点。第二步，从起点开始依次往后面的节点连线，进行节点连线与栅格障碍相交检测，若和当前节点的连线与障碍相交，保留当前节点的前一节点，该节点为下次往后连线的起点，删除中间节点。第三步，重复执行第二步，直至与目标点连线且不与障碍相交，输出优化后路径，策略结束。如图3所示，具体实现步骤如下：（1）初始化图4中实线的所有节点；（2）将起始点和目标点加入新路径节点集合；（3）从开始向连线，然后进行上文提到的节点连线与障碍相交检测，线段与障碍未发生相交，往后依次遍历节点，直至检测线段与栅格障碍发生相交，将节点加入集合，剔除冗余节点；同理剔除冗余节点。
27.（4）剔除冗余节点后，构成优化后路径节点集合为，其中只包含了起始点，目标点和路径转折点，算法结束。
28.为了使机器人更好的跟随路径，减少运动中不必要的震荡和抖动，需要对路径做平滑处理。使用一种基于三阶b样条曲线的平滑方法，通过在给定的数据点之间拟合一条连续的曲线来实现。b样条曲线数学表达式定义为：；式中，为b样条曲线第i个控制点，n为控制点数量减去1，t为定义域内的参数，
为第i个k阶b样条基函数，是对阶b样条基函数的线性组合，由递归公式计算：；式中，为第i个1阶b样条基函数，为定义域内参数轴上的节点。
29.图4a为标准a*算法规划的路径，图4b为本发明实施的改进a*算法规划的路径，数据为下表1所示：
30.s2、在标准dwa算法的评价函数中增加曲率评价子函数和目标点距离函数，并依据与局部环境内所有障碍物的最短距离自适应调整速度评价函数权重系数，得到新的权重系数，得到改进dwa算法，使用改进dwa算法作为局部路径规划算法，得到局部最优路径；标准dwa算法的评价函数定义为：；式中，为方向评价函数，为机器人经过前向模拟时间后的运动方向与模拟轨迹末端点和目标点连线之间的夹角，为障碍距离评价函数，表示模拟轨迹到障碍物的最短距离，为速度评价函数，评估当前机器人向目标点的前进速度，为相应函数的权重系数，对评价函数各部分进行归一化处理。
31.移动机器人的运动学模型如图5所示，只考虑机器人的水平运动，为世界坐标系，为机器人本体坐标系，为机器人在世界坐标系中的位姿。在低速运行的情况下，机器人满足阿克曼转向几何的约束，可以用双轮自行车模型来等效替代。选择机器人后轴中心为参考点，为前轮转向角，r为转弯半径，l为机器人轴距，icr为模型瞬时转向中心，参考点围绕icr做圆弧运动。
32.由于机器人在一个极短的采样时间δt内的位移很小，所以在时间[t,t+δt]内机器人可以看作为匀速直线运动，位移近似为一条短直线。对移动机器人进行建模，运动模型的数学表达式为：
；式中，为机器人t时刻在世界坐标系中的位姿，为机器人t+δt时刻在世界坐标系中的位姿，和分别为机器人线速度在水平方向和竖直方向上的分量，为机器人t时刻的角速度。
[0033]
在标准dwa算法中新增两个评价子函数：（1）轨迹曲率可以反映一个机器人运动的平稳性，为了防止机器人出现剧烈抖震的情况，需要将轨迹曲率的约束加入到标准评价函数中。在一段时间内，机器人运动轨迹的曲率与角速度呈正相关，与线速度呈负相关，轨迹曲率越小，表明机器人运动越平顺。新增函数：；（2）新增目标点距离函数，可以减少机器人偏离目标点的风险。该函数计算机器人基于dwa算法产生的模拟轨迹末端点到目标点的欧式距离，来进行对速度组的评分，其中距离计算公式为：；式中，为机器人模拟轨迹末端点的坐标，为目标点的坐标，为起点到目标点的路径距离。
[0034]
权重系数大，机器人的速度快，但是运行会贴近障碍物，安全性低，甚至可能会出现无法运动到目标点，在附近“绕圈”的情况；权重系数小，路径安全性高，但运行速度减缓，影响效率。依据与局部环境内所有障碍物的最短距离自适应调整速度评价函数权重系数，定义新的权重系数为：
；式中，为标准dwa算法结合运动学模型最短时间通过障碍物密集区域的对应值，为通过狭窄通道且最安全的对应值。为减速阈值距离，与机器人最高线速度成正比，与线加速度成反比，为机器人与局部环境内障碍物的最短距离，为自适应调整的系数。
[0035]
s3、在改进a-star算法生成的全局最优路径中选取局部目标点，为移动机器人运动提供指引；具体为：针对步骤s1改进a-star算法输出的平滑曲线，选取曲线拐点处的曲率极大值点，作为改进dwa算法的局部目标点，为机器人运动提供指引。
[0036]
s4、选取最优模拟轨迹运行，一次性拿完所有局部目标点后，会存进一个变量中；s5、判断移动机器人是否运动到目标点，若否，则返回运行步骤s3和s4。
[0037]
步骤s4，s5中，改进dwa算法同时用于移动机器人的运动控制，生成模拟运动轨迹，根据评价函数选取最优轨迹对应的作为下一周期的控制指令，机器人运动到最终目标点，算法结束。
[0038]
图6为本发明实施的混合算法路径规划仿真图，图中实线为实际运动轨迹，虚线为规划路径，图7为改进前的融合仿真图，可以看出与改进a-star算法规划的全局路径差距较大，且运动不够平滑。
[0039]
图8和图9分别为改进前后的算法的仿真数据图，可以看出改进前的数据图，速度抖动较大，改进后的仿真数据图，速度平稳，未出现较大抖动，且步数减少，效率提高。
[0040]
所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本发明的范围（包括权利要求）被限于这些例子；在本发明的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如上所述的本发明的不同方面的许多其它变化，为了简明它们没有在细节中提供。
[0041]
本发明旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、修改和变型。因此，凡在本发明的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种基于混合智能算法的移动机器人路径规划方法，其特征在于，包括以下步骤：s1、在标准a-star算法的评价函数中加入安全阈值函数，并在a-star算法中增加冗余节点剔除策略和路径平滑处理，得到改进a-star算法，使用改进a-star算法作为全局路径规划算法，得到全局最优路径；s2、在标准dwa算法的评价函数中增加曲率评价子函数和目标点距离函数，并依据与局部环境内所有障碍物的最短距离自适应调整速度评价函数权重系数，得到新的权重系数，得到改进dwa算法，使用改进dwa算法作为局部路径规划算法，得到局部最优路径；s3、在改进a-star算法生成的全局最优路径中选取局部目标点，为移动机器人运动提供指引；s4、选取最优模拟轨迹运行；s5、判断移动机器人是否运动到目标点，若否，则返回运行步骤s4；所述路径平滑处理包括：使用基于三阶b样条曲线的平滑方法，通过在给定的数据点之间拟合一条连续的曲线得到平滑处理后的路径；b样条曲线数学表达式为：；式中，为b样条曲线第i个控制点，n为控制点数量减去1，t为定义域内的参数，为第i个k阶b样条基函数，是对阶b样条基函数的线性组合，由递归公式计算：；；式中，为第i个1阶b样条基函数，为定义域内参数轴上的节点。2.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，所述安全阈值函数用于根据安全阈值系数和当前节点距离最近障碍物的距离，评价安全阈值，其中障碍栅格由采用栅格法将地图等分得到，定义不与障碍栅格有任何相交的独立自由栅格的安全阈值系数为零。3.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，所述冗余节点剔除策略包括：s11、剔除每一段路径中间的冗余节点，保留起始点，拐点和目标点；s12、从起点开始依次往后面的节点连线，进行节点连线与栅格障碍相交检测，若和当前节点的连线与障碍相交，保留当前节点的前一节点，该节点为下次往后连线的起点，删除中间节点；s13、重复执行步骤s12，直至与目标点连线且不与障碍相交，输出优化后路径，策略结
束。4.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，所述曲率评价子函数用于根据机器人运动的角速度和线速度评价机器人运动轨迹在两个时刻间的曲率差。5.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，所述目标点距离函数用于基于dwa算法产生的模拟轨迹末端店到目标点的欧氏距离，对包含角速度和线速度的速度组进行评价。6.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，得到的所述新的权重系数为：；式中，为标准dwa算法结合运动学模型最短时间通过障碍物密集区域的对应值，为通过狭窄通道且最安全的对应值，为减速阈值距离，与机器人最高线速度成正比，与线加速度成反比，为机器人与局部环境内障碍物的最短距离，为自适应调整的系数。7.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，步骤s3进一步包括：针对步骤s1改进a-star算法输出的平滑曲线，选取曲线拐点处的曲率极大值点，作为改进dwa算法的局部目标点，为机器人运动提供指引。8.根据权利要求1所述的基于混合智能算法的移动机器人路径规划方法，其特征在于，步骤s5进一步包括：使用改进dwa算法作为移动机器人的运动控制，生成模拟运动轨迹，根据评价函数选取最优轨迹对应的线速度和角速度作为下一周期的控制指令，机器人运动到最终目标点。

技术总结
本发明涉及机器人路径规划技术领域，尤其涉及一种基于混合智能算法的移动机器人路径规划方法，通过结合A-Star算法和DWA算法，在标准A-Star算法的评价函数中加入安全阈值函数，并在A-Star算法中增加冗余节点剔除策略和路径平滑处理，在标准DWA算法的评价函数中增加曲率评价子函数和目标点距离函数，并依据与局部环境内所有障碍物的最短距离自适应调整速度评价函数权重系数，得到新的权重系数，使路径安全性提高，同时对路径进行了平滑优化，同时可以根据局部障碍信息自适应调整移动机器人的运行速度，效率大大提升。效率大大提升。效率大大提升。


技术研发人员：何舒平 周锟 张良 邓京辉 宋军 余涛
受保护的技术使用者：安徽大学
技术研发日：2023.07.11
技术公布日：2023/8/9