基于改进A的全局动态路径规划方法研究∗ 算法 翻译+总结_a*全局路径规划算法经典论文

针对智能驾驶全局路径规划的最优路径和规划效率问题，提出了一种基于改进a∗ 算法。首先，该方法改进了传统A的启发式功能∗ 提高全局路径规划效率的算法。其次，该方法采用路径优化策略，使全局路径更加平滑。㼿ird，该方法与动态窗口方法相结合，以提高智能车辆动态避障的实时性。最后，提出了一种改进的全局动态路径规划方法∗ 通过仿真实验和实车试验对算法进行了验证。在仿真分析中，与改进的A∗ 算法与传统的A∗ 算法中，本文的方法将路径距离缩短了2.5%∼3.0%，提高效率10.3%∼13.6%，生成更平滑的路径。在实车试验中，车辆可以实时避开动态障碍物。㼿因此，本文提出的方法可以应用于智能车辆平台。㼿e路径规划效率高，动态避障实时性好。

1.导言

智能驾驶作为未来汽车的发展方向之一，正受到越来越多的关注[1]。特别是，路径规划是智能驾驶的重要组成部分。路径规划是智能车辆基于环境信息规划的从起点到目标点的无障碍路径[2]。特别是在动态环境下，为了保证实时避障和路径规划的效率，有必要对路径规划算法进行改进。

         近年来，该领域最具代表性和最常见的路径规划算法主要分为神经网络算法[3]、人工势场算法[4]、快速扩展随机树算法[5]、蚁群算法[6]和∗ 算法[7,8]。特别是A∗ 算法是一种启发式搜索算法；由于其强大的全局搜索能力、较高的搜索效率和最短路径，被广泛应用。Ziang Zhang等人[9]提出了一种改进的方法基于单摆的球形移动机器人混合路径规划方法提高了路径搜索的效率，但它是针对球形移动机器人的。Bijun Tang等人[10]提出了一种算法，该算法使用人工势场方法来优化混合A的路径∗ 算法。㼿生成的路径不仅平滑，而且与障碍物保持安全距离。然而，在动态环境中，实时避障效果并不理想。Oleiwi等人[11]提出了一种基于蚁群算法和遗传算法的多目标移动机器人路径规划方法，该方法可以在静态环境中有效地为多目标选择最优路径，但不适用于动态环境。王继凯等[12]提出了一种基于混合映射的全局路径规划框架，提高了复杂环境下路径规划的效率，但不能保证最优路径。宋晓如等[13]提出了一种适用于移动机器人的动态全局路径规划方法，该方法可以在动态环境中规划出平滑的路径，但路径规划的效率较低规划仍需改进。㼿e A∗ 基于栅格地图的算法适用于全局路径规划。㼿is算法具有结构简单、计算量小等优点[14]。然而，传统的∗ 该算法存在多个折叠点，不利于智能车辆的驾驶。此外，如果环境空间增加，则∗ 该算法存储空间大，效率低，实时性差。㼿e动态窗口法在动态环境中具有良好的避障能力，但不适用于全局路径规划[15]。

    针对智能驾驶全局路径规划的最优路径和规划效率问题，提出了一种基于改进a∗ 算法和动态窗口方法。㼿改进的路径规划方法具有许多优点。首先，传统A的启发式功能∗ 对算法进行了改进，使得∗ 路径搜索更加偏颇。㼿减少了路径规划的时间，提高了效率。㼿恩，优化策略用于减少路径规划中的冗余转折点和节点。㼿优化了路径的距离，提高了路径的平滑度。最后，A∗ 算法全局搜索能力与动态窗口法局部规划能力相结合，使智能车辆能够进行全局动态路径规划，动态避障的实时性好。㼿本文的剩余部分组织如下：第2节讨论了改进的A∗ 算法；第3节讨论了动态窗口方法；第四节讨论了模拟和实验结果；第5节讨论了实车试验；第6节讨论了本研究的结论。

2.改进的A∗ 算法

传统的A∗ 算法是一种启发式搜索算法，它不断扩展节点并计算每个节点的值。最后，我们可以找到一条最小值的路径。㼿使用启发式函数可以大大提高搜索效率。传统的e公式A∗ 算法如下所示：

     其中f（n）是从初始节点到目标节点的估计值，g（n）是从初始节点到状态n的节点的实际值，h（n）是从状态n的节点到目标节点的估计值。㼿h（n）的选择直接影响算法的性能。只有当h（n）的值更接近状态n节点到目标节点的实际代价值时，才能保证最优路径，提高算法的效率。㼿因此，进行了以下改进。

