局部放电检测机器人巡检的重复路径问题研究①

李 宁 郝术兴 雷耀旭 郭 欣 王 熙 邵谢宁

(*河北工业大学人工智能与数据科学学院 天津 300130)(**保定中创电子科技有限公司 保定 071051)(***河北省烟草公司邢台市公司 邢台 054001)

0 引 言

随着我国电力建设的不断发展，变电站的电压等级也不断提高，对电网的稳定运行提出了更高的要求。变电站的高质量稳定运行是可靠供电的重要前提和保障。因此，变电站的运维巡检工作十分重要。智能巡检机器人的出现改善了变电站的巡检情况，在一些无人看守的边远地区以及恶劣天气下的变电站巡检工作中，巡检机器人起到了很大作用[1]。智能机器人搭载超声波传感器进行局部放电带电检测[2]，不仅保证了工作人员的安全，提高了供电质量和经济效益，而且加快了变电站巡检的智能化发展。

高效的巡检路径规划是智能机器人巡检工作的重要问题之一，路径规划的优劣直接影响着巡检效率的高低。近些年来，国内外提出了很多关于变电站巡检机器人路径规划的方法，如Dijkstra算法、A*算法[3-6]、遗传算法、神经网络算法[7]、模拟退火法等等，并为优化巡检路线做出了相应改进[8，9]。

变电站巡检任务中各巡检点的路径规划其实可以看作为旅行商问题(traveling salesman problem,TSP)。旅行商问题是一个经典的组合优化问题，属于Non-deterministic Polynomial问题，而蚁群算法正是最早应用于解决TSP问题的。

将启发式搜索算法A*算法与蚁群算法相结合，利用A*算法计算出两两巡检点间的路径，并将所有巡检点间的距离信息提供给蚁群算法进行巡检序列的计算，此方法能有效地解决变电站巡检机器人的路径规划问题[10]，但其计算结果在力求最短路径的同时并没有解决路径重复的问题，导致机器人行驶较多重复路径。

本文针对变电站局部放电检测机器人的路径规划的路径覆盖比优化问题提出一种改进了传统的融合算法，其依据蚁群算法计算出的巡检序列来指导A*算法寻路，并依据重复路径表信息，增大已寻路径节点的代价值，驱使A*算法减少重复路径的搜索，再继续将改进后的A*算法生成的距离信息表供蚁群算法进行计算，获得巡检点序列，直到迭代优化出最优巡检路径，大大提高了巡检路径的有效覆盖比和巡检质量，对变电站巡检工作的研究具有重要意义。

1 变电站局部放电故障检测

1.1 智能车载局部放电检测的原理

变电站电气设备的绝缘劣化往往是造成设备故障的主要原因，而局部放电正是高压电气设备绝缘劣化的体现，也进一步造成了设备的损坏。绝缘体表面或内部的电场特别集中并且达到一定强度后产生局部放电。局部放电过程是一个物理化学反应过程，伴随着电磁波、超声波、脉冲电流以及光能和热能的产生。但变电站中的局部放电故障不仅在主要电气设备上发生，输电线以及绝缘子等都有可能发生局部放电故障。在变电站局部放电故障检测过程中，应在完成巡检任务的前提下，尽可能检测更多的可疑放电点。目前针对局部放电现象提出了很多放电检测方法，如脉冲电流检测法、特高频检测法[11]以及超声波检测法[12,13]等。

大多数变电站对于局部放电检测所采取的方法是人工手持超声波接收传感器来寻找局部放电区域。由于超声波具有良好的方向性，这种超声波检测法在实际检测工作中取得了不错的效果。

智能车载局部放电检测系统在巡检机器人上搭载与超声波接收传感器方向一致的摄像头，通过巡检机器人的移动记录超声波信号大小，并在局部区域找到超声波信号异常区域的信号最大处，然后用摄像头对该区域进行拍照并回传到后台系统等待进一步处理。

由此可见，整个巡检任务的路径规划对于局部放电的检测是至关重要的。由于在实际的检测工作中故障发生点的位置是未知的，所以应依据检修经验和随机检测的方法，在一定的巡检代价下尽量巡检更多的不重复路径进而扩大巡检范围，提高巡检效率。

1.2 变电站环境建模

对于巡检机器人的路径规划问题，首先要针对变电站的环境特点进行变电站环境的建模，变电站环境的准确建模是做好路径规划问题的前提。本文采用栅格模型来对变电站环境进行二维建模，将变电站环境用以相同尺寸的正方形栅格为单位的二维栅格图来进行描述。

