基于IACO-ABC 算法的变电站巡检机器人路径规划

薛 阳，俞志程，吴海东，张 宁

（上海电力大学 自动化工程学院，上海 200090）

0 引言

随着我国科学技术不断发展，自动化水平不断提高，变电站无人值守模式逐渐成为变电站监控和保护的主流趋势。变电站巡检主要是对变电站内部设备包括仪器仪表等进行巡检，通过定期检查确保设备能够稳定运行。采用机器人进行自动化巡检，既能够保证安全性和高效性，又能够克服传统人工变电站巡检所存在的一些问题和缺陷，而巡检机器人的路径规划则是机器人导航的关键技术之一[1]。

路径规划问题是指在存在障碍物的情况下，按照规定的要求，找到一条历时尽可能短、路径尽可能平滑的从起点到终点的无碰撞轨迹[2]。在上述问题中，首先需要考虑的是要找到实现不碰撞障碍物的轨迹，然后通过智能算法来判断筛选满足指标的最优轨迹[3]。变电站的监测点即检查点是固定点，也就是说机器人要到达指定的位置完成检查工作，可见变电站巡检机器人的路径规划为全局路径规划[4]。

研究者们提出了不同算法来解决各种环境下的路径规划问题。机器人路径规划应用较普遍的算法是人工势场法，如文献[5]利用栅格法建立工作环境并且对传统的ACO（蚁群优化）算法进行改进，通过仿真表明该算法收敛速度快且优化性能良好，但是算法所用迭代次数相对较高，优势不够明显。RRT（快速扩展随机树）算法是另外一种常用的机器人路径规划算法，该算法可高效地搜索高维空间来获得解，其搜索效率得到了研究者们的青睐，文献[6]提出改进的RRT 算法以提高路径规划的质量，缩短机器人到达目标点运动时间，但由于随机性较高，导致了算法的不确定性。近年来学者提出了多种仿生智能优化算法，并在机器人路径规划领域得到了发展，如：文献[7]将改进的Dijkstra 算法与模拟退火算法相结合，应用到变电站智能巡检机器人的全局路径规划中，可实现可靠运行，但面对复杂环境时仍然无法高效地完成规划任务；文献[8]为了提高传统ACO算法在实现路径规划时的收敛速度和效率，并且解决传统算法易陷入局部最优的问题，提出蚁群-粒子群组合优化算法，虽然能成功避免算法陷入局部最优的情况，但由于计算量较大导致收敛速度较慢。

本文根据机器人路径规划的特征，以ACO算法为基础，针对其全局寻优能力差和搜索性能弱等缺点，结合ABC（人工蜂群）算法，提出IACO-ABC（改进蚁群-蜂群融合）算法，并将其应用到变电站机器人路径规划中，以提高系统的鲁棒性以及在复杂工作环境下的路径规划能力，并通过仿真实验进行了验证。

1 ACO 算法与ABC 算法原理

1.1 ACO 算法的改进

ACO 算法模拟蚂蚁在大自然中觅食时发现路径的行为，是一种用来寻找优化路径的概率性算法[9]。在该算法中，蚂蚁会在蚁穴和食物之间往返的过程中留下一种称为信息素的关键信息，蚂蚁们会优先寻找并且往返于最短的路径，因此越优的路径中留下的信息素就越多，进而吸引蚁群中的大多数蚂蚁聚集来此路径[10]。当蚂蚁遇到障碍物时，会首先寻找周围信息素浓的地方，若周围没有信息素存在，那么蚂蚁会随机选择路径，避开障碍物[11]。

为了解决ACO 算法易陷入局部最优的问题并扩大搜索空间，提高搜索结果的多样性，许多专家学者针对不同应用场景提出了多种改进的ACO 算法，如文献[12]的相遇ACO 算法、文献[13]的奖惩ACO 算法等。本文在此基础上提出一种IACO（改进的蚁群优化）算法，其基本思想为：在初始位置初始化一群蚂蚁，蚂蚁们按照状态转移概率对下一节点进行选择和移动，朝着最后的目的地出发[14]。整个蚁群系统采取确定性选择与随机性选择相结合的选择策略以避免出现停滞现象，且状态转移概率会在蚁群搜索最优路径的过程中动态地变化。当位于地点i 的蚂蚁随机数q≤q0（q0为算法参数）时，按照式（1）前往下一个地点j；当q＞q0时，按照状态转移概率，利用轮盘赌法确定蚂蚁下一个要去的地点。