2.1. .改进的启发式函数h(n)。.

假设d（n）是从状态n的节点到目标节点的实际值。当以不同方式选择启发式函数h（n）时，将出现以下三种情况：

 式中（Mx、My)表示当前节点的坐标值，（Gx、Gy)表示目标节点的坐标值，D为移动一个网格的智能车辆的实际成本值。为了使启发式函数h(n)更接近实际值d(n)，利用曼哈顿距离和切比雪夫距离设计了一种新的启发式函数。e，然后对启发式函数进行动态加权：

 其中，m(n)为搜索深度，R为期望路径长度，K为常数。其他参数与公式（2）-（4）相同。

2.2.路径优化策略。

e传统的∗算法基于网格对节点进行扩展，包含更多的转折点和冗余节点[18]ey不擅长驾驶智能汽车。为了解决这些问题，本文提出了一种路径优化策略:

（1）查找冗余的节点并移除它们。假设由A∗算法规划的路径是.首先，从路径规划的第二个节点M2开始，判断M2的子节点M3与其父节点M1是否在同一直线上。如果它在同一条直线上，则M2为冗余节点。删除并更新路径列表。然后，检查下一个节点的子节点及其父节点是否在同一行上。删除冗余节点，并更新路径列表。最后，遍历所有节点，得到一组点，包括起点、转折点和目标点。

（2）寻找冗余的转折点并删除它们。假设A∗算法规划的路径为.策略（1）经过优化后，除了起点M1和目标点Mn外，其他节点都是转折点。首先，连接节点M1M3。如果直线M1M3未通过该障碍物，且距离最近障碍物的距离大于设定的安全距离，则M2为冗余转折点，删除M2。在连接 ，并重复上述检查步骤。如果M1Mk通过一个障碍物或距离最近障碍物的距离小于安全距离，则删除节点Mk−2，并连接节点M1Mk−1。更新路径列表并连接节点。最后，重复上述检查步骤，直到遍历所有节点为止。

 3.动态窗口方法

    .   动态窗口法可以使智能车辆在动态环境中具有良好的避障能力。e动态窗口法主要用于对速度空间和速度空间中的多个组速度(线速度v和角速度w)进行采样，模拟智能车辆在下一个时间间隔内的轨迹。在获得多组轨迹后，根据评估函数[19]对多组轨迹进行评估，智能车辆选择最优轨迹对应的速度进行下一步驾驶[20]。

3.1.车辆运动学模型。

     根据动态窗口法，它可以在一段时间内连续模拟智能车辆的运动轨迹。因此，有必要了解智能车辆[21,22]的运动学模型。轨迹用(_xt，_yt)表示。运动学模型如图1所示。

    利用动力学的基本定律，我们可以得到动力学公式：

 式中(_xt、_yt)为智能车辆在t时刻坐标轴上的投影速度，v为智能车辆的速度，θt为t时刻的姿态角，θ_t为t时刻的姿态角速度，L为智能车辆的轴距，ϕt为t时刻的前轮角，ρ为转弯半径。

在实际应用中，考虑到智能车辆的全向运动和世界坐标系的变换，得到了新的运动学公式：

 3.2.速度采样系统的设计。

在建立了智能车辆的运动学模型后，可以根据其速度(线速度v和角速度w)计算出运动轨迹。然而，在速度空间中有无限个的速度组。为了更好地控制速度采样，必须根据智能车辆和环境空间的限制，将速度组限制在一定的控制范围内。

(1) .e智能车辆的直线速度及其角速度极限范围公式如下：

 （2）在实际应用中，电机必须经过一定的时间间隔，使智能车辆达到相应的速度，在电机扭矩的影响下速度在动态范围内。因此，计算公式如下：

 其中vd和ωd为智能车辆v_c和v_e当前的前线速度和角速度分别为线速度的最大加速度和减速，_ωc和_ωe分别为角速度的最大加速度和减速。

(3)在智能车辆的运行过程中，当在安全距离内检测到障碍物时，智能车辆需要减速甚至停车。因此，有必要进一步限制速度（线速度和角速度)

 其中，dist(vt，ωt)为智能车辆的当前位置与最近的障碍物之间的距离。