变电站的设备布局比较紧凑，可行道路比较狭窄，针对变电站的环境特点，本文对变电站的环境进行了二维仿真建模。如图1所示，以可行道路宽度为边长的正方形栅格作为最小单位，建立了20×20单位长度大小的环境地图。其中黑色栅格代表变电站的不可行区域，即为障碍区域，白色的区域为巡检机器人的可行区域。

图1 变电站二维栅格模型

结合变电站环境的实际情况，设定巡检机器人的移动方向为正前、正后、正左、正右4个方向，不能跨越障碍物，不能沿栅格对角线方向前进，如图2所示。

图2 巡检机器人可移动方向示意图

2 A*算法和蚁群算法的基本原理

2.1 A*算法基本原理

A*算法是基于Dijkstra算法和Greed-Best-First-Search算法的一种启发式搜索算法。在静态环境下的路径搜索问题中，A*算法往往是最有效的求解最短路径的方法。A*算法通过一个估价函数来选择机器人的移动路径，其估价函数表示为

f(n)=g(n)+h(n)

(1)

其中，g(n)表示初始节点到任意节点n的代价，h(n)表示从当前节点n到目标节点的启发式评估代价，f(n)是这2个代价的和，是选择路径的参考依据。考虑到变电站的环境以及巡检机器人的运行特点，本文选取曼哈顿距离来计算启发函数，则2节点之间的启发函数代价可表示为

h(n)=abs(n.x-goal.x)+abs(n.y-goal.y)

(2)

其中，n.x和n.y分别代表当前节点的横、纵坐标，goal.x和goal.y分别代表目标节点的横、纵坐标。在利用A*算法进行路径规划时，从起始点开始，把当前点周围的可行进点放入openList表中，将已经走过的点和障碍点放入closeList表中，每次选择openList表中f(n)最小的点为前进节点，并将该点放入closeList表中，如此重复寻找过程，直到寻到终点，由此得到一条最短路径。

2.2 蚁群算法基本原理

蚁群算法的本质也是一种启发式的全局优化算法，其灵感来源于自然界中蚂蚁觅食的行为。蚁群在寻找食物的最短路径的过程中，会在其经过的路径上释放一种“信息素”，在相同时间内，路径越短，路径上的“信息素”的浓度也就越浓，结合“信息素”的更新原则，蚁群依据路径上的“信息素”的浓度大小来选择最短路径。蚁群算法作为一种全局智能仿生算法，首先应用在解决TSP问题上。

蚁群算法解决TSP问题的基本步骤如下。

步骤1首先计算所有城市两两之间的距离，生成城市距离信息矩阵。

步骤2初始化迭代次数、信息素矩阵等计算参数，随机分配蚂蚁初始城市。

步骤3对所有蚂蚁进行路径搜索，依据概率函数进行路径点选择，概率函数如下所示：

(3)

其中，i、j分别为当前点和下一步的可选择节点，k表示当前为第k只蚂蚁，τij为点i、j之间的信息素强度；ηij=1/dij，为i、j2点距离之间的倒数，称为能见度；allowedk为还没访问过的节点集合；α和β是2个常数参数，分别为信息素和能见度的权重。

步骤4依据概率选择下一节点，直到当前蚂蚁遍历全部节点后，更新信息素浓度，公式如下：

(4)

其中0<ρ<1为信息素的蒸发率，m为蚂蚁总数，Δτij为蚂蚁在i、j2点间留下的信息素。

步骤5多次迭代后，输出最优路径。

2.3 A*算法和蚁群算法结合解决变电站巡检路径规划问题算法原理

变电站局部放电巡检的路径规划问题可近似看作TSP问题[14]，因此利用蚁群算法来解决这一问题。

在蚁群算法解决TSP问题时，初始时的地理距离信息矩阵只是通过两城市之间的直线距离获得的，此初始方法虽然可以作为解决TSP问题的前提条件，但显然不适于解决变电站各巡检点间的路径规划问题。依据变电站的环境特点以及其距离数量级相比TSP很小的特点可知，应以两两巡检点间的实际巡检距离来初始化地理距离信息矩阵。

利用A*算法计算得到两两巡检点间的巡检路径并计算路径的长度信息，由此方法初始所有巡检点间的距离后，将获得的地理距离信息矩阵用于蚁群算法的计算，经过多次有效迭代后获得最短的巡检路径。虽然获得了最短路径，但是此结合算法并没有对巡检路径的重复路径问题进行处理，即此结合算法只是用A*算法独立地计算两两巡检点间的巡检路径，将距离信息提供给蚁群算法进行路径规划，并未考虑各路径之间的路径重复问题。从变电站的巡检目标来看，应要求巡检机器人尽量避免行走重复的路径，在可以接受的路径总长度范围内，应围绕巡检点尽可能地探索出更多的新路径，找出局部放电故障点，真正实现巡检。

