一种融合改进的A*与DWA算法的室内移动机器人路径规划方法

摘要

本发明公开了一种融合改进的A*与DWA算法的室内移动机器人路径规划方法，包括：S1，优化传统A*算法的代价函数，将环境信息障碍率Q引入代价函数，改变启发函数H(n)的权重,实现其自适应调整；S2，路径平滑的优化，利用一种关键点选取策略，解决冗余的共线节点和转折点的问题，保留必要的路径节点，得到只具有关键点的全局路径；S3，构造结合关键点信息的评价函数，然后应用DWA算法，使局部路径规划遵循全局路径轮廓，从而使路径更加平滑，并实现实时避障。本发明能快速找到最优路径，且在全局最优的基础上，又能及时躲避环境中出现的动静态障碍物，提高室内移动机器人在复杂环境中的适应能力。

说明书

技术领域

本发明涉及移动机器人导航和路径规划领域，具体涉及一种融合改进的A*与DWA算法的室内移动机器人路径规划方法。

背景技术

目前，路径规划是当前移动机器人研究领域的前沿课题之一，其目的是在复杂的环境中避开障碍物，寻找一条从起点到终点的最佳路径。路径规划技术也是移动机器人实现自主导航功能的核心技术。为解决路径规划问题，大量的国内外学者对此课题进行研究，并提出了各种算法。

路径规划可以分为全局路径规划与局部路径规划两大类，其中，全局路径算法有A*算法、Dijkstra算法和RRT算法等；局部路径算法有DWA算法、粒子群算法、人工势场法和蚁群算法等。

Dijkstra算法采用遍历搜索方式，规划节点数较多，节点网络非常庞大且算法效率低下。在Dijkstra算法的基础上，A*算法引入目标点到当前点的估计代价，根据估计代价决定路径搜索方向，提高了算法效率。A*算法在已知环境下能快速实现移动机器人无碰、最短全局路径规划，主要通过节点状态检测和简单的估值功能规划出一条最佳的安全道路。但A*算法规划的路径通过节点连接，导致曲率不连续，存在路径冗长的缺点。赵晓等提出了一种基于跳点搜索算法的改进A*算法，提高了路径的搜索速度，减少了计算量。Zhang等提出了一种改进A*算法，遍历路径的所有节点，然后删除不必要的节点，减短了机器人的行驶路径和转弯时间。然而，这些改进A*算法仅考虑了全局路径的优化，机器人却不能避开未知障碍物。

而对于局部路径规划算法，DWA算法具有很好的局部避障能力。王永雄等提出了参数自适应的DWA算法，获得了机器人运动的最佳速度，并提高了安全性。Mai等提出了一种能够提前感知密集物体分布情况的改进DWA算法，可以使机器人稳定地避开密集区域。然而，改进DWA算法在实现机器人避障的同时，却无法做到全局路径最优。

以上改进算法均只考虑了移动机器人导航过程中的全局路径最优或者局部避障。因此，如何使机器人在导航过程中找到最优路径且能实时避障，一直是个本技术领域人员需要解决的问题。

发明内容

本发明的目的是针对上述问题，为实现移动机器人既能以全局最优路径行驶，又能够实时避开障碍物，提出了一种融合改进的A*与DWA算法的室内移动机器人路径规划方法。该算法将传统A*算法的启发函数中引入环境信息，提高了搜索效率；删除轨迹中冗余节点、减少转折，实现路径平滑度的优化；提取改进A*算法规划路径的关键点作为DWA算法的中间目标点做全局引导，实现改进的A*与DWA算法融合。

本发明采取的技术方案为：一种融合改进的A*与DWA算法的室内移动机器人路径规划方法，具体包括以下步骤：

S1：优化传统A*算法的代价函数，将环境信息障碍率Q引入代价函数，改变启发函数H(n)的权重,实现其自适应调整；

S2：路径平滑的优化，利用一种关键点选取策略，解决冗余的共线节点和转折点的问题，保留必要的路径节点，得到只具有关键点的全局路径；

S3：构造结合关键点信息的评价函数，然后应用DWA算法，使局部路径规划遵循全局路径轮廓，从而使路径更加平滑，并实现实时避障。

