基于蚁群-动态窗口法的无人驾驶汽车动态路径规划

郑琰，席宽，巴文婷，肖玉杰，余伟; ZHENG Yan; XI Kuan; BA Wenting; XIAO Yujie; YU Wei

2025年5月30日 11:02 星期五

doi: 10.13878/j.cnki.jnuist.20240506001

1. 南京林业大学汽车与交通工程学院,南京, 210037

2. 南京财经大学营销与物流管理学院,南京, 210023

基金项目: 国家自然科学基金(71871111)

详细信息

作者简介

郑琰,女,博士,副教授,研究方向为人工智能算法、智能车路径优化等．yzheng_x@163.com

通讯作者

肖玉杰,男,博士,副教授,主要研究方向为物流系统优化、车辆路径优化等．yujiexiao@nufe.edu.cn

中图分类号: U436.6;TP18

文献标识码: A

Dynamic path planning for autonomous vehicles via ant colony-dynamic window approach

1. College of Automobile and Traffic Engineering,Nanjing Forestry University,Nanjing 210037 ,China

2. School of Marketing and Logistics Management,Nanjing University of Finance & Economics,Nanjing 210023 ,China

摘要

针对传统路径规划算法在无人驾驶汽车应用中搜索效率低、距离较长和路径不平滑的问题进行改进,使用改进蚁群算法最优路径的关键节点替代动态窗口法的局部目标点,并在动态窗口法评价函数中加入目标距离评价子函数,提高路径规划的效率和平滑性,同时采用路径决策方法解决全局路径失效问题,使车辆摆脱障碍困境,满足路径规划安全性的要求．改进后的蚁群算法利用起止点的位置信息使初始信息素分布不均匀,减少搜索初期阶段的时间消耗;通过维护全局最优路径和强化优秀局部路径的信息素浓度,优化信息素更新机制,提高路径探索效率;对规划路径进行二次优化,优化节点和冗余转折点,减少路径长度．仿真结果表明,相比传统路径规划算法,利用本文提出的融合算法所得到的路径在距离、平滑度和收敛性方面都具有更好的表现,且符合无人驾驶汽车安全行驶的要求．

关键词

路径规划 / 蚁群算法 / 动态窗口法 / 动态避障 / 融合算法

Abstract

To address the issues of low search efficiency,long distance,and non-smooth paths in traditional path planning algorithms for autonomous vehicles,this study proposes an improvement by using key nodes of the optimized ant colony algorithm to replace the local target points in the dynamic window approach.Additionally,a target distance evaluation sub-function is incorporated into the dynamic window approach's evaluation function to enhance the efficiency and smoothness of path planning.Furthermore,a path decision-making method is employed to solve the problem of global path failure,enabling the vehicle to avoid obstacles and meet safety requirements of path planning.The improved ant colony algorithm utilizes the positional information of the start and end points to create an uneven initial pheromone distribution,thereby reducing time consumption during the initial search phase.By maintaining the global optimal paths and enhancing the pheromone concentration of excellent local paths,the pheromone update mechanism is optimized to speed up path exploration efficiency.The planned path is further optimized to reduce redundancy in nodes and turning points,thereby shortening path length.Simulation results show that compared to traditional path planning algorithms,the proposed integrated algorithm achieves better performance in terms of distance,smoothness,and convergence,aligning with the safety requirements for autonomous vehicle operation.

Keywords

path planning / ant colony algorithm(ACO) / dynamic window approach(DWA) / dynamic obstacle avoidance / integrated algorithm

0 引言 1 问题描述与环境建模 2 改进蚁群路径规划算法 2.1 不均匀初始信息素分布 2.2 优化信息素更新 2.3 二次路径优化 3 动态窗口法 4 融合算法 4.1 可行性分析 4.2 路径决策方法 4.3 融合算法路径规划的实现 5 仿真试验 5.1 改进蚁群算法仿真试验分析 5.2 融合算法仿真试验分析 6 结论

0 引言

随着互联网5G技术的突破性进展以及自动化技术的持续发展，自动驾驶已成为交通发展的未来趋势．自动驾驶技术能够提高出行安全和缩短出行时间，而制定合理的路径规划更是直接影响无人驾驶汽车的安全性和乘坐舒适性^[1]．传统的路径规划方法包括人工势场法^[2]、模拟退火算法^[3]、快速随机扩展树算法^[4]等．然而，在一些复杂环境下，传统路径规划算法面临搜索区域空间庞大、障碍物分布不规则等挑战，导致寻优效率较低．

蚁群算法^[5]作为一种智能仿生算法，具有良好的全局搜索能力和适应性，在寻找最优路径方面，比其他诸如模拟退火^[6]和遗传算法^[7]等优化方法有着明显的优越性．近年来，针对传统蚁群算法在处理路径规划问题中存在的收敛速度慢、距离较长和路径不平滑等问题，国内外学者展开了大量研究，例如:Miao等^[8]在转移概率中加入障碍排除因子，同时引入自适应调整因子和自适应信息素挥发因子对蚁群算法的信息素更新规则进行改进，加快了算法的收敛速度; 唐传茵等^[9]将蚁群算法与大规模领域搜索算法（LNS）结合起来，有效提高了解的质量; 王倩等^[10]通过在蚁群算法启发函数中引入A^*算法思想及调整信息素的更新机制，同时消除路径冗余点，有效降低了路径长度，提高了算法的搜索速度; 蔡军等^[11]在蚁群算法状态转移公式中引入目标距离和引导素，加快了算法搜索速度并有效避免陷入局部最优; 巫茜等^[12]在蚁群算法启发函数中加入航迹引导因子，并调整信息素的更新机制，加快了算法的收敛速度; Fatemidokht等^[13]通过限制信息素取值范围，采用联合局部最佳路径的信息素调整方式，提高了算法的收敛速度．