3.3.动态窗口评价功能的设计

根据动态窗口法，我们需要一个适当的评价函数来从最终规划的多个轨迹中选择最优轨迹。e评价功能的优先级标准是使智能车辆避开障碍物，向轨道最短的目标移动。e公式显示如下：

 式中，头部(vt，ωt)为机器人在t时刻的采样速度，dist(vt，ωt)为机器人在t时刻的轨迹与最近的障碍物之间的距离，速度(vt，ωt)为机器人在t时刻的速度。

3.4.算法的流程图。e该算法的流程图如图2所示。

步骤1：地图初始化和改进的∗算法进行全局路径规划

步骤2：计划路径的策略优化

步骤3：建立运动学模型，和速度组采样

步骤4：根据规划全局路径和多个轨迹模拟的速度，选择最优轨迹使用评价函数

步骤5：建立最优路径

 4.仿真实验与分析

    为了验证本文设计的融合算法的有效性，采用MATLAB2019b进行仿真实验，构建一个网格地图场景（20米×20米，网格间距1米），同时放置7个不同形状和大小的静态障碍和两个动态障碍。在模拟实验建立的网格图中，起点坐标为(1.5m、1.5m)，目标点坐标为(19.5m、19.5m)

4.1.改进的启发式函数的仿真实验。

.e传统的∗算法具有大量冗余节点，搜索范围大，降低了算法的效率。本文改进了A∗算法，减少了搜索范围，提高了搜索效率算法黑色为初始位置，绿色为目标位置，红色为最优路径，黄色为除最优路径外的搜索区域。e实验结果如图3所示。

.e本文改进的∗算法的实验图像如图3(a).所示。e搜索面积为128m2，路径长度为28.38m，时间为0.040s。

.e传统A∗算法的实验图像如图3(b).所示。e搜索面积为180m2，路径长度为28.38m，时间为0.050s。

.e利用曼哈顿距离和欧几里德距离改进的A∗算法的实验图像如图3(c).所示为了区分，它被命名为改进的A∗算法e搜索面积为166m2，路径长度为28.38m，时间为0.045s。

.e详细数据见表1。

 从以上数据来看，与传统的A∗算法相比，本文改进的A∗算法可以减少28.9%的搜索面积，提高0.20%的效率。与改进的A∗算法相比，本文改进的A∗算法可以减少22.9%的搜索面积，提高11.1%的搜索效率。

4.2.静态全局路径规划。

.在静态仿真环境下，本节将比较基于不同算法的仿真实验结果。e本文的仿真实验是在相同的环境下，智能车辆的最大速度和加速度是相同的，红线为智能车辆的实际轨迹。

工作条件1：传统的A-∗算法的实验图像如图4(a).所示图中的每个圆圈代表一个节点，各种多边形都是障碍环境。从仿真实验结果可知，该算法具有许多冗余节点和转折点，最优路径节点数为24个，转折点数为7个，共扩展了180个节点。e搜索路径长度为28.38m，时间为0.050s。

工作条件2：修改后的A∗算法的实验图像如图4(b).中的蓝线所示图中的每个圆圈代表一个节点，各种多边形都是障碍环境。经仿真实验结果表明，该算法的最优路径节点数为4个，转折点数为2个，共扩展了166个节点。e搜索路径的长度为27.50m，时间为0.045s。

工作条件3：改进后的A∗算法和动态窗口方法的实验图像如图4(b).中的红线所示图中的每个圆圈代表一个节点，各种多边形都是障碍环境。根据仿真实验结果，该算法规划的轨迹平滑，最优路径长度为28.56m，时间为51.31s。'

工作条件4：本文改进的A∗算法的实验图像如图4(c).中的蓝线所示图中的每个圆圈代表一个节点，各种多边形都是障碍环境。根据仿真实验结果，该算法的最优路径节点数算法为4，转折点数为2，共扩展了128个节点。e该算法的最优路径长度为26.99m，时间为0.04s。

工作条件5：本文改进的A∗算法和动态窗口方法的实验图像如图4(c).中的红线所示图中的每个圆圈代表一个节点，各种多边形都是障碍环境。根据仿真实验结果，该算法规划的路径平滑，最优路径长度为27.13m，时间为46.69s。详细的统计数据见表2和表3。

  4.3.动态全局路径规划

