智能汽车主动避障的改进蚁群路径规划方法

吕 佳，邱建岗

（1.重庆建筑工程职业学院轨道与机电工程系，重庆 400072；2.北京汽车动力总成有限公司，北京 101106）

1 引言

随着家用汽车的普及，汽车在城镇居民家庭中的保有量持续升高，而与此同时行车安全问题也逐渐受到关注。随着人工智能和传感技术的快速发展，智能汽车逐渐成为各个国家关注的热点方向。所谓智能汽车是指在普通汽车上加装传感系统、控制系统和执行系统，以使车辆能够智能感知外界环境并自主进行行为决策[1]。智能轨迹规划方法是智能汽车的关键技术，主要涉及两部分内容：（1）以某种性能最优为优化指标，规划汽车从出发点到终点的路径；（2）在路径规划过程中，主动避开沿途的障碍物。目前，研究智能汽车轨迹规划算法对智能汽车行业的快速发展至关重要[2−3]。

国内外学者围绕智能汽车主动避障路径规划方法做了大量工作，主要方法包括人工势场法[4]、Dijkstra算法[5]、滚动时域法[6]、遗传算法[7]、蚁群算法[8−9]等。文献[5]提出了一种改进的Dijkstra算法以规划移动机器人路径，但该算法容易陷入局部最优。文献[6]基于滚动时域优化思路对移动机器人进行轨迹规划，但该算法对系统的模型精度要求较高，在较为复杂的栅格环境中很难找到最优解析解。Dijkstra算法虽然能有效规划路径，但算法的可行性较差，解算出最优解耗时过长。此外，遗传算法计算效率较低，收敛速度较慢且占用内存较大。

人工势函数法虽在一定程度上能够满足规划需求，但其解算过程容易受初值的影响[10]。传统的蚁群算法由于其具有良好的鲁棒性和可靠性在智能避障方面受到学者们的青睐。但该算法也存在进化速度缓慢、容易陷入局部最优等问题[11]。由此可知，探索较为有效的智能搜索算法仍存在挑战。

在充分考虑传统蚁群算法缺陷的基础上，为解决智能汽车主动避障轨迹规划问题，这里提出了一种改进蚁群智能轨迹规划方法。在传统蚁群算法的基础上，通过在迭代过程中自适应调节信息素因子、启发因子、信息素挥发率和信息素浓度函数，实现了自适应轨迹规划的目标。所提方法能够自适应更新各项参数以扩大粒子搜索范围、提升算法全局搜索能力并且显著加快算法的收敛速度，从而有效解决了算法的局部最优和进化缓慢问题。智能汽车主动避障实验验证了所提方法的有效性和可靠性。

2 蚁群算法基本原理和流程

2.1 蚁群算法基本原理

蚁群算法由意大利学者提出，该算法模拟蚁群运动规律，在路径规划过程中用信息素浓度表征蚂蚁对当前路径选择的概率大小，较大的信息素浓度意味着蚂蚁选择该路径的概率较大且该路径较优。蚁群算法经过多次迭代，最终可找到从出发点到目标地的最优路径。目前该算法在智能路径规划和主动避障方面应用较为广泛。在传统的蚁群算法中，每只蚂蚁选择路径（i，j）的转移概率可表示为：

式中：dij(t)—两点i和j之间的距离。

当在一次迭代循环中每只蚂蚁完成路径规划后，信息素全局更新方法为：

式中：τij(t+1)—第（k+1）次迭代时信息素总量；Δτij(t)—相应的增量；ρ—信息素挥发率；Q—信息素强度，为常值；Lk—第k个蚂蚁选择路径（i，j）时的路径长度。

2.2 蚁群算法具体流程

（1）参数初始化

初始化蚁群种群数量n，信息素因子α，启发信息因子β，信息素挥发率ρ，信息素强度Q，以及最大迭代次数Nmax，同时约定蚁群的出发点和终点。

（2）更新状态转移概率

对于每只蚂蚁，计算路径（i，j）的距离，并根据式（1）和式（2）计算转移概率。通过比较不同路径的概率大小，确定该步的路径节点。

（3）更新禁忌表

对于每只蚂蚁，每经过一个节点后将该节点纳入禁忌表；

（4）搜索全局路径

对于每只蚂蚁，重复步骤（2）和（3），直到到达终点，同时将每只蚂蚁的全局路径进行保存；

（5）更新信息素

所有蚂蚁规划完路径后，对于每条路径的信息素进行更新，也就是计算式（4）～式（6）；

（6）循环迭代

在第（5）步信息素更新的基础上，将所有蚂蚁重新放回出发点，重新进行路径规划，直到达到最大迭代次数。在每次迭代之后，保留每代蚂蚁的最短路径。

（7）最优路径