据已有文献可知，通过改进初始信息素分配，信息素挥发与更新机制以及搜索模式可以有效地提高路径规划算法求解效率与质量，但也存在一些问题有待进一步研究:1）目前的研究成果主要聚焦于智能机器人的路径规划问题，针对无人驾驶汽车的路径规划问题的相关研究较少; 2）在无人驾驶汽车的局部路径规划，特别是避障机制方面的探讨与创新不够充分，存在进一步研究的空间; 3）部分所规划的路径存在速度突变、转向频繁及转角过大的问题，不符合车辆安全行驶的要求．

针对上述问题，本文综合考虑多种环境条件，对蚁群算法在无人驾驶汽车路径规划中的不足之处进行改进，提出一种融合算法，使用改进蚁群算法最优路径的关键节点替代动态窗口法的局部目标点，提高路径的避障能力，加快算法搜索速度．

1 问题描述与环境建模

路径规划的目的是寻找一个最佳路线（长度、时间最短），同时保证该路线在给定环境中从起点到终点都不与任何障碍物相交^[14]．在无人驾驶汽车路径规划中，需要特别考虑车辆本身的运动学约束问题，如转角约束、速度约束等．因此，本文设定车辆行驶环境为复杂的二维空间，并选取路径长度、时间等作为路径规划的主要评价指标．设置工作环境为N_x×N_y的栅格环境，黑色区域代表障碍物，白色区域代表可通行区域，如图1所示．路径采用8邻域搜索规则，每个栅格的中心点为搜索位置，如图2所示．

图1占据栅格地图

Fig.1Occupancy grid map

图2蚂蚁寻路规则

Fig.2Ant pathfinding rules

按式（1）建立栅格地图与直角坐标系的转化关系，栅格地图序号排列见图1．