在动态仿真环境下，本节将比较基于不同算法的仿真实验。e本文的仿真实验是在相同的环境下，智能车辆的最大速度和加速度是相同的，红线为智能车辆的实际轨迹。

工作条件1：传统的A-∗算法和动态窗口方法的实验图像如图5所示。e图显示了不同时刻的动态避障情况。各种多边形都是障碍的环境。仿真实验结果表明，该算法的最优路径长度为29.63m，总时间为54.77s。

工作条件2：改进后的A∗算法和动态窗口方法的实验图像如图6所示。e图显示了不同时刻的动态避障情况。各种多边形都是障碍的环境。仿真实验结果表明，该算法的最优路径长度为29.48m，总时间为52.75s。

工作条件3：本文使用改进的A∗算法和动态窗口方法进行的实验图像如图7所示。e图显示了不同时刻的动态避障情况。各种多边形都是障碍的环境。根据仿真结果详细的统计数据见表3。

4.4.仿真实验结果及分析。

在静态障碍物环境下，与改进的A∗算法和动态窗口算法相比，本文改进的A∗算法和动态窗口算法将路径距离缩短了5.0%，时间缩短了9.0%。

在动态障碍环境下，与改进的A∗算法和动态窗口算法相比，本文改进的A∗算法和动态窗口算法将路径距离减少了2.5%，时间减少了10.3%。与传统的A∗算法和动态窗口算法相比，本文提出的算法的路径距离减少了3.0%，时间减少了13.6%

.因此，本文提出的算法效率更高。e规划路径更短、顺畅，有利于智能车辆的驾驶

5.真实车辆测试

本文采用基于Linux系统的无人驾驶测试车，对改进的∗路径规划算法进行了验证e平台支持完全独立开发，配备16线激光雷达、毫米波雷达、双目视觉模块、GPS定位模块等设备，具有高精度定位、自动导航和跟踪功能。e实际车辆如图8所示。。。。。。e静态障碍是一个纸箱，动态障碍是一个测试仪。为保证安全，测试车辆配备了一名负责紧急情况的驾驶员，最高速度设置为30km/h。

图9是一个由双目视觉显示的图像，它显示了一个障碍环境。图10是激光雷达的图像，包括障碍物的位置。图11显示了静态的避障轨迹。e红色轨迹为全局路径规划和局部路径规划的轨迹，黄色为障碍物，蓝色为实验车辆的实际轨迹。e静态障碍物是指宽度较大的纸箱，因此避障范围较大。图12和图13是动态避障轨迹。e红色轨迹为全局路径规划和局部路径规划的轨迹，黄色为障碍物，蓝色为实验车辆的实际轨迹，动态障碍物为实验人员。图14-17为真实车辆在高速试验过程中拍摄的避障照片。

.e真实车辆测试表明，该车辆能够实时避免动态障碍物。e的轨迹是平滑的。。。。。。。。。。因此，本文提出的算法可以应用于智能电动汽车平台的实际应用，具有实际的工程应用价值。

6.结论 

本文提出了一种基于改进的∗算法的全局动态路径规划方法，以解决智能驾驶全局路径规划的最优路径和规划效率。该方法具有较高的路径规划效率，动态避障的实时性能好。e本文的具体内容总结如下：

(1) .对传统∗算法的启发式函数h(n)进行了改进，采用动态加权方法使h(n)更接近实际距离d(n)。该方法减少了A-∗路径搜索中的搜索面积，减少了规划时间，提高了算法的效率。

（2）采用优化策略对最优路径进行优化，减少最优路径的冗余节点和转折点，使路径更平滑，有利于智能车辆的驾驶。e将改进的∗算法与动态窗口方法相结合，进行动态避障。不仅保证了改进后的A∗算法能够有效地规划最优路径，而且改进了动态窗口法的局部最优问题，使智能车辆具有全局动态路径规划能力。

（3）在仿真分析中，本文的方法通过2.5%∼3.0%缩短了路径距离，提高了10.3%∼13.6%的效率，生成了一个更平滑的路径。实际车辆测试结果表明，该算法具有良好的实时性性能和动态避障稳定性。e改进的∗方法可实际应用于智能电动汽车平台，在工程应用中具有实用价值。