天津职业技术师范大学电子工程学院，天津

收稿日期：2022年8月15日；录用日期：2022年9月13日；发布日期：2022年9月21日

摘要

传统蚁群算法由于参数固定化，在机器人路径规划中，无法发挥算法的优越性。本文提出了一种改进的蚁群算法，用于提高算法在路径研究上的效率。通过分析蚁群各阶段的特点，有针对性地调整信息素因子大小，提高算法的性能。引入自适应平衡因子对启发式信息函数进行改进，维持算法平衡。利用随机概率触发随机状况，提高系统的抗干扰能力。通过提出前瞻概率调整蚂蚁节点状态转移方式，扩大搜索空间，提高路径规划的整体效率。实验仿真采用复杂度不同的地图来对比改进前后的蚁群算法。结果表明，改进后的算法不仅提高了算法性能，还可以稳定应对更为复杂的环境，为研究路径规划提供了参考。

关键词

改进蚁群算法，机器人，路径规划

Research on Improved Ant Colony Algorithm in Robot Path Planning

Fankai Chen, Shixin Li^*, Baosheng Li, Chen Liu, Yue Meng

College of Electronic Engineering, Tianjin University of Technology and Education, Tianjin

Received: Aug. 15^th, 2022; accepted: Sep. 13^th, 2022; published: Sep. 21^st, 2022

ABSTRACT

Due to the fixed parameters of the traditional ant colony algorithm (ACA), the advantages of the algorithm cannot be exerted in the robot path planning. This paper proposes an improved ACO to improve the efficiency of the algorithm in path research. By analyzing the characteristics of each stage of the ant colony, the size of the pheromone factor is adjusted in a targeted manner to improve the performance of the algorithm. An adaptive balance factor is introduced to improve the heuristic information function to maintain the balance of the algorithm. Use random probability to trigger random conditions to improve the anti-interference ability of the system. By proposing forward-looking probability to adjust the state transition method of ant nodes, the search space is expanded and the overall efficiency of path planning is improved. The experimental simulation uses maps with different complexity to compare the ant colony algorithm before and after improvement. The results show that the improved algorithm not only improves the performance of the algorithm, but also can stably deal with more complex environments, which provides a reference for the study of path planning.

Keywords:Improved Ant Colony Algorithm, Robot, Path Planning

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着人工智能的快速崛起，各行业迎来智能制造时代，机器人作为人工智能的主力军，应用在生产等各个领域。机器人移动的最优路径可以提高生产效率，节约生产成本，而路径规划的关键在于路径搜索。在路径搜索算法上，有传统的算法如人工势场法 [1]、模糊逻辑算法 [2] 等，也有启发式路径优化算法如A*算法 [3]、Dijkstra算法 [4] 等，还有如遗传算法 [5]、蚁群算法 [6] 等群智能仿生优化算法。

本文就是以蚁群算法为基础，对传统算法在路径规划上存在的不足进行优化改进。通过灵活调整蚁群算法中信息素影响因子大小，优化信息函数和状态转移概率计算方式，实现蚁群高效、准确地规划路径。

2. 传统蚁群算法

蚂蚁在搜索食物过程中，通过分析状态转移概率来对蚂蚁行动路线进行选择。状态转移概率主要由信息素浓度和每条路径上启发式信息组成 [7]。蚂蚁m (m = 1, 2, …, M)在t时刻从当前节点i移动到下一节点j的概率 $P_{ij}^m\left(t\right)$ 如公式(1)所示。