\{\begin{matrix} x_{i} = a (m o d (i, N_{x}) - 0.5), \\ 若 x_{i} = - 0.5, 则 x_{i} = N_{x} - 0.5; \\ y_{i} = a (N_{y} + 0.5 - c e i l (i / N_{y})) . \end{matrix}

$\{\begin{matrix} x_{i} = a (m o d (i, N_{x}) - 0.5), \\ 若 x_{i} = - 0.5, 则 x_{i} = N_{x} - 0.5; \\ y_{i} = a (N_{y} + 0.5 - c e i l (i / N_{y})) . \end{matrix}$

(1)

式中:a为栅格大小; mod为求余运算; ceil为向上取整运算; i为栅格序号数;（x_i，y_i）为第i个小栅格位置坐标; N_x为栅格列数; N_y为栅格行数．

2 改进蚁群路径规划算法

2.1 不均匀初始信息素分布

传统蚁群算法（Ant Colony Optimization，ACO）的信息素均匀分布策略导致蚂蚁在搜索初期缺乏有效的引导，出现“乱跑”和“往回走”等无效搜索，导致算法的收敛速度下降．为此，本文提出一种非均匀信息素分布方法．该方法根据起点和终点之间的连线信息，并增加该连线附近的信息素浓度^[15]，信息素浓度随节点与连线的距离增加而逐渐降低，具体公式为

τ = ξ μ τ_{0} + c

$τ = ξ μ τ_{0} + c$

(2)

式中:τ为蚁群算法的初始信息素水平; τ₀为基础信息素量; μ为节点与连线之间的接近程度，μ值随节点与连线的距离减小而增加，取值范围为（0，1）; c为地图中非障碍物区域的占比，c值随着障碍物数量的减少而增加，其取值范围为（0，1）; ξ为连线上障碍物附近信息素增加的权重，当节点位于障碍物附近时取1.2，否则取1．

图3a展示了初始信息素在无障碍物时的分布情况，网格信息素浓度与到连线的距离呈负相关，距离连线越远的信息素浓度越低，颜色深浅表示不同的浓度大小．图3b展示了初始信息素在起点和终点连线上有障碍物时的分布情况，黑色区域代表障碍物，整体的信息素浓度会随障碍物的出现而降低．最优路径较大可能出现在起点和终点的连线附近，而处于起终点连线上的障碍物会对路径的搜索造成影响，通过增加障碍物附近的信息素浓度，能够帮助蚂蚁绕过障碍物，并有效避免倒退搜索．

2.2 优化信息素更新

为了凸显优秀路径的优势，提高算法的收敛速度，构建一种基于最差路径和现行路径差值的信息素浓度动态增量模型，信息素浓度动态增量模型的表达式为

Δ τ_{i j}^{m} (t) = \frac{Q^{*}}{L_{n, m}},

$Δ τ_{i j}^{m} (t) = \frac{Q^{*}}{L_{n, m}},$

图3初始信息素在不同障碍物下的分布

Fig.3Schematic of initial pheromone distribution under different obstacle conditions

Q^{*} = \{\begin{matrix} L_{n, m a x} - L_{n, m}, Q^{*} ⩽ Q_{m a x}; \\ Q_{m a x}, Q^{*} > Q_{m a x} . \end{matrix}

$Q^{*} = \{\begin{matrix} L_{n, m a x} - L_{n, m}, Q^{*} ⩽ Q_{m a x}; \\ Q_{m a x}, Q^{*} > Q_{m a x} . \end{matrix}$

(3)

式中:Δτ^m_ij（t）为信息素增量; Q^*为改进后的信息素浓度强度; n为当前的迭代次数; L_n_，_m为当前路径长度，即第m只蚂蚁在第n次迭代产生的路径长度; L_n_，max为最差路径长度，即第n次迭代的所有路径中最长的路径长度; Q_max为信息素浓度的最大强度．

2.3 二次路径优化

蚁群算法规划的路径存在大量的节点及转折点冗余，路径长度有进一步缩短的空间，如图4所示．本文通过二次路径优化对上述问题进行处理，去掉路径中多余节点和转折点，保留关键节点，减少路径长度．优化原理:通过判断当前节点与间隔节点及障碍物的位置关系，进而推断能否舍去邻近节点，若位置关系处于水平、垂直或连线与障碍物的距离小于障碍物的作用范围，则舍去相邻节点，待节点无法舍去时，选取下一节点作为当前节点，然后重复上述过程．

如图5所示，选取蚁群搜索的6个关键节点q₁~q₆，其中，q₁为当前节点，q₂为相邻节点，q₃、q₄、q₅、q₆为间隔节点．节点q₁与节点q₃、q₄、q₅均处于水平、垂直或连线与障碍物的距离小于障碍物的作用范围的位置关系，所以去掉冗余节点q₂、q₃、q₄．节点q₁与q₆的位置关系既不水平也不垂直且与障碍物的距离小于障碍物的作用范围，则节点q₅无法去掉．将节点q₅设为当前节点，并重复上述过程．优化后路径（图5橙色路径）为q₁→q₅→q₆．

3 动态窗口法

动态窗口法（Dynamic Window Approach，DWA）^[16]是一种基于车辆动力学性能的局部路径规划方法，在给定时间窗口内生成合适的速度和转向指令，以确保车辆安全地到达目标点．

图4蚁群算法搜索路径

Fig.4Path searching via ant colony algorithm

图5二次路径优化原理

Fig.5Principle of secondary path optimization

1）建立无人驾驶汽车运动模型

本文将动态窗口法应用在无人驾驶汽车上，假定车辆的线速度v和角速度w能够独立受控，每组速度（v，w）在一定时间内产生不同的轨迹．在Δt时间内，把无人驾驶汽车相邻时刻的运动视为匀速直线运动，那么第t+Δt时刻无人驾驶汽车的位姿表示为

[\begin{matrix} x_{t + Δ t} \\ y_{t + Δ t} \\ θ_{t + Δ t} \end{matrix}] = [\begin{matrix} x_{t} \\ y_{t} \\ θ_{t} \end{matrix}] + [\begin{matrix} c o s θ & 0 \\ s i n θ & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} v Δ t \\ w Δ t \end{matrix}] .

$[\begin{matrix} x_{t + Δ t} \\ y_{t + Δ t} \\ θ_{t + Δ t} \end{matrix}] = [\begin{matrix} x_{t} \\ y_{t} \\ θ_{t} \end{matrix}] + [\begin{matrix} c o s θ & 0 \\ s i n θ & 0 \\ 0 & 1 \end{matrix}] [\begin{matrix} v Δ t \\ w Δ t \end{matrix}] .$

(4)

式中:[x_t_+Δ_t y_t_+Δ_t θ_t_+Δ_t]^Τ为t+Δt时刻世界坐标系下车辆的位置坐标姿态; [x_t y_t θ_t]^Τ为t时刻世界坐标系下车辆的位置坐标姿态; [vΔt wΔt]^Τ为t时刻坐标系下车辆的位置坐标姿态变化; θ为t时刻车辆的姿态角．

2）无人驾驶汽车速度空间约束

在动态窗口法中，基于自身的动力学和运动学特点，无人驾驶汽车的速度控制会受到最大最小速度约束、动力学约束以及安全约束，每个时间间隔的预测轨迹都在三者共同的作用下产生．

3）轨迹评价

在动态窗口法中，每条预测生成的轨迹的优劣需要通过轨迹评价函数进行量化，无人驾驶汽车以最优轨迹对应的（v，w）作为速度控制指令进行行驶．动态窗口法的轨迹评价函数如下:

\begin{matrix} G (v, w) = σ (α \cdot h e n d (v, w) + β \cdot d i s t (v, w) + \\ γ \cdot v e l (v, w)) . \end{matrix}

$\begin{matrix} G (v, w) = σ (α \cdot h e n d (v, w) + β \cdot d i s t (v, w) + \\ γ \cdot v e l (v, w)) . \end{matrix}$

(5)

式中:G（v，w）为车辆在速度（v，w）下的轨迹评价值; σ为归一化系数; hend（v，w）为轨迹末端车辆朝向与目标方向的角度差距; dist（v，w）为轨迹末端车辆位置与障碍物的最短距离; vel（v，w）为轨迹末端车辆的速度; α、β、γ为G（v，w）中三项评价值的权重系数．

在传统动态窗口法运行过程中，如果采样轨迹周围存在障碍物，动态窗口法会选择离障碍物较远的采样轨迹，即使车辆与目标点的直线轨迹不与障碍物相交，使得轨迹的路径较长且转弯频繁．基于此，本文将目标距离评价子函数引入到动态窗口法的轨迹评价函数中，减少路径长度，提高路径的平滑性．目标距离评价子函数的数学模型如下:

\{\begin{matrix} d_{c} = \sqrt{{(x_{g} - x_{c})}^{2} + {(y_{g} - y_{c})}^{2}}, \\ g d i s t (v, w) = 1 / d_{c} . \end{matrix}

$\{\begin{matrix} d_{c} = \sqrt{{(x_{g} - x_{c})}^{2} + {(y_{g} - y_{c})}^{2}}, \\ g d i s t (v, w) = 1 / d_{c} . \end{matrix}$

(6)

式中:d_c为轨迹末端车辆与目标点的距离;（x_g，y_g）为目标点的坐标;（x_c，y_c）为车辆轨迹末端点的坐标; gdist（v，w）为车辆目标距离评价子函数．

因此，改进后的动态窗口算法的轨迹评价函数为

\begin{matrix} G (v, w) = σ (α \cdot h e n d (v, w) + β \cdot d i s t (v, w) + \\ γ \cdot v e l (v, w) + δ \cdot g d i s t (v, w)) . \end{matrix}

$\begin{matrix} G (v, w) = σ (α \cdot h e n d (v, w) + β \cdot d i s t (v, w) + \\ γ \cdot v e l (v, w) + δ \cdot g d i s t (v, w)) . \end{matrix}$

(7)

4 融合算法

4.1 可行性分析

将目标距离引入到DWA算法评价函数中，使得算法的各项性能相较于传统DWA算法有了较大的提升，但在试验中，由于DWA算法仅依靠全局目标点的信息进行路径搜索，会使车辆在遇到T型、U型等陷阱时停止前进，如图6a所示．在搜索过程中加入局部目标点（1.5，2.5）、（2.5，4.5）和（3.5，5.5）后，车辆能够很好地避开陷阱区域，最后成功到达目标点，如图6b所示．因此，在全局目标点中加入合适的局部目标点能够有效改善DWA算法在路径搜索过程中的不足．

图6DWA算法规划路径对比

Fig.6Comparison of DWA path planning

4.2 路径决策方法

当环境发生变化时，比如新出现的障碍物与原来的障碍物形成了U形陷阱或者新出现的障碍物覆盖原全局路径规划的关键节点等，这些情况都会导致原生成的全局最优路径失效，如果依然采用原来的全局路径作为参考路径，可能会大大增加规划路径的时间和距离，甚至规划失败．基于此，本文提出一种决策方法，即当遇到大面积动态障碍物堵塞全局路径规划的路径时，利用当前车辆最近的节点作为起点重新规划全局路径，并将全局路径的关键节点作为局部路径规划的局部目标点．

4.3 融合算法路径规划的实现

采用改进蚁群算法最优路径的关键节点替代动态窗口法的局部目标点，本文提出一种基于融合算法的无人驾驶汽车动态路径规划方法，以缩短路径长度、减少路径规划时间．具体流程如图7所示．

图7融合算法流程

Fig.7Fusion algorithm flowchart

融合算法的实现步骤如下:

1）获取环境信息，采用栅格法建立无人驾驶汽车的工作环境.

2）利用改进的蚁群算法进行全局路径规划，获取规划路径的关键节点序列.

3）使用改进蚁群算法最优路径的关键节点替代动态窗口法的局部目标点.

4）把局部的目标点作为轨迹采样的预测输入，通过改进的评价函数进行评价，选择最优的速度控制作为输出.

5）检测车辆的环境信息，若新障碍物或动态障碍物遮挡局部目标点或堵塞全局路径使车辆无法通行时，选取车辆最近的节点作为起点，回到2）重新规划全局路径.

6）判断车辆是否到达局部目标点，如果车辆与局部目标点的距离小于0.5 m，则视为到达局部目标点，此时选择下一个节点作为新的局部目标点，并重新执行4）; 若未到达局部目标点，则回到4）继续迭代．

7）判断车辆是否到达全局目标点，如果车辆与全局目标点的距离小于0.2 m，则视为到达全局目标点; 若没有到达全局目标点，则回到6），直到到达全局目标点．

5 仿真试验

5.1 改进蚁群算法仿真试验分析

仿真试验用改进后的蚁群算法、传统蚁群算法和文献^[17]算法的路径规划进行对比，验证改进蚁群算法的有效性．选取栅格地图规模为20×20和30×30，其中:20×20环境中包含简单、复杂两种环境，简单环境障碍物覆盖率为25%，复杂环境障碍物覆盖率为55%，且包含狭窄、危险区域; 30×30环境的障碍物覆盖率为25%．在栅格地图环境中，白色区域表示自由区域，即可通行区域，黑色区域表示障碍物区域，即不可通行区域．蚁群算法的参数设置:蚂蚁数M为50，信息素启发因子α为1，期望启发因子β为7.5，信息素增加强度系数Q为1，最大迭代次数N_max为100，信息素挥发因子ρ为0.7，Q_max为1.2．路径规划起点为左下角，用三角形表示，终点为右上角，用圆形表示．3种算法路径规划结果对比如图8所示．

由表1可知，通过对比3种不同的搜索空间的仿真试验，改进蚁群算法在迭代次数上较传统蚁群算法分别降低44.44%、33.33%、37.88%，相比文献^[17]算法分别降低28.57%、25%、24.07%，在路径长度上较两种算法也有一定的优化．通过对蚁群规划路径进行二次优化，使得改进的蚁群算法规划路径的节点数、转折点数更少，有效提高了路径的平滑性，降低了路径长度．从图8a和8b可以得出，随着栅格地图障碍物的增多，改进蚁群算法的优化效果得到加强，特别是在具有狭窄区域的环境中，二次路径优化的效果更为明显．从图8a和8c可以得出，在不同规模的环境下，改进的蚁群算法在路径长度、迭代次数等方面均有较好的优化效果，可以有效缩短路径长度，加快算法的搜索速度．

图8不同环境规模下三种算法路径规划对比

Fig.8Comparison of path planning results via three algorithms in different environmental scales

表1三种算法性能对比

Table1Performance comparison between three algorithms

5.2 融合算法仿真试验分析

为了客观评价融合算法的性能指标，在多种环境下进行仿真试验，验证本文融合算法的路径规划效果．融合算法参数设置:最大线速度v_max为1.0 m/s，线速度的最大加速度

{\dot{v}}_{m a x}

${\dot{v}}_{m a x}$ 为0.2 m/s²，线速度分辨率d_v为0.01 m/s，最大角速度w_max为20 deg/s，角速度的最大加速度

{\dot{w}}_{m a x}

${\dot{w}}_{m a x}$ 为50 deg/s²，角速度分辨率d_w为1 deg/s，模拟时间间隔Δt为3.0 s，单位时间dt为0.1 s，评价函数各部分的权重系数α为0.05，β为0.2，γ为0.1，δ为0.3．

1）静态环境下融合算法仿真试验分析

构建20 m×20 m栅格地图作为融合算法路径规划静态环境下的仿真试验环境，起始点坐标为（0.5，0.5），用三角形表示，目标点为（19.5，19.5），用圆圈表示，将融合算法与DWA算法进行对比分析，验证融合算法的有效性．仿真结果如图9所示．

图9融合算法和改进DWA路径轨迹对比

Fig.9Comparison of path trajectories between fusion algorithm and improved DWA

在图9中，融合算法获得的路径长度为28.55 m，相较DWA算法获得的路径长度31.29 m，缩短了8.76%．在轨迹平滑度方面，融合算法获得的轨迹更为平滑，曲折较小．

2）变化环境下融合算法仿真试验分析

构建20 m×20 m栅格地图作为路径规划变化环境下的仿真试验环境，黑色区域为障碍物区域，白色区域为自由区域，红色区域为随机障碍物区域，路径规划起点坐标为（0.5，0.5），目标点为（19.5，19.5），验证融合算法在变化环境下的有效性．仿真结果如图10所示，融合算法的性能如表2所示．

图10变化环境下融合算法路径规划

Fig.10Path planning with fusion algorithm in changing environment

表2融合算法性能

Table2Performance of fusion algorithm

由图10可知，本文融合算法在面对突然出现的障碍物时仍能很好地发挥避障的作用，规划出一条避开障碍物的平滑路径，避免车辆与障碍物发生碰撞．从表2中可以看出，在宽阔地带出现障碍物时，规划出的路径比其他两种环境的路径更长．这是因为在狭窄地带出现障碍物的情况下，尽管障碍物覆盖了全局路径，但同时也引导车辆朝向更短的路径行驶，从而降低了路径长度．

3）融合算法路径选择策略的仿真试验分析

为了验证当全局路径失效时融合算法路径决策方法的有效性，构建20 m×20 m的栅格地图，黑色区域为障碍物区域，白色区域为自由区域，红色区域为随机障碍物区域，黄色区域为动态障碍物区域，起始点坐标为（0.5，0.5），目标点为（19.5，19.5），随机障碍物坐标为（2.5，3.5）、（3.5，3.5）、（4.5，3.5）、（5.5，8.5）、（6.5，8.5）、（7.5，8.5）、（17.5，15.5）、（17.5，16.5）和（17.5，17.5），动态障碍物在（10.5，7.5）和（14.5，7.5）之间往返运动，起点坐标为（10.5，7.5），改进蚁群算法规划的初始全局路径的关键节点为（7.5，8.5）、（10.5，13.5）、（16.5，19.5）．融合算法经632次迭代从起点到达目标点，其中部分迭代结果如图11所示．

由图11可以看出，车辆从起始点前往局部目标点（7.5，8.5）的过程中，新静态障碍物1刚好挡在全局路径上，此时无人驾驶汽车进行了实时避障，顺利到达局部目标点（7.5，8.5）附近．但在前往局部目标点（7.5，8.5）的过程中，新静态障碍物2与周边障碍物形成了U形陷阱，使得车辆无法到达局部目标点（7.5，8.5），这时对无人驾驶汽车进行了新的全局路径规划，将新静态障碍物1、2加入新地图中，以当前车辆最近的节点（7.5，6.5）作为起始点，利用改进的蚁群算法进行路径规划，将新的关键节点作为局部目标点．在前往局部目标点（19，5，15.5）的过程中，出现了以0.2 m/s做匀速运动的动态障碍物3，车辆仍然能够及时进行躲避．最后在前往全局目标点（19.5，19.5）的过程中，车辆同样很好地避开了出现的新静态障碍物4，并顺利到达全局目标点．综上所述，融合算法的路径规划能进行实时避障，在全局路径失效时可以再次规划全局路径，使车辆摆脱了障碍困境，到达全局目标点．

6 结论

1）针对传统蚁群算法在无人驾驶汽车路径规划中的不足进行改进，通过初始信息素不均匀分布，优化信息素更新机制和二次路径优化，减少了转折点和节点冗余并有效降低了路径长度，提高了算法搜索速度．

2）针对无人驾驶汽车的局部避障，使用改进蚁群算法最优路径的关键节点替代动态窗口法的局部目标点，同时在轨迹评价中引入目标距离评价，并采用路径决策方法解决全局路径失效问题，使得算法在进行实时避障时提高搜索效率．

3）通过仿真试验验证了改进蚁群算法和融合算法的有效性．结果表明:改进蚁群算法在不同的环境下均较传统蚁群算法性能更优，优化效果随着环境复杂度提高而升高．融合算法能充分利用全局路径规划的结果，避开障碍物并减少路径长度，满足路径规划安全性的要求，对优化无人驾驶汽车的行驶路径规划方案具有现实意义．

图11融合算法路径决策方法下的规划路径

Fig.11Planned paths under fusion algorithm decision-making method

图1占据栅格地图

Fig.1Occupancy grid map

下载: 全尺寸图片

图2蚂蚁寻路规则

Fig.2Ant pathfinding rules

下载: 全尺寸图片

图3初始信息素在不同障碍物下的分布

Fig.3Schematic of initial pheromone distribution under different obstacle conditions

下载: 全尺寸图片

图4蚁群算法搜索路径

Fig.4Path searching via ant colony algorithm

下载: 全尺寸图片

图5二次路径优化原理

Fig.5Principle of secondary path optimization

下载: 全尺寸图片

图6DWA算法规划路径对比

Fig.6Comparison of DWA path planning

下载: 全尺寸图片

图7融合算法流程

Fig.7Fusion algorithm flowchart

下载: 全尺寸图片

图8不同环境规模下三种算法路径规划对比

Fig.8Comparison of path planning results via three algorithms in different environmental scales

下载: 全尺寸图片

图9融合算法和改进DWA路径轨迹对比

Fig.9Comparison of path trajectories between fusion algorithm and improved DWA

下载: 全尺寸图片

图10变化环境下融合算法路径规划

Fig.10Path planning with fusion algorithm in changing environment

下载: 全尺寸图片

图11融合算法路径决策方法下的规划路径

Fig.11Planned paths under fusion algorithm decision-making method

下载: 全尺寸图片

表1三种算法性能对比

Table1Performance comparison between three algorithms

下载: 全尺寸图片

表2融合算法性能

Table2Performance of fusion algorithm

下载: 全尺寸图片

图1占据栅格地图

Fig.1Occupancy grid map

图2蚂蚁寻路规则

Fig.2Ant pathfinding rules

图3初始信息素在不同障碍物下的分布

Fig.3Schematic of initial pheromone distribution under different obstacle conditions

图4蚁群算法搜索路径

Fig.4Path searching via ant colony algorithm

图5二次路径优化原理

Fig.5Principle of secondary path optimization

图6DWA算法规划路径对比

Fig.6Comparison of DWA path planning

图7融合算法流程

Fig.7Fusion algorithm flowchart

图8不同环境规模下三种算法路径规划对比

Fig.8Comparison of path planning results via three algorithms in different environmental scales

图9融合算法和改进DWA路径轨迹对比

Fig.9Comparison of path trajectories between fusion algorithm and improved DWA

图10变化环境下融合算法路径规划

Fig.10Path planning with fusion algorithm in changing environment

图11融合算法路径决策方法下的规划路径

Fig.11Planned paths under fusion algorithm decision-making method

表1三种算法性能对比

Table1Performance comparison between three algorithms

表2融合算法性能

Table2Performance of fusion algorithm

[1]	熊璐, 杨兴, 卓桂荣, 等. 无人驾驶车辆的运动控制发展现状综述[J]. 机械工程学报,2020,56(10):127-143. XIONG Lu, YANG Xing, ZHUO Guirong,et al. Review on motion control of autonomous vehicles[J]. Journal of Mechanical Engineering,2020,56(10):127-143
[2]	赵奉奎, 葛振, 董锋威, 等. 基于改进人工势场法的智能汽车轨迹规划算法研究[J]. 重庆交通大学学报(自然科学版),2022,41(11):153-160. ZHAO Fengkui, GE Zhen, DONG Fengwei,et al. Intelligent vehicle trajectory planning algorithm based on improved artificial potential field method[J]. Journal of Chongqing Jiaotong University(Natural Science),2022,41(11):153-160
[3]	陶重犇, 雷祝兵, 李春光, 等. 基于改进模拟退火算法的搬运机器人路径规划[J]. 计算机测量与控制,2018,26(7):182-185. TAO Chongben, LEI Zhubing, LI Chunguang,et al. Path planning of handling robot based on improved simulated annealing algorithm[J]. Computer Measurement & Control,2018,26(7):182-185
[4]	Shi Y Y, Li Q Q, Bu S Q,et al. Research on intelligent vehicle path planning based on rapidly-exploring random tree[J]. Mathematical Problems in Engineering,2020:5910503
[5]	张松灿, 普杰信, 司彦娜, 等. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用,2020,56(8):10-19. ZHANG Songcan, PU Jiexin, SI Yanna,et al. Survey on application of ant colony algorithm in path planning of mobile robot[J]. Computer Engineering and Applications,2020,56(8):10-19
[6]	Steinbrunn M, Moerkotte G, Kemper A. Heuristic and randomized optimization for the join ordering problem[J]. The VLDB Journal,1997,6(3):191-208
[7]	Grefenstette J J. Genetic algorithms and machine learning[C]//Proceedings of the Sixth Annual Conference on Computational Learning Theory. July 26-28,1993, Santa Cruz, California, USA. ACM,1993:3-4
[8]	Miao C W, Chen G Z, Yan C L,et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering,2021,156:107230
[9]	唐传茵, 章明理, 李静红, 等. 基于改进蚁群算法的外卖配送路径规划研究[J]. 南京信息工程大学学报,2024,16(2):145-154. TANG Chuanyin, ZHANG Mingli, LI Jinghong,et al. Takeout delivery path planning based on improved ant colony optimization algorithm[J]. Journal of Nanjing University of Information Science & Technology,2024,16(2):145-154
[10]	王倩, 杨立炜, 李俊丽, 等. 蚁群融合动态窗口法的分布式多机器人运动规划研究[J]. 重庆邮电大学学报(自然科学版),2024,36(1):20-28. WANG Qian, YANG Liwei, LI Junli,et al. Research on distributed multi-robot motion planning based on ant colony algorithm fusion dynamic window approach[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2024,36(1):20-28
[11]	蔡军, 钟志远. 改进蚁群算法的送餐机器人路径规划[J]. 智能系统学报,2024,19(2):370-380. CAI Jun, ZHONG Zhiyuan. Path planning of a meal delivery robot based on an improved ant colony algorithm[J]. CAAI Transactions on Intelligent Systems,2024,19(2):370-380
[12]	巫茜, 黄浩, 曾青, 等. 改进ACO算法的UAV航迹规划在山区物流配送中的应用研究[J]. 重庆理工大学学报(自然科学),2022,36(10):185-191. WU Qian, HUANG Hao, ZENG Qing,et al. Application of UAV trajectory planning based on improved ACO algorithm in mountain logistics[J]. Journal of Chongqing University of Technology(Natural Science),2022,36(10):185-191
[13]	Fatemidokht H, Kuchaki Rafsanjani M. F-Ant:an effective routing protocol for ant colony optimization based on fuzzy logic in vehicular ad hoc networks[J]. Neural Computing and Applications,2018,29(11):1127-1137
[14]	王鹤静, 王丽娜. 机器人路径规划算法综述[J]. 桂林理工大学学报,2023,43(1):137-147. WANG Hejing, WANG Lina. Review of path planning for robots[J]. Journal of Guilin University of Technology,2023,43(1):137-147
[15]	曹新亮, 王智文, 冯晶, 等. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学,2020,42(3):564-570. CAO Xinliang, WANG Zhiwen, FENG Jing,et al. Global path planning of robots based on improved ant colony algorithm[J]. Computer Engineering & Science,2020,42(3):564-570
[16]	张琳, 章新杰, 郭孔辉, 等. 未知环境下智能汽车轨迹规划滚动窗口优化[J]. 吉林大学学报(工学版),2018,48(3):652-660. ZHANG Lin, ZHANG Xinjie, GUO Konghui,et al. Rolling window optimization for intelligent vehicle trajectory planning in unknown environment[J]. Journal of Jilin University(Engineering and Technology Edition),2018,48(3):652-660
[17]	牛龙辉, 季野彪. 基于改进蚁群算法的机器人路径规划问题研究[J]. 微处理机,2020,41(1):37-40. NIU Longhui, JI Yebiao. Research on robot path planning based on improved ant colony algorithm[J]. Microprocessors,2020,41(1):37-40

PDF下载

XML下载导出引用

引用提醒

图(11) / 表(2)

手机扫码阅读

引用本文

郑琰，席宽，巴文婷，肖玉杰，余伟.基于蚁群-动态窗口法的无人驾驶汽车动态路径规划[J].南京信息工程大学学报(自然科学版),2025,17(2):256-264
ZHENG Yan, XI Kuan, BA Wenting, XIAO Yujie, YU Wei. Dynamic path planning for autonomous vehicles via ant colony-dynamic window approach[J]. Journal of Nanjing University of Information Science & Technology, 2025,17(2):256-264

复制

计量

文章访问量: 30

HTML全文浏览量: 4

PDF下载量: 32

图1占据栅格地图

Fig.1Occupancy grid map

图2蚂蚁寻路规则

Fig.2Ant pathfinding rules

图3初始信息素在不同障碍物下的分布

Fig.3Schematic of initial pheromone distribution under different obstacle conditions

图4蚁群算法搜索路径

Fig.4Path searching via ant colony algorithm

图5二次路径优化原理

Fig.5Principle of secondary path optimization

图6DWA算法规划路径对比

Fig.6Comparison of DWA path planning

图7融合算法流程

Fig.7Fusion algorithm flowchart

图8不同环境规模下三种算法路径规划对比

Fig.8Comparison of path planning results via three algorithms in different environmental scales

图9融合算法和改进DWA路径轨迹对比

Fig.9Comparison of path trajectories between fusion algorithm and improved DWA

图10变化环境下融合算法路径规划

Fig.10Path planning with fusion algorithm in changing environment

图11融合算法路径决策方法下的规划路径

Fig.11Planned paths under fusion algorithm decision-making method

表1三种算法性能对比

Table1Performance comparison between three algorithms

表2融合算法性能

Table2Performance of fusion algorithm

熊璐, 杨兴, 卓桂荣, 等. 无人驾驶车辆的运动控制发展现状综述[J]. 机械工程学报,2020,56(10):127-143. XIONG Lu, YANG Xing, ZHUO Guirong,et al. Review on motion control of autonomous vehicles[J]. Journal of Mechanical Engineering,2020,56(10):127-143

赵奉奎, 葛振, 董锋威, 等. 基于改进人工势场法的智能汽车轨迹规划算法研究[J]. 重庆交通大学学报(自然科学版),2022,41(11):153-160. ZHAO Fengkui, GE Zhen, DONG Fengwei,et al. Intelligent vehicle trajectory planning algorithm based on improved artificial potential field method[J]. Journal of Chongqing Jiaotong University(Natural Science),2022,41(11):153-160

陶重犇, 雷祝兵, 李春光, 等. 基于改进模拟退火算法的搬运机器人路径规划[J]. 计算机测量与控制,2018,26(7):182-185. TAO Chongben, LEI Zhubing, LI Chunguang,et al. Path planning of handling robot based on improved simulated annealing algorithm[J]. Computer Measurement & Control,2018,26(7):182-185

Shi Y Y, Li Q Q, Bu S Q,et al. Research on intelligent vehicle path planning based on rapidly-exploring random tree[J]. Mathematical Problems in Engineering,2020:5910503

张松灿, 普杰信, 司彦娜, 等. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用,2020,56(8):10-19. ZHANG Songcan, PU Jiexin, SI Yanna,et al. Survey on application of ant colony algorithm in path planning of mobile robot[J]. Computer Engineering and Applications,2020,56(8):10-19

Steinbrunn M, Moerkotte G, Kemper A. Heuristic and randomized optimization for the join ordering problem[J]. The VLDB Journal,1997,6(3):191-208

Grefenstette J J. Genetic algorithms and machine learning[C]//Proceedings of the Sixth Annual Conference on Computational Learning Theory. July 26-28,1993, Santa Cruz, California, USA. ACM,1993:3-4

Miao C W, Chen G Z, Yan C L,et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering,2021,156:107230

唐传茵, 章明理, 李静红, 等. 基于改进蚁群算法的外卖配送路径规划研究[J]. 南京信息工程大学学报,2024,16(2):145-154. TANG Chuanyin, ZHANG Mingli, LI Jinghong,et al. Takeout delivery path planning based on improved ant colony optimization algorithm[J]. Journal of Nanjing University of Information Science & Technology,2024,16(2):145-154

王倩, 杨立炜, 李俊丽, 等. 蚁群融合动态窗口法的分布式多机器人运动规划研究[J]. 重庆邮电大学学报(自然科学版),2024,36(1):20-28. WANG Qian, YANG Liwei, LI Junli,et al. Research on distributed multi-robot motion planning based on ant colony algorithm fusion dynamic window approach[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2024,36(1):20-28

蔡军, 钟志远. 改进蚁群算法的送餐机器人路径规划[J]. 智能系统学报,2024,19(2):370-380. CAI Jun, ZHONG Zhiyuan. Path planning of a meal delivery robot based on an improved ant colony algorithm[J]. CAAI Transactions on Intelligent Systems,2024,19(2):370-380

巫茜, 黄浩, 曾青, 等. 改进ACO算法的UAV航迹规划在山区物流配送中的应用研究[J]. 重庆理工大学学报(自然科学),2022,36(10):185-191. WU Qian, HUANG Hao, ZENG Qing,et al. Application of UAV trajectory planning based on improved ACO algorithm in mountain logistics[J]. Journal of Chongqing University of Technology(Natural Science),2022,36(10):185-191

Fatemidokht H, Kuchaki Rafsanjani M. F-Ant:an effective routing protocol for ant colony optimization based on fuzzy logic in vehicular ad hoc networks[J]. Neural Computing and Applications,2018,29(11):1127-1137

王鹤静, 王丽娜. 机器人路径规划算法综述[J]. 桂林理工大学学报,2023,43(1):137-147. WANG Hejing, WANG Lina. Review of path planning for robots[J]. Journal of Guilin University of Technology,2023,43(1):137-147

曹新亮, 王智文, 冯晶, 等. 基于改进蚁群算法的机器人全局路径规划研究[J]. 计算机工程与科学,2020,42(3):564-570. CAO Xinliang, WANG Zhiwen, FENG Jing,et al. Global path planning of robots based on improved ant colony algorithm[J]. Computer Engineering & Science,2020,42(3):564-570

张琳, 章新杰, 郭孔辉, 等. 未知环境下智能汽车轨迹规划滚动窗口优化[J]. 吉林大学学报(工学版),2018,48(3):652-660. ZHANG Lin, ZHANG Xinjie, GUO Konghui,et al. Rolling window optimization for intelligent vehicle trajectory planning in unknown environment[J]. Journal of Jilin University(Engineering and Technology Edition),2018,48(3):652-660

牛龙辉, 季野彪. 基于改进蚁群算法的机器人路径规划问题研究[J]. 微处理机,2020,41(1):37-40. NIU Longhui, JI Yebiao. Research on robot path planning based on improved ant colony algorithm[J]. Microprocessors,2020,41(1):37-40

地址：江苏省南京市宁六路219号邮编：210044

联系电话：025-58731025 E-mail：nxdxb@nuist.edu.cn