作为优选，所述步骤S1优化传统A*算法的代价函数，具体包括在代价函数F(n)中引入随着移动机器人的当前位置变化而变化的环境障碍率Q。假设机器人的起始点与目标点组成的矩形栅格数为M，当前节点到目标点搜索范围内的栅格障碍数为N，环境障碍率表达式为：

作为优选，所述步骤S2路径平滑的优化，传统A*算法路径规划是由连续栅格中心点连接组成，存在许多冗余的节点，路径转折次数多，路径不平滑。针对这些问题，基于Floyd算法思想设计路径平滑优化算法。具体包括以下几步：第一步：遍历所有的节点，删除每一段路径中间的冗余节点，保留起始点和拐点。第二步：遍历起始点和拐点，从起点开始将每一个节点都与后面的节点相连作为备选路径，判断每条路径与障碍物栅格的距离d

作为优选，所述步骤S3改进的A*算法与DWA算法的融合，步骤S1和S2实现对A*算法的改进，得到了只包含起始点、关键点和目标点的导航路径，但无法避开环境中出现的未知障碍物。DWA算法具有良好的局部避障能力，但只有一个最终目标点作为指引，容易陷入局部最优。因此，本发明将两种算法相融合，以提取的改进A*算法规划的全局路径关键点作为DWA算法的中间目标点，优化后的评价函数使得局部路径规划遵循已规划的全局路径轮廓。通过融合导航算法，以实现移动机器人导航过程中的全局路径最优，同时兼具实时避障功能。

本发明的有益效果：

1、优化传统A*算法的代价函数，实现其自适应调整，提高算法效率；

2、解决冗余的共线节点和转折点的问题，保留必要的路径节点，得到只具有关键点的全局路径，实现路径平滑的优化；

3、与DWA算法融合，构造结合关键点信息的评价函数，然后应用DWA算法，使局部路径规划遵循全局路径轮廓，从而使路径更加平滑，并实现实时避障。

附图说明

图1为移动机器人路径规划的A*算法搜索示意图；

图2为移动机器人路径规划时当前点选择下一点时的寻找步骤示意图；

图3为本发明实施例的室内移动机器人路径规划方法流程图；

图4a为本发明实施例的路径平滑优化前示意图；

图4b为本发明实施例的路径平滑优化后示意图；

图5为本发明实施例的融合算法流程图。

具体实施方式

下面结合附图和具体实施方式对本发明做进一步说明。

为本发明的技术方案能得到充分的理解，现对A*算法简要介绍如下：

传统的A*算法搜索原理是将起始点加入到open列表，将该点作为父节点加close列表，搜索其相邻的可到达节点加人open列表。依据代价函数计算open列表中节点的代价，选取代价最低的节点作为下一个父节点并放入close列表，再次搜索父节点可到达节点并计算其代价，依次循环，直到父节点为目标点的位置。

传统A*算法的代价函数为：F(n)＝G(n)+H(n)。式中，n代表当前节点，F(n)表示的是移动机器人在当前节点的代价函数，用来选取最优路径。G(n)代表移动机器人从起始点到当前点的实际代价值。H(n)为启发函数，代表从当前点n到目标点的估计代价值。一般情况下，H(n)小于从当前点n到目标点的实际代价值，当H(n)值为0时，此时只有G(n)起作用，算法即为Dijkstra算法。H(n)的估计值比实际代价值小时，算法搜索时间会因搜索空间的增大而增加。H(n)估计值比实际代价值大时，算法搜索速度会增加，但是算法可能无法搜索到最短路径。

不难看出H(n)对于搜索效率有很大的影响，H(n)有几种常见的表现形式：(1)曼哈顿距离；(2)切比雪夫距离；(3)欧几里得距离。本发明的一具体实施例采用的是曼哈顿距离。

如图1所示，为搜索区域，其中黑色格子为障碍物节点，白色格子为可走节点。图2为当前点选择下一点时的寻找步骤，假设设直线代价为10，斜线代价为14，如图2所示，右下角的代价函数最小，故下一节点为右下角节点，以此类推，如果碰到障碍物，则不将障碍物作为考虑范围之内。直到最后的到达目标点停止，获得最短路径，如图1所示，折线连接的路径代表寻找到的最短路径。