$P_{ij}^m=\{\begin{array}{cc}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}{{\displaystyle \underset{S\subset T_{allowed,m}}{\sum }{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}}，& j\subset T_{allowed,m}\\ 0，& 其他\end{array}$ (1)

式中 ${\tau }_{ij}\left(t\right)$ 为t时刻节点i到节点j之间路径上的信息素；α为信息启发式因子；β为期望启发式因子； $T_{allowed,m}$ 表示蚂蚁m下一时刻可以移动的栅格集合； ${\eta }_{ij}\left(t\right)$ 为t时刻两节点之间启发式信息，与两节点之间的距离呈负相关。

3. 改进的蚁群算法

3.1. 信息素因子动态调整

在蚁群觅食过程中，信息素浓度决定着蚂蚁的行动路线，影响着算法寻找最优路径的效率，信息素浓度主要受信息素影响因子( $\alpha ,\beta ,\rho$ )影响 [8]。由于传统算法中影响因子参数固定化，无法发挥蚁群算法的最优状态。本文针对蚁群在不同迭代阶段信息素分布状况不同，按阶段动态适应性调整影响因子。

3.1.1. 信息素启发式因子调整

信息素启发式因子α和期望启发式因子β影响着蚂蚁路径的选择程度 [9]，因子α主要用来描述当前路径上信息素浓度对路径选择的影响程度，因子β用来描述启发信息对路径选择的影响程度。本文根据不同时刻蚁群搜索状况，采用公式(2)分阶段调整信息素启发式因子的值。

$\{\begin{array}{c}\alpha ={\alpha }_{{}_1}^w\\ \beta ={\beta }_1^v\end{array}$ (2)

式中 ${\alpha }_1$ 和 ${\beta }_1$ 表示启发式因子的初始值， $w$ 和 $v$ 为信息素因子动态调节指数。根据不同迭代次数路径上信息素分布特点和路径长度最优的状况，可以分为三个阶段，迭代初期中期和后期，不同迭代阶段特点比较明显，所以采用幂指函数对因子进行动态调整。迭代初期地图上信息素浓度较少，以节点启发式信息为主导，通过 $w\in \left(0,1\right)$，$v\in \left(1,2\right)$ 来实现前期搜寻最优路径；迭代中期，地图上信息素积累到一点浓度，不同路径上信息素差异显著，可以通过 $w\in \left(1,2\right)$，$v\in \left(0,1\right)$，以信息素浓度为主导方向，提高算法的收敛速度；迭代后期，信息素浓度呈现一定规模，容易陷入局部最优情况，可以通过 $w\in \left(0,1\right)$，$v\in \left(1,2\right)$ 实现减弱信息素浓度对路径搜索的影响，避免陷入局部最优。

3.1.2. 信息素挥发因子调整

信息素挥发因子ρ的取值决定着路径上信息素挥发的程度。ρ过小时，导致各路径上残留的信息素过多，造成过度搜索无效路径，影响收敛速度；ρ过大时，在排除搜索无效路径的同时，有效路径也会受到影响，干扰最优路径的搜索 [10]。在保证算法收敛性的情况下，利用等比数列的思维对挥发因子实现动态逐次递减如式(3)，后期通过增大搜索范围的方式，对信息素挥发因子进行自适应调整。

$\rho \left(k\right)=\{\begin{array}{cc}{\rho }_{\max }\times g^k,& \rho \left(k-1\right)>{\rho }_{\min }\\ {\rho }_{\min },& 其他\end{array}$ (3)

式中 ${\rho }_{\min }$ 为信息素挥发因子最小值， ${\rho }_{\max }$ 为最大值，g是挥发因子变化程度系数，为常量，k为当前蚂蚁迭代次数。

3.2. 改进启发式信息函数

在传统蚁群算法中，启发式信息函数η_ij只考虑两节点之间的距离，这导致算法早期的全局性较差，为提高启发式搜索效率，在原有的基础上考虑了当前节点i和目标节点E之间的距离。算法后期为了平衡全局搜索能力和收敛速度，引入了自适应平衡因子。改进后启发式信息函数如式(4)所示。

${\eta }_{ij}\left(t\right)=\frac{\epsilon }{h*d_{ij}+\left(1-h\right)*d_{iE}}$ (4)

式中h是距离比例因子，为常数， $d_{ij}$ 表示节点之间的欧式距离， $d_{iE}$ 表示与目标节点之间的距离。ε为自适应平衡因子利用正态分布函数进行动态调整，算法前期ε接近于1，可以强化启发式信息的作用，提高收敛速度，随着迭代次数的增加，ε逐渐小于1，减少启发式信息的干扰，增强全局搜索能力。ε如式(5)所示。

$\epsilon ={\text{e}}^{-2{\left(\frac{k}{K}\right)}^2}$ (5)

式中k为当前迭代次数，K为迭代总次数。

3.3. 改进蚁群状态转移概率

传统蚁群算法利用信息素浓度和节点距离长度计算状态转移概率。本文引入了当前节点前瞻概率 $F{p}_{ij}$ 这个概念，在选择下一个节点的问题上，考虑了下一个节点的位置信息。一个节点可选路径有8条，随着障碍物的增加，对应可选路径减少，前瞻概率就是下一个节点的可选路径占比。表达式如式(6)所示。

$F{P}_{ij}=\frac{N-N_{ob}}{N}$ (6)

式中 $N_{ob}$ 表示节点j周围障碍物的数量，N表示周围总路径数量。前瞻概率的加入可以让蚂蚁更合理的选择下一个节点，改进后的状态转移概率P如式(7)所示

$P_{ij}^m=\{\begin{array}{cc}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }F{P}_{ij}}{{\displaystyle \underset{S\subset T_{allowed,m}}{\sum }{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }F{P}_{ij}}}，& j\subset T_{allowed,m}\\ 0，& 其他\end{array}$ (7)

3.4. 随机情况

为了提高系统的鲁棒性和路径规划的可靠性，本文在蚁群算法对机器人的路径规划过程中加入了随机情况，当满足随机概率触发条件时，算法的相关影响因子( $\alpha ,\beta ,\rho$ )变成随机的。当算法陷入局部最优或某种异常情况时，随机概率的加入有利于突破这种算法局限性；当算法正常时，随机情况可以提高算法的抗干扰性，稳定规划最优路径。

3.5. 改进蚁群算法步骤

改进后的蚁群算法步骤如下，算法流程图如图1所示。

步骤一生成栅格地图，利用二维数组生成栅格地图模拟真实环境。

步骤二初始化蚁群参数，设定算法影响因子( $\alpha ,\beta ,\rho$ )初始值，选择起点位置和目标节点，确定蚂蚁数量M和迭代次数K等参数。

步骤三根据当前迭代数k值给启发式因子指数 $w$ 和 $v$ 赋值，是否触发随机状况，触发则给影响因子赋随机值，初始化蚂蚁数 $m$ 为1。

步骤四蚂蚁根据状态转移概率公式和轮盘赌方法进行路径节点选择，局部信息素更新，禁忌表更新。蚂蚁数 $m$ 加1。

步骤五判断蚂蚁是否全部完成路径规划，没有全部完成则返回步骤四。

步骤六全局信息素更新，迭代次数k加1。

步骤七判断是否完成所有迭代次数，没有则返回步骤三。

步骤八输出最优路径，绘制迭代收敛曲线，完成路径规划。

4. 实验仿真和结果分析

4.1. 栅格地图模型

在路径规划研究中，因为栅格法简单有效，对障碍物的适应性强，并且可以降低环境搭建的复杂性，所以本文采用该方法搭建机器人的工作环境模型。在网格中，0表示自由区域用白色填充，1表示障碍区域用黑色填充，利用直角坐标系和序列号相对应的方法来生成栅格地图，生成地图如图2所示。每个网格都有唯一一个序列号和对应的直角坐标信息，网格序列号和位置坐标之间的关系转化如式(8)所示。

图1. 改进蚁群算法流程图

图2. 20 * 20栅格地图

$\{\begin{array}{c}{x}_i=\mathrm{mod}\left(i,N_x\right)-0.5\\ y_i=N_y+0.5-ceil\left(\frac{i}{N_y}\right)\end{array}$ (8)

式中 $\left(x_i,y_i\right)$ 表示节点 的位置信息， $N_x$ 和 $N_y$ 表示栅格地图的列数和行数。

4.2. 算法初始化参数设置

本文采用MATLAB R2019a对算法进行试验仿真。算法迭代次数为100次，设定蚂蚁数量为50只，相关影响因子设定为 $\alpha$ = 3， $\beta$ = 6， $\rho$ = 0.3，地图单位长度设定为1 cm。改进后的算法和传统算法在初始值设定上保持一致性，有利于分析两种算法的差异性和可信度。

4.3. 路径规划结果

为了更好地比较两种算法，选取了20 * 20和30 * 30两种复杂度不同的栅格地图，传统蚁群算法和改进后的蚁群算法均采用上述设定的初始值进行实验仿真。其中30 * 30栅格环境下仿真结果如图3所示，将两种栅格环境下的最优路径长度和收敛迭代次数结果记录在表1中。

表1. 两种环境下仿真结果记录

图3. 30 * 30栅格环境下两种算法最优路径和收敛曲线

实验结果表明，两种算法均可以完成从起点到终点的路径规划，证明了改进后蚁群算法的可行性。由图3可知，两种算法随着迭代次数的增加，最优距离都出现明显减少，较传统蚁群算法而言，改进后的算法迭代初期时最优路径长度明显较短，且收敛速度更快。在20 * 20栅格环境1中，虽然传统算法和改进后的算法最优路径长度一样都为30.9706 cm，但是收敛迭代次数减少了7次，收敛速度提升了140%。在复杂环境2中，改进后的算法无论在最优路径长度上还是收敛速度上都有明显的优势，最优路径长度缩短了14.7%，收敛速度提升了133%。仿真实验结果表明，改进后的蚁群算法较传统算法在路径搜索能力和收敛速度上有显著提升，在算法的稳定性方面也更具优势，满足机器人对路径规划的要求。

5. 结论

本文改进的蚁群算法，根据不同阶段蚁群特征动态调整了算法信息素影响因子，解决了传统蚁群算法因为固定值造成的局部最优和收敛速度慢的问题。并且优化了状态转移概率和启发式函数，使得蚁群算法的搜索过程更加合理高效，同时引入了随机情况，提高了系统的灵活性和抗干扰能力。通过和传统算法的实验对比分析，改进后的蚁群算法在满足机器人路径要求的前提下，可以高效、准确地规划最优路径。

文章引用

陈范凯,李士心,李保胜,刘 宸,孟 玥. 基于改进蚁群算法在机器人路径规划上的研究
Research on Improved Ant Colony Algorithm in Robot Path Planning[J]. 计算机科学与应用, 2022, 12(09): 2120-2127. https://doi.org/10.12677/CSA.2022.129215

参考文献