对比每代蚁群的最短路径，并找出最短路径即为最优路径。

蚁群算法由于计算过程清晰、鲁棒性强，且易与其他算法结合，在智能汽车轨迹规划和避障领域应用较为广泛。但由2.2节基本流程（1）～（7）可知，由于信息素因子α，启发信息因子β和信息素挥发率ρ不能随路径搜索过程进行自适应调节，这也给智能汽车轨迹规划和避障带来了一定的缺陷，如收敛速度慢、易于陷入局部最优以及搜索停滞等问题。针对本文智能汽车轨迹规划问题，为了提高算法的实用性和可靠性，本文提出一种改进的蚁群算法。

3 改进的蚁群算法

由式（1）可知，每只蚂蚁的一步转移概率与信息素因子α和起发因子β直接相关，在基本蚁群算法中，α和β均设置为固定值，该做法极易造成算法的局部最优。其次，信息素挥发率ρ对算法的全局搜索能力有很大影响，而传统蚁群算法不能够对ρ进行自适应调节，这也不利于算法的快速收敛。

本节提出一种改进蚁群算法以增强算法的可行性和稳定性。首先，3.1节给出一种α和β的自适应更新方法以扩大算法的全局搜索空间，增强算法的可靠性。其次，通过自适应调节信息素挥发率ρ进一步提高算法的收敛速度；最后，通过改进式（2）的启发函数ηij(t)的计算方式以提高蚂蚁就近选择路径的概率，进而提高算法的运算效率。

3.1 自适应调节信息素因子和启发因子

由式（1）可知，信息素因子α和启发因子β对蚂蚁一步转移概率有十分重要的影响。α过大或者过小，该算法均会陷入局部最优。β过大则蚂蚁更倾向于选择较近的路径。因此，这里给出了一种自适应更新方法，具体如式（6）所示：

式中：αmin和βmin—初始值；αmax和βmax—最大值；P—循环迭代过程中的某一给定值；Ni—当前迭代次数。

式（6）和式（7）自适应更新的思想为：在路径寻优的初期，先将α和β置于最小初值以提高算法的全局搜索能力，避免陷入局部最优；当迭代次数达到P次时，基于式（6）和式（7）自适应调节α和β以避免算法出现停滞和僵局。

3.2 自适应调节信息素挥发率

由式（3）可知，信息素挥发率ρ对信息素的更新起到至关重要的作用。当ρ较大时，之前的搜索路径被蚂蚁选择的概率更高，此时信息素的正反馈作用明显。当ρ较小时，之前的搜索路径效果并不好，此时蚂蚁寻求新的路径的可能性更大，此时算法的全局搜索能力更强，但是收敛速度较低。因此，为了配合式（6）和式（7）的更新，在前期可以选择较大的ρ以弥补前期α和β较小的不足。随着迭代次数的增大，可以由大到小自适应更新ρ以增强算法的全局搜索能力。具体更新为：

式中：ρ0—初始挥发率，取值为接近1的常数。

3.3 改进启发函数的更新方式

蚁群算法具有易于实现、约束条件宽松且具有较好的适用性，但根据3.1和3.2节的分析可知，由于寻优思路简单且基本算法中参数适应性不强，该方法极易陷入局部最优。由式（2）可知，启发函数ηij(t)与路径距离成反比，在智能汽车轨迹规划过程中，约定：

根据式（2）可知，基本蚁群算法中启发函数为：ηij(t)=1/dij(t)，该种更新方式不利于算法的搜索结果快速收敛。为了有效提高算法的一步决策效率，使蚁群向着路径最短的方向进化，这里改进启发函数ηij(t)的更新方式（式（10）），在算法中增加一个权系数用于调节寻优速度。

式中：C—权系数。

3.4 改进蚁群算法流程

根据上述内容，本文改进蚁群算法具体流程可以概括为：

（1）初始化算法参数。分别设置蚁群种群数量n，最大迭代次数Nmax，信息素强度Q，权系数C，以及自适应调节参数αmin，αmax，βmin，βmax和ρ0。设定智能汽车规划路径的出发点和终点。

（2）更新一步状态转移概率。对于每只蚂蚁，根据式（10）计算路径（i，j）的距离，并根据式（1）和式（2）计算转移概率。这里的信息素因子α和启发因子β按照式（6）和式（7）进行自适应更新。在解算每条路径概率之后，选择出一步转移的最佳路径，也即概率最大的路径。

（3）更新禁忌表。对于每只蚂蚁，每经过一个节点后将该节点纳入禁忌表；

（4）搜索全局路径。对于每只蚂蚁，重复（2）和（3），直到到达终点，同时保存每只蚂蚁的全局路径和路径长度；

（5）更新信息素。所有蚂蚁完成路径规划后，基于式（4）～式（6）对每条路径的信息素进行更新，在计算过程中，这里的信息素挥发率ρ按照式（8）进行自适应更新；