本发明的一种融合改进的A*与DWA算法的室内移动机器人路径规划方法，其核心在于对A*算法的改进及融合A*与DWA算法。以下实施例用于说明本发明，但不用来限制本发明的范围。

如图3所示，本实施例所述的室内移动机器人路径规划方法的流程示意图，具体包括：S1，优化传统A*算法的代价函数，将环境信息障碍率Q引入代价函数，改变启发函数H(n)的权重,实现其自适应调整；S2，路径平滑的优化，利用一种关键点选取策略，解决冗余的共线节点和转折点的问题，保留必要的路径节点，得到只具有关键点的全局路径；S3，构造结合关键点信息的评价函数，然后应用DWA算法，使局部路径规划遵循全局路径轮廓，从而使路径更加平滑，并实现实时避障。

S1，优化传统A*算法的代价函数，将环境信息障碍率Q引入代价函数，改变启发函数H(n)的权重,实现其自适应调整。

当前节点离目标点较远时，估计代价值远小于实际值，此时搜索空间大，搜索节点较多，应适当增大H(n)的权重，提高搜索效率；当前节点逐渐靠近目标点时，估计代价值也随之增大，接近实际值，为防止估计值较大而陷入局部最优，应适当减小H(n)的权重。因此，为了自适应调整启发函数的权重，引入随着移动机器人的当前位置变化而变化的环境障碍率Q。

通过引入环境障碍率Q，对传统的A*算法的代价函数进行优化。环境障碍率表达式为：

此时的代价函数F(n)优化为F(n)＝G(n)+e

S2，路径平滑的优化，利用一种关键点选取策略，解决冗余的共线节点和转折点的问题，保留必要的路径节点，得到只具有关键点的全局路径。

传统A*算法路径规划是由连续栅格中心点连接组成，存在许多冗余节点，路径转折次数多，路径不平滑。针对这些问题，基于Floyd算法思想设计路径平滑优化算法。

路径平滑优化原理如图4a和4b所示，以此为例，传统A*算法规划的路径规划由栅格中心点的连线组成，优化前的路径为(S，1，2，…，13，E)，存在许多冗余节点。在考虑安全距离D的基础上，对路径进行平滑优化，使得路径的选择不再局限于过栅格的中心位置。优化后的路径平滑度增加，路径长度和转折点减少，路径平滑优化步骤如下：

步骤1：遍历所有的节点，删除每一段路径中间的冗余节点，保留起始点和拐点。删除中间点后剩下S，2，6，8，9，10，11，13，E九个节点。

步骤2：遍历起始点和拐点，从起点开始将每一个节点都与后面的节点相连作为备选路径，判断每条路径与障碍物栅格的距离d

步骤3：提取剩余的节点，输出优化路径，算法结束。

S3，构造结合关键点信息的评价函数，然后应用DWA算法，使局部路径规划遵循全局路径轮廓，从而使路径更加平滑，并实现实时避障。

改进A*算法得到了只包含起始点、关键点和目标点的导航路径，但无法避开环境中出现的未知障碍物。DWA算法具有良好的局部避障能力，但只有一个最终目标点作为指引，容易陷入局部最优。因此，本发明将两种算法相融合，以提取的改进A*算法规划的全局路径关键点作为DWA算法的中间目标点，优化后的评价函数使得局部路径规划遵循已规划的全局路径轮廓。通过融合导航算法，以实现移动机器人导航过程中的全局路径最优，同时兼具实时避障功能。

融合算法的具体流程如图5所示。首先，采用改进A*算法规划出一条全局路径，利用其优化的评价函数以及关键点选取策略对路径进行优化，并得到路径必要的关键节点。然后，以提取的路径关键点作为DWA算法的中间目标点，指引局部路径的规划。DWA算法对移动机器人的速度进行采样，并模拟出各速度对的移动轨迹，利用结合关键点信息的评价函数选取出最优的模拟移动轨迹，并以最优轨迹对应的速度控制机器人向目标点的移动，从而实现改进A*算法和DWA算法的融合。

上述对实施例的描述是为便于本技术领域的普通技术人员能理解和应用本发明。所属领域的普通技术人员依然可以对本发明的具体实施方式进行修改或者等同替换，而未脱离本发明精神和范围的任何修改或者等同替换，其均应涵盖在本发明的权利要求范围当中。