3 改进的A*算法与蚁群算法融合解决变电站局部放电巡检的路径规划问题

3.1 算法的改进

在A*算法融合蚁群算法解决变电站局部放电巡检的路径规划问题的基础上，本文提出利用改进的A*算法与蚁群算法融合的算法来解决这一问题。首先利用传统的A*算法融合蚁群算法计算出一个巡检点序列；然后用A*算法对此序列中从左到右的两两巡检点依次进行路径计算，将每次获得的巡检路径节点都加入一个新建的重复路径记录表中，并将重复路径记录表中的节点的步长代价值增大到某一合理数值。文中所指的步长代价为单个节点的步长值，即从相邻节点行进到重复路径记录表中的节点所需的代价。改进的方法通过增大重复路径记录表中节点的步长代价，进而有效避免了传统A*算法在启发搜索过程中选择重复路径的问题。

重新获得地理距离信息矩阵后，再次利用蚁群算法计算得到巡检序列，如果此次的巡检序列和前一次巡检序列不一样，则依据此次序列从左到右依次利用改进的A*算法重新获得初始地理距离信息矩阵，并再次利用蚁群算法获得巡检序列，直到连续2次得到与上次巡检序列一致的结果，结束迭代过程，得到最终的巡检路径，算法流程图如图3所示。

3.2 巡检序列结果指导A*算法策略

与传统A*算法与蚁群算法融合不同，本文提出的利用蚁群算法得出巡检点序列来指导A*算法进行有序节点间的路径生成并增加重复路径列表是改进算法的核心之一，将重复路径列表里的节点赋予新的步长代价，使改进的A*算法生成路径时尽量不寻找已经得到过的路径节点。

例如，有巡检点列表[1,2,3,4,5]，经过首次蚁群算法计算后生成的巡检序列为2-5-1-3-4，然后利用A*算法首先计算“2-5”之间的巡检路径，并将此路径中的所有节点加入重复路径列表，而重复路径列表中的节点都被重新赋予了较大的步长代价，即从当前点行进到重复路径列表里的节点的代价要比行进到不在重复路径列表里的节点的代价大，按照此过程依次计算得到“5-1”、“1-3”、“3-4”、“4-2”间的路径，示意图如图4所示。

依据巡检序列，首先利用A*算法获得“2-5”巡检点之间的路径，如上图中的实线箭头所示，然后依顺序计算“5-1”巡检点间的路径，由图4可见，如果是传统A*算法，依据最短路径的启发式搜索原则，将会获得“5-0-1”的虚线箭头所示巡检路径，但明显“5-0”是一条已经走过的重复路径。为达到高效的巡检目的，应在一定的巡检代价范围内，尽量探索更多的巡检路径。利用改进后的A*算法计算后，得到“5-1”实线箭头部分的路径，达到了预期效果。

3.3 迭代指导策略

改进后的算法首次计算出巡检序列后，利用巡检序列指导改进的A*算法进行巡检点间的路径规划，更新地理距离信息矩阵。再利用蚁群算法计算出巡检点序列，将此序列与前一个指导A*算法计算的巡检点序列进行比对。如果不一致则清空重复路径列表，使用最新巡检点序列再次指导A*算法进而再次更新地理距离信息矩阵并提供给蚁群算法进行计算，迭代对比，直到连续2次得到一致的巡检点序列，结束迭代，获得最终巡检点序列。

每一次的蚁群算法计算都代表着在当前地理距离信息矩阵前提下的最短路径规划，本文提出的算法认为连续2次巡检序列一致则找到了最优巡检路径。

3.4 定义路径覆盖比

定义路径覆盖比的公式如下：

(5)

其中，巡检路径的总路径覆盖长度为C,总路径长度为L，路径覆盖比为ε。

图3 改进算法的流程图

图4 重复列表作用下机器人寻路示意图

4 仿真验证

4.1 蚁群算法的参数选择

蚁群算法作为一种基于种群模拟进化的随机搜索算法，其算法参数对于计算结果的影响非常大。本仿真遵循传统蚁群算法的参数设置原则[15-17]，随机选取N=10个巡检点，蚂蚁数量m=5，信息素权重α=1，能见度权重β=2，信息素挥发系数ρ=0.5，总信息量Q=100，迭代次数为1 000。

4.2 改进算法步长代价的选择