式中：i 为可行栅格以及周围8 个方向上相邻栅格的节点；为信息素，α 为信息启发式因子；为启发值，β 为期望启发式因子；J 为式（2）所计算出的概率；pij为方格i 到下一个方格j 的概率；τij为路径（i，j）上的信息素浓度；ηij为方格i 转移到方格j 的期望程度；A 为此时蚂蚁k 下一步允许选择的方格集合。

信息素只针对每次循环中找到最优路径的蚂蚁进行更新，更新规则如下：

式中：ρ 为信息素挥发系数；Q 为信息量增加强度；Lk（t）为第k 只蚂蚁在本次循环中所走路径的总长度。

当满足迭代次数，蚂蚁构建的当前最优路径输出为最终所得的解。

1.2 ABC 算法的改进

ABC 算法是受蜜蜂采蜜行为的启发而提出的一种新型群智能优化算法，该算法被广泛应用于许多领域来解决最优化问题[15]。ABC 算法将工作蜂群分为雇佣蜂与未雇佣蜂，而未雇佣蜂又分为观察蜂和侦察蜂，每个族群分工不同，各司其职。雇佣蜂开发对应的蜜源并传递相应的信息给观察蜂，每个蜜源的位置代表问题的一个可能解，蜜源的花蜜量对应于相应的解的适应度[16]。侦察蜂负责寻找更好的蜜源，而观察蜂根据从雇佣蜂得到的信息，选择自己认为好的蜜源并进行开采，若观察蜂发现蜜源质量并不理想，放弃当前蜜源，转为侦察蜂，继续寻找更好的蜜源[17]。

通过分工合作，蜜蜂们能够很快发现最好的蜜源，当侦察蜂观察到陷入局部最优时，可随机搜索其他可能的蜜源[18-19]。该算法具有强大的探索能力，并具有一定的解决算法陷入局部最优的处理方法，且蜜蜂在找寻最优蜜源的这个过程与机器人在路径规划上有很大的相似度，所以应用ABC 算法解决巡检机器人的路径规划问题有着比较好的效果。

标准ABC 算法中，与第j 个蜜源相对应的雇佣蜂依据式（5）寻找新的蜜源：

式中：j=1，2，…，K，雇佣蜂与观察蜂的个数均为K；d=1，2，…，D，D 为维数；为新蜜源位置；xjd为当前位置；φjd为区间[－1，1]上的随机数；q≠j。

受到差分进化算法的启发，文献[20]提出改进雇佣蜂寻找新蜜源的公式来提高算法的局部搜索能力，本文在此基础上提出自适应位置更新公式，雇佣蜂随机选择两个不同个体以及当前最佳个体来寻找新的蜜源，充分利用种群个体信息来提高种群搜索过程中的多样性，即：

式中：xgbest为当前最优解；xr1d与xr2d为随机选择的不同个体。等式右边第1 项为当前位置；第2项为随机位置差值所得，代表了蜜蜂的全局搜索能力；第3 项为当前最优对当前位置的影响；φ由个体之间的适应度值来确定。

式中：F 为[0，1]之间的随机数；fr1，fr2，fb分别为xr1d，xr2d，xgbest对应的适应度值。

每个观察蜂依据概率选择一个蜜源，概率公式为：

式中：fj为可能解Xj的适应度值。

对于被选择的蜜源，观察蜂根据式（8）搜寻新的可能解。当所有的雇佣蜂和观察蜂都搜索完整个搜索空间时，如果一个蜜源的适应度值在给定的步骤内（定义为控制参数“llimit”）没有被提高，则丢弃该蜜源，而与该蜜源相对应的雇佣蜂变成侦察蜂，侦察蜂通过式（9）搜索新的可能解。

2 IACO-ABC 算法