（6）循环迭代。将上一步计算的全局信息素反馈到下一次迭代过程中，将所有蚂蚁重新放回出发点，重新进行路径规划，直到达到最大迭代次数。在每次迭代之后，保留每代蚂蚁的最短路径。

（7）算法完成。在完成所有迭代之后，从每代种群中找出最优路径。综上，这里改进蚁群算法的具体流程，如图1所示。

4 智能汽车自主避障仿真实验

4.1 栅格环境模型

为了检验这里改进蚁群算法在智能汽车避障问题中的有效性和可靠性，这里用栅格法将智能汽车避障地图进行分解。采用一定宽度的栅格将汽车行驶的环境进行分割，可以有效检验智能算法的有效性。在栅格环境中，当障碍物存在于某个栅格内时，此时将栅格属性赋值为1，代表该栅格内存在障碍物。当不存在障碍物时，赋值为0。

此外，当障碍物不能完全占满栅格时，采用膨胀法视为完全填充。最后将汽车行驶的地图用包含0和1元素的栅格矩阵来表示，如：

在下文仿真验证过程中，采用标准的（15×15）和（20×20）两张地图开展仿真实验（下文分别称为1号地图和2号地图），两张地图中障碍物的分布有所区别。

4.2 路径规划性能验证

为了说明本文算法的优势，这里的智能车分别采用基本蚁群算法和本文改进蚁群算法两种方法，分别在1号和2号地图中开展仿真实验。在仿真过程中，蚁群数目设定为100，最大迭代次数为200 次，设定αmin为0.3，αmax为0.9，βmin为0.2，βmax为1，ρ0为0.25，C为2.5。中间过渡迭代次数P为80.信息素强度Q为1。信息素初始增量为0。在1号地图中，起始点设置为（0.5，0.5），终点设置为（14.5，14.5）。在2 号地图中，起始点和终点设置为（0.5，0.5）和（19.5，19）。两组实验结果，如图2和图3以及表1所示。

图2 在1号地图中两种方法的对比结果Fig.2 Comparative Results of the Two Methods in Map 1

图3 在2号地图中两种方法的对比结果Fig.3 Comparative Results of the Two Methods in Map 2

表1 实验结果对比Tab.1 Comparison of Experimental Results

图2和图3所示分别为智能车采用传统蚁群算法和改进蚁群算法在1号地图和2号地图中规划的最优路径。由图2可知，在（15×15）栅格环境下，两种方法均能够保证智能车有效规避障碍物并规划出可行路径，但采用改进蚁群算法所规划的路径更加简洁、清晰。在仿真时，每个栅格的长度设定为1，此时传统蚁群算法规划的最优路径长度为30.52，而改进蚁群算法规划的最优路径为26.53，采用改进算法规划的路径节省了13.07%的路程。在更为复杂的2号地图中，两种方法所得的结果，如图3所示。对比图3（a）和3（b）可知，改进蚁群算法所规划的路径更加简洁高效。实际上，传统蚁群算法在2 号地图中所规划最优路径长度为40.56，而改进蚁群算法所规划的最优路径长度为36.58，后者节省了9.81%的路程。

由表1所示实验统计结果可知，改进蚁群算法在平均路径长度、最优路径长度、迭代次数和平均耗时等方面均优于传统蚁群算法，显示出了算法的改良特性。由于改进蚁群算法采用了自适应因子更新方法，能够在实验初期扩大搜索范围、并在实验全程有效加快粒子进化速度，从而提高了算法的全局收缩能力和收敛速度，最终保证了避障路径的最优和最快。

综合以上分析，由于改进蚁群算法在路径搜索初期能够自适应调节信息素因子α和启发因子β，在前期保证了智能车能够在较大范围内进行全局路径规划。而在路径搜索全程通过自适应调节挥发率和信息素函数，实现了算法的快速收敛，进而保证了智能车快速搜索到最短路径。这从图2和图3中的最优轨迹和表1中的收敛特性也能得以体现。仿真结果验证了这里所提智能汽车主动避障改进蚁群算法的有效性和平滑性。

5 结论

这里针对智能汽车主动避障路径规划问题，提出了一种自适应蚁群智能避障方法。首先，在分析传统算法缺陷的基础上，给出了信息素因子、启发因子、信息素挥发率以及启发函数的更新算法以扩大算法的全局搜索能力、提升算法的收敛速度并提高路径规划质量。智能汽车避障实验验证表明：（1）所提方法能够有效规划智能汽车避障路径，并有效加快算法的收敛速度，降低迭代次数；（2）与传统蚁群算法相比，这里算法能够有效提升路径规划质量，显著降低路径规划长度，增强了算法的可靠性和平滑性。