步长代价(step)的选择是影响改进A*算法不选择重复路径的效果的重要因素，传统的A*算法的步长代价设为10。针对变电站二维地图障碍物的最大周长，本文在[10, 300]的步长代价范围内进行对比，在每个步长代价的作用下进行10次路径规划并求得路径覆盖比的平均值，对比所有步长代价的平均路径覆盖比，选出步长代价的最佳值。在Spyder开发环境中利用Python语言编程进行仿真，对比结果如图5所示。

从图5可以看出，当step为210时，规划路径的平均路径覆盖比在对比范围内的效果是最佳的，所以选取step为210进行改进算法的仿真。

4.3 仿真结果

为不失一般性，运用本文所提出的方法进行3组仿真，每组仿真随机挑选10个变电站巡检点进行路径计算，并求得连续10次的路径覆盖比，与传统算法得出的结果进行对比，如图6所示。

图5 不同step值的平均路径覆盖比

第1组改进算法与传统算法仿真结果的平均效果增幅如表1所示。

由表1可以看出，第1组对比仿真结果显示改进算法比传统算法的平均覆盖比增大了12.4%。

对改进算法和传统算法的第1组多次仿真结果进行最优挑选，如图6(c)、(d)所示，对比结果分析如下。

图6 第1组仿真结果

表1 第1组仿真平均结果对比

图6(c)中①、②、③、④、⑤、⑥、⑦、⑧、⑨、⑩依次代表1～10号巡检点，最终的巡检序列为4-8-3-6-2-5-7-10-1-9-4，路径总长度为100节点，有效覆盖99节点，路径覆盖比达到了99%。图6(d)中的巡检序列为6-3-8-4-9-1-10-7-5-2-6，路径总长度为93节点，有效覆盖路径为 77节点，路径覆盖比为82.8%。改进算法比传统算法的路径覆盖比增大了16.2%。

第2组重新挑选10个巡检点仿真结果如下。

第2组改进算法与传统算法仿真结果的平均效果增幅如表2所示。

由上表可以看出，第2组对比仿真结果显示改进算法比传统算法的平均覆盖比增大了8.4%。

对改进算法和传统算法的第2组多次仿真结果进行最优挑选，如图7(c)、(d)所示，对比结果分析如下。

图7(c)中的最终巡检序列为4-2-8-10-9-1-3-5-7-6-4，路径总长度为96节点，有效覆盖93节点，路径覆盖比达到了96.9%。图7(d)中的巡检序列为9-10-8-2-4-6-7-5-3-1-9，路径总长度为88节点，有效覆盖路径为75节点，路径覆盖比为85.2%。改进算法比传统算法的路径覆盖比增大了11.7%。

图7 第2组仿真结果

表2 第2组仿真平均结果对比

第3组重新挑选10个巡检点仿真结果如下。

第3组改进算法与传统算法仿真结果的平均效果增幅如表3所示。

由表3可以看出，第3组对比仿真结果显示改进算法比传统算法的平均覆盖比增大了10.4%。

对改进算法和传统算法的第3组多次仿真结果进行最优挑选，如图8(c)、(d)所示，对比结果分析如下。

图8(c)中的最终巡检序列为9-5-6-4-8-10-7-3-2-1-9，路径总长度为94节点，有效覆盖92节点，路径覆盖比达到了97.9%。图8(d)中的巡检序列为1-2-3-8-4-10-6-5-9-7-1，路径总长度为82节点，有效覆盖路径为68节点，路径覆盖比为82.9%。改进算法比传统算法的路径覆盖比增大了15%。

4.4 3组仿真对比结果

通过3组仿真的对比，获得表4和表5的结果。

4.5 结果讨论

由以上结果可以看出，在一定范围内的巡检代价下，本文所提出的算法在对变电站局部放电故障巡检路径规划的路径覆盖比方面效果更好，平均覆盖比提升了10%左右。虽然增加了一定的路径长度，但路径覆盖比有了显著的提升。改进后的算法规划出的路径满足了故障巡检的要求，提高了巡检的效率和质量。

图8 第3组仿真结果

表3 第3组仿真平均结果对比

表4 3组仿真的平均覆盖比增幅

表5 3组仿真较好结果覆盖比增幅

5 结 论

传统的A*算法与蚁群算法相结合解决变电站局部放电故障巡检路径规划问题时存在重复路径较多的问题，结合变电站局部放电故障巡检背景，传统的方法在路径规划中的路径覆盖比方面有待提高。针对此现象，本文提出的改进的A*算法与蚁群算法相融合的方法很好地解决了这一问题。在一定范围的巡检资源消耗代价下，扩展出更多的巡检路径，提升了巡检路径覆盖比，提高了变电站局部放电巡检工作的质量。

本文所提出的改进算法在寻找最优路径的收敛问题上还有待提高，目前只能通过多次计算来挑选最优路径，此问题是今后研究的重点。