基于两种算法各自优势，为了平衡算法的探索能力与收敛性能[21]，同时能够提高算法的鲁棒性和解决算法陷入局部最优的问题，提出IACOABC 算法。

IACO-ABC 算法的基本思想为：生成一个群体，将其分为两个部分，Part1 为蜂群，Part2 为蚁群。通过比较两者的当前最优解，学习对方种群有用的信息，取长补短。仿真实验表明该交互融合算法具有较好的寻优能力以及鲁棒性，并且在复杂工作环境下也能出色地完成任务。

IACO-ABC 算法流程如图1 所示，具体步骤如下：

Step1：参数初始化；对融合算法的各个参数进行初始赋值，包括蚂蚁数K、信息素矩阵τ、信息启发式因子、期望启发式因子、信息素总量Q、蚂蚁迭代次数N、维数D、蜂群总数K、蜂群迭代次数G、限度llimit。

Step2：随机生成初始解N，并将种群分为两部分，Part1 的规模为n1，Part2 的规模为n2。

Step3：Part1 子群根据IACO 算法进行进化，得到全局最优解为gbest1；Part2 子群根据ABC 算法进行进化，得到全局最优解为gbest2。

Step4：比较gbest1与gbest2，若gbest1优于gbest2，将gbest1作为Part2 蜂群当前最优解再次进行迭代更新；若gbest2优于gbest1，则将gbest2作为最优解输出。

Step5：比较当前最优解是否满足终止条件输出最优解，否则返回Step1。

图1 IACO-ABC 算法流程

3 仿真结果

3.1 仿真环境建模

在机器人路径规划中栅格法非常实用，因此首先采用栅格法构建机器人的工作环境。如图2所示，将变电站巡检机器人规划地图分解为一系列小栅格，使用大小相同的栅格划分环境空间，并用20×20 二值化栅格数组来表示环境。其中：黑格代表障碍物，在栅格数组中标为1；白格代表自由空间，在栅格数组中标为0；同时还存在陷阱，例如被黑格包围着的白格同样是不能经过的。最优路径要求是在所有不能碰到黑色障碍物的路径中的一条最短路径。Start，End 分别表示机器人的起始和终止位置。

图2 机器人工作环境栅格法建模

3.2 实验结果与分析

将IACO-ABC 算法应用于实验工作环境下巡检机器人的路径规划，本文算法实现的软件平台为MATLAB 2017a，采用计算机配置为Intel Core i5-4570 CPU，8.00 GB RAM。为了体现改进融合算法的性能，IACO-ABC 算法中的蚁群参数与ABC 算法参数一致，并将仿真结果与ABC 算法结果进行分析对比，算法初始化参数对比见表1、表2。

表1 ACO 算法初始化参数

表2 改进算法蜂群初始化参数

仿真结果对比如图3、图4 所示。

图3 ACO 算法仿真结果

图4 IACO-ABC 算法仿真结果

为了更好地验证融合算法的有效性与优势，通过改变障碍物的分布情况以及扩大地图的大小来进行进一步的仿真实验。将原先的20×20 二值化栅格数组尺寸改为25×25，30×30 与35×35。随着地图尺寸的增加，障碍物的规模增大，寻优的难度系数增大，可以充分衡量算法对于不同尺度地图的规划能力，测试其鲁棒性和泛化能力。

算法优化结果对比见表3。可以看出：当工作环境简单时，融合算法的优势并没有体现出来，搜索时间反而相对较长；当面对复杂情况时，融合算法体现了其快速性与稳定性，在参数不变的前提下，IACO-ABC 算法有效地加快机器人全局寻优速度，减少了搜索时间，改善了算法执行效率。

表3 算法优化结果对比

4 结语

针对变电站巡检机器人的路径规划，本文提出了IACO-ABC 算法。为了避免算法出现停滞现象，将融合算法的ACO 算法部分在全局信息已知的情况下进行改进，并提出一种蜂群自适应位置更新公式，提高了ABC 算法部分的局部搜索能力。对栅格地图的仿真实验结果表明，本文算法在复杂环境下的规划能力和鲁棒性能较好，并提高了路径质量以及算法效率。