基于ACO-PSO 算法的变电站巡检机器人路径规划研究

（郑州轻工业大学 电气信息工程学院，郑州 450002）

0 引言

随着科技的发展，人工智能、机器人开始逐渐步入人们的视野，智能化与自动化也开始应用于实践中。在很多场合机器人已经开始代替人类从事一些危险的工作，以变电站智能巡检机器人为例，利用变电站智能巡检机器人定期自动检查确保设备能够稳定运行，能够很好地保证安全性和高效性。

路径规划是移动机器人的一个重要研究方向，是指在有障碍物的情况下，按照规定的要求找到一条历时尽可能短、路径尽可能平滑的从起点到终点的无碰撞轨迹[1]。路径规划使得机器人能的对静态及动态环境作出综合性判断，进行智能决策。

机器人路径规划的传统算法有BFS（广度优先搜索），DFS（深度优先搜索），Dijkstra（迪杰斯特拉），A*，D*，D*lite 等，不同的算法有着各自的优缺点。随着科技的发展，越来越多新颖的算法也运用到机器人路径规划这一方向中，例如快速扩展RRT（随机树）算法、ACO（蚁群）算法、SA（模拟退火）算法、APF（人工势场）等，这些智能算法可以很好地解决机器人的路径规划问题。

针对上述算法也有很多人结合其他方法提出了很好的改进方向与方法。文献[2]利用Dikstra 进行机器人路径规划，并进一步用SA 对路径进行优化，提升Dikstra 的求解速度。文献[3]介绍了蚂蚁的相遇策略、蚂蚁的惩罚策略，并结合GA（遗传）算法对ACO 算法进行改进，极大避免了局部最优问题，但它也有着一定的缺点，庞大的计算使得求解速度较慢。文献[4]介绍了ACO 算法的几种典型系统，例如最大-最小蚂蚁系统、带精英策略的蚂蚁系统等，并将机器学习中的OBL 思想引进，来减少搜索时间。文献[5]将贪婪交叉算子应用于ACO 算法中，在选择下一节点的轮盘赌算法时，通过实验交叉操作来加快最优解的求解速度。文献[6]通过设置初始信息素、信息素的挥发机制与调整自适应路径长度，提高了求解出最优解的收敛速度。文献[7]有着不同的思路，除了针对ACO 算法的不足提出改进之外，还对栅格地图进行改进，通过对栅格地图的旋转提高了算法的运行速度和搜索能力。

本文分析应用于机器人路径规划的ACO 算法的特征，针对ACO 算法的迭代次数多、收敛速度慢、容易陷入局部最优和出现死锁状态等问题，采用蚂蚁回退策略并结合PSO（粒子群优化）算法提出了ACO-PSO 算法，可以提高系统的利用率与鲁棒性，加快收敛速度，同时将其运用到机器人路径规划中，并通过仿真实验来进行验证。

1 路径规划模型

本文探究的是机器人的路径规划问题，试图利用ACO 算法研究出机器人的最优路径规划的算法。

通常情况，机器人在二维环境中进行工作，在探究机器人路径规划的开始便是根据栅格法构建符合实际工作环境的栅格矩阵地图。栅格法的基本思想是将一块实际的场地划分成面积大小相等的小区，每个小区称为一个栅格，栅格面积的大小一般由机器人车体大小来决定[3]。栅格法的目的就是建立一个数字地图，在地图中存储机器人的可运动路径及障碍物信息。在给定机器人初始位置和目标位置后，使用搜索算法生成若干条由一组栅格坐标组成的路径[8]。

构建的栅格矩阵为01 矩阵，其中0 表示所在栅格无障碍，1 则表示所在栅格有障碍物存在，可以得到栅格地图如图1 所示。

图1 栅格地图

在任意一个N×N 的栅格环境矩阵，对每个栅格进行编号，自上而下、从左到右总体编为1，2，3，…，N，以左下角为坐标系原点建立坐标系，从而计算出第n 个栅格节点的坐标，便于计算节点之间的距离。具体转换为：

式中：a 表示每个栅格的边长；x，y 分别为第n个栅格的横坐标与纵坐标。

知道各个节点的坐标位置，便可以计算两两节点的距离dij。任意两个节点的距离为：

在对机器人工作环境进行环境建模之后，便需要考虑机器人的移动方向问题，采用的是八叉树搜索策略，即机器人在搜索过程中可以朝附近八个方向的相邻栅格之间的移动，如图2 所示。

图2 移动方向

2 ACO 算法

2.1 传统ACO 算法

ACO 算法是一种蚂蚁在寻找食物过程中发现路径的行为并用来寻找优化路径的概率型算法。蚂蚁在寻找食物源的时候，会在走过的路径上释放一种叫信息素的激素，使一定范围内的其他蚂蚁能感知环境和食物的存在和强度,通过这些信息素了解自己运动的方向。相等时间内较短路径上的信息量就遗留得比较多，则选择较短路径的蚂蚁也随之增多，利用的便是信息正反馈的特性[9]。

在ACO 算法中，较为重要的便是对下一个节点的选择，一般采用轮盘赌法来进行选择，假设搜寻k 次的蚂蚁从节点i 运动到j 的概率为，其中节点j 不在禁忌表中，否则为0，则的计算公式为：

式中：τij表示在t 时刻节点i 到节点j 之间的信息素浓度，其对蚂蚁路径的选择有很大的影响，浓度越高，蚂蚁选择该节点的可能性就越大。表示的是节点i 与节点j 的启发式信息，其大小由节点i 到终点的距离决定，代表距离对蚂蚁路径选择的影响。

启发式因子α 表示信息素对蚂蚁路径选择的影响程度，α 越大，蚂蚁蚂蚁选择以前走过路径的可能性就越大，搜索的全局搜索能力就越弱。期望启发式因子β 反映了路径长度在蚁群搜索中的重要程度，β 越大，蚂蚁在某个局部点选择距离短的路径的可能性越大[4]。所有的蚂蚁到达终点后，对各个路径的节点的信息素浓度进行更新，更新信息素的公式为：

式中：Δτ 的更新模式有三种，它们各有自己的特色，分别为蚁周模型、蚁量模型、蚁密模型。这三种模式中，蚁周模型利用的是全局信息，蚁量模型和蚁密模型利用的则是局部信息[10]。蚁周模型的信息素增量与蚂蚁搜索的路径相关，即公式（5）；蚁量模型的信息素增量与路径的距离相关，即公式（6）；而蚁密模型的信息素增量是固定的，其大小与距离等要素无关：

本文采用的信息素更新模式为蚁周模型，具体公式为：

2.2 局部最优

对于很多大型系统或复杂的问题，一般的算法都着眼于从局部展开求解，以此来减少计算量、降低算法复杂度，这就导致局部最优在多数算法都存在，而且很难判断，就算判断出来也很难避免局部最优解。

ACO 算法存在着局部最优的问题，蚂蚁路径搜索过程中，会在搜索过后的路径留下信息素，蚂蚁会在相对最优的路径上留下更多的信息素，越多的信息素会吸引越多的蚂蚁选择该路径，搜索的随机性被限制，使得局部最优出现的可能大大增加。

2.3 死锁状态

在ACO 算法中，蚂蚁在搜寻路径的过程中很容易陷入“胡同”中，出现死锁现象。假设一个集合Wk，集合Wk中包含着蚂蚁k 下一个节点的选择，在还未达到终点时，如果集合Wk中并未包含任何节点，那么便可能陷入死锁状态，使得算法对环境的复杂程度和健壮性不够强。

一般陷入死锁状态有两种情况，一种是陷入凹型区域，见图3（a），当蚂蚁在节点18 时，没有可以选择的下一节点；另一种是蚂蚁因自己走过的节点使得其陷入死锁，见图3（b），这种情况更为常见。

图3 死锁状态

2.4 迭代次数过多

ACO 算法由于在初期信息素匮乏，选择下一个节点时倾向于随机选择，虽然可以找到全局最优解，但收敛速度较慢，尤其当参数设置不合适时，就要较长时间才能完成搜索，这样会使整个系统运算量增加，迭代次数过多，收敛速度较慢。

3 PSO 算法

PSO 是一种基于种群的随机优化技术。粒子在解空间中运动，通过跟踪个体极值Pbest和群体极值Gbest更新个体位置，粒子每更新一次位置，就计算一次适应度值，并且通过比较新粒子的适应度值和个体极值、群体极值的适应度值更新个体极值Pbest和群体极值Gbest位置。

假设在多维空间中存在许多粒子，它们在多维空间中来回运动，假设它们在多维空间中搜寻食物，群体中的每个粒子都有着自己搜寻的食物的位置Pbest，但同时整个群体也有一个更好的食物的位置Gbest，每一个粒子都需要考虑两个位置的关系，它们的速度矢量也在不断变化。同时群体中的每个成员通过学习其自身的经验和其他成员的经验来不断改变其搜索模式。

PSO 算法的基本思想是：在优化问题中对于其解空间，随机初始化一群粒子作为目标函数的可行解，定义适应度函数来描述每个解的优劣。然后每一个粒子在解空间内随机运动，粒子的运动位置由粒子的速度决定，而粒子自身找到的最优解与粒子群找到的最优解会影响粒子的速度[11-14]。PSO 算法的速度与位置的更新公式为：

PSO 作为一种随机的、并行的优化算法，具有不要求被优化函数具有可微、可导、连续等性质，收敛速度较快，算法简单，容易编程实现。但对于离散的优化问题处理不佳，在搜索中很容易出现早熟收敛，并且在处理复杂的多峰收缩问题上表现出局部搜索能力较差，而且易陷入局部解[15]。

4 ACO 算法的改进

4.1 提升全局搜索

ACO 算法容易陷入局部最优，不能很好地通过全局搜索找到全局最优解。解决局部最优的最好方法便是增加算法的随机性，如果缺乏随机性，那么陷入局部最优的概率会大大增加，为了获得找到最优解的更大期望值，算法中一定要有足够的随机性[16]。本文对信息素更新公式与信息素增加进行改进，加入随机变量。改进后的信息素更新公式为：

改进后的信息素增量Δτij的公式为：

4.2 死锁改进

对于蚂蚁处于死锁状态，有不同的解决方法，可以利用惩罚因子对死锁路径上的信息素进行惩罚，可以对死锁进行凸型处理，可以采取信息素渐灭方式将该路径的信息素清零，也可以采用回退策略，即当蚂蚁无路径搜索时释放禁忌表、回退一步等多种方法[17-20]。

本文采用的是回退策略，可以很好地使蚂蚁脱离死锁状态。以图3（a）为例，蚂蚁在节点18处陷入死锁，蚂蚁走过的节点在禁忌表中已经进行设置声明，在节点18 处蚂蚁处将节点18 在禁忌表中声明，同时将已经走过的上一个节点13 在禁忌表中的位置重置，返回到上一个节点13，再按此步骤返回到节点3，这样便使得蚂蚁摆脱死锁。死锁改进前后迭代次数的比较如图4 所示。

图4 改进对比1

4.3 迭代优化

如果仅仅解决蚁群的死锁问题，蚂蚁在进行回退策略之后，需要重新选择节点，选择下一节点的次数增加，运算量增加，会使得算法的迭代次数增加，降低算法的收敛速度。

为了提升算法的运行速度，便利用PSO 算法对ACO 算法中下一个节点的选择与信息素的更新进行改进，增加一定的指向性。文献[6]也是采用ACO 算法与PSO 算法相结合的方法，但它先用PSO 算法进行粗略的搜索，再利用ACO 算法进行更为细致的检索，从而找到最优路径。但它的缺点很明显，两种算法的先后使用使得计算量较大，进而导致收敛速度较慢。

本文是用PSO 算法对ACO 算法中轮盘赌法选择下一节点这一步骤进行优化，加快选择速度，增加选择精度。

轮盘赌法便是利用各个可选择项的积累概率和随机数来进行选择的方法，本文的各节点选择的概率由公式（3）可以得到，但它有着一定的局限性，没有从全局进行考虑。文献[21]考虑到了这一问题，加入了导向函数，并得到导向系数，将其加入公式（3），得到新的计算公式。

本文定义了一个新的信息素，命名指向信息素φ，它代表蚂蚁受终点与可选择的下一节点的影响，从全局进行考虑。指向信息素对下一个节点的影响在于增加下一次选择下一节点中信息素最高的节点的信息素含量，增加其选择的概率。而在何种情况下增加节点信息素含量，便利用到了PSO 算法。

将可选择的下一节点中信息素浓度最高的节点坐标作为PSO 算法中的局部最优坐标Pbest，将终点坐标作为PSO 算法中的全局最优坐标Gbest。在二维平面中，按照PSO 算法中公式（9）求得在某一节点速度的方向，速度是矢量，可以得到速度的方向，并将该方向整理为在坐标系中的角度φ，便可得到其指向的节点A。

利用方向与轮盘赌法的结果进行结合，方向指向的可选的节点A 与轮盘赌法选择的可选节点B 是否相同，如果相同便在节点A 增加指向信息素φ，反之便不增加，这样会使得蚂蚁整体向终点移动，减少迭代次数。

针对改进死锁后的ACO 算法与整体改进后的迭代次数对比如图5 所示。

4.4 ACO-PSO 算法

整理融合针对ACO 算法缺点的几处改进，并归纳为ACO-PSO 算法，利用PSO 来改善ACO算法，可减少算法的迭代次数，提高算法的收敛速度。

图5 改进对比2

具体的步骤如下：

（1）利用栅格法构建环境矩阵并求得对应的邻接矩阵。对蚁群与粒子群的各个参数进行赋值，包括蚁群出动次数k 与蚂蚁个数M，起点与终点，启发式因子α 与期望启发式因子β，初始信息矩阵η 等，粒子粒子群的初始信息包括初始速度v，学习因子c1与c2，全局最优Gbest的坐标等。

（2）派出蚂蚁进行全图搜索，避开障碍物，搜索可选择的下一节点的位置，同时判断所有可选择节点是否已经被蚂蚁走过，即是否在禁忌表中，去除禁忌表中的节点，得到可选择节点集合W。

（3）对目前所在的节点w 进行判断，如果节点w 与终点相同，便代表搜素结束；反之搜素继续。然后对集合W 包含的个数n 进行判断，如果n=0，则代表蚂蚁陷入死锁，执行蚂蚁回退策略；如果n≠0 则继续后续步骤。

（4）利用轮盘赌法来选择下一个节点，并利用PSO 算法来对合适的节点添加指向信息素φ，并将选择的下一个节点设置为当前节点w，将走过的节点全部包含在禁忌表中，防止路线重复。

（5）记录各个蚂蚁的路线及其路线长度，并按照公式对信息素矩阵η 进行更新。

（6）然后不断的重复步骤2—5，直到运行结束。最终得到最优的路线，便是最优解。

ACO-PSO 算法的具体流程如图6 所示。

5 仿真分析

本文采用MATLAB 2019 作为仿真工具，选取蚂蚁的数目为50，出动次数为100，设置相关参数，如α=1，β=7，ρ=0.3 等。假设传统与改进两种蚁群算法的各个参数相同，便于进行实验结果的比较与分析。得到机器人最优路径轨迹，如图7所示。

图6 算法流程

图7 路径轨迹

两种ACO 算法得到的最优路径轨迹图是相同的，但两者的速度与迭代次数有差异，如图8所示。

图8 迭代次数比较

本文对传统ACO 算法的不足逐步进行改进，先对死锁改进，再在死锁改进的基础上再改进，传统ACO 算法在运行时间上要快于改进后的ACO 算法，但迭代次数也多于最终改进后的，总体而言，改进后的ACO 算法要优于传统算法，对比结果如表1 所示。

表1 仿真比较

6 结语

本文基于栅格法构建了环境模型，对解决机器人路径规划的ACO 算法进行一定的优化与改进。针对ACO 算法中存在的死锁、局部最优、迭代次数过多、收敛速度过慢等问题，逐一加以解决并整合得出最终的改进算法。当蚂蚁处于死锁状态时，采用蚂蚁回退策略使其返回上一个节点；利用PSO 算法中粒子速度的方向对ACO 算法进行改进，对在一定方向的已选择的栅格节点增添信息素，从而减少了迭代的次数，提高此类算法的收敛速度；同时在信息素的更新中，增加了算法的随机性，扩大了蚂蚁路径搜索的范围，减少陷入局部最优的可能性。通过仿真结果进行分析，可以看出改进后的ACO 算法在运行时间、迭代次数等方面均有一定程度的改善，增加了其搜索范围与准确度，使其在任意工作环境下都可以很快地搜索出最优路径。