栅格遗传算法的变电站巡检机器人路径规划

2015-05-04姜英杰吕学勤段利伟

科技与创新 2015年6期

姜英杰　吕学勤　段利伟

摘要：根据变电站巡检机器人的巡检环境和巡检任务，提出采用栅格法模拟划分机器人的工作空间，将变电站工作环境分解成一系列具有二值信息的网格单元，并结合遗传算法对变电站巡检机器人进行全局路径规划。提出了连续相邻栅格定义和不等长染色体编码，并使用自适应方法选取了交叉概率和变异概率进行路径寻优。通过MATLAB仿真，证明了这种栅格地图与遗传算法结合的方法能快速、有效地在已知环境中得到机器人的避障最优路径。

关键词：巡检机器人；栅格法；改进遗传算法；路径规划

中图分类号：TP242 文献标识码：A DOI：10.15913/j.cnki.kjycx.2015.06.012

变电站传统的人工巡检方式中存在劳动强度大、管理成本高和工作效率低等不足，且很多变电站受恶劣地理、气候条件的限制，一般的人工巡检很难实现有效的巡检工作，即使一些变电站实现了少人或无人值班，但依旧在一定程度上存在因无人及时监视、巡视而带来的一系列问题。因此，智能化巡检已成为发展智能变电站的必然要求。基于移动机器人技术开发的变电站巡检机器人系统，利用机器人主体的自主运动，并根据巡检任务在特定的工位停靠，通过携带的红外热像仪、可见光CCD等相关电站设备检测装置进行设备检测，能及时发现电力设备的内部热缺陷、外部机械和电气问题，从而提高工作效率和质量，真正起到减员增效的作用，最终推进变电站无人值守的发展。

巡检机器人是轮式移动机器人在工业上的又一典型应用，其路径规划的主要任务是在已知障碍物的环境中的静态全局规划。目前，全局路径规划研究主要包括环境建模和路径搜索两个子问题。其中，环境建模的主要方法有可视图法（V—Graph）、自由空间法（Free Space Approach）和栅格法（Grids）等；路径搜索策略主要方法有A×算法、D×算法等。

随着人工智能的发展，启发式优化方法被逐渐应用到路径规划的研究中。遗传算法作为一种典型的启发式算法，成为寻优搜索方面的主要方法之一。本文采用栅格法进行环境建模，结合自适应算子的遗传算法对机器人进行全局路径静态规划。栅格法表示的地图简单、直观，直接使用栅格标号对路径个体进行编码，易于操作且节省内存空间。不等长染色体编码和连续相邻栅格搜索方法保证了初始生成路径的多样性和可行性，可自适应地调整交叉概率和变异概率，能够避免早熟现象。

1 建立巡检模型

1.1 建立栅格地图

只考虑巡检机器人工作的变电站环境的平面状况，变电站环境用正方形表示，变电站内设备等效于机器人路径中的障碍物，且尺寸和位置己知。在机器人的运动过程中，障碍物的位置不发生变化。如图1所示，采用栅格法将机器人的工作空间划分为成一系列大小相等的、具有二值信息的网格单元。栅格的二值信息包括直角坐标（x，y）和栅格序号N，每个栅格都能用其中一个量值唯一表示。利用序号法编码表示路径，易于操作且节省存储空间。当需要评价一个路径的优劣时，可以将栅格序号转换为二维直角坐标，用以计算每条路径的距离。每个栅格的序号和坐标的对应关系为：

N=x+10y. （1）

在图1中，空白栅格表示巡检机器人能够自由通过的通道；阴影栅格表示障碍物，即变电站设备所占空间。一般在电气设

———————————————————————————

备实际边界的基础上增加1个电气绝缘的安全距离，并将其增补等效为正方形栅格。给每个栅格单元赋予一个二值属性Property，记作P，空白栅格P值为0，阴影栅格P值为1.模拟机器人在自由通道行走时，需定义连续的相邻栅格。如图2所示，一般情况下，当前栅格N有8个相邻栅格，分别记作N-10-1，N-1，N+10-1，N+10，N+10+1，N+1，N-10+1和N-10.

图1 环境地图的10×10栅格描述

对于N-1，N+10，N+1和N-10栅格，与栅格N是连续相邻栅格的条件为它们都为自由栅格；对于N-10-1，N+10-1，N+10+1和N+10+1栅格，都是栅格N的对角栅格，与栅格是连续相邻栅格的条件为各个对角栅格都为自由栅格，且每个对角栅格与栅格公共的水平栅格和垂直栅格中至少有一个是自由栅格。搜索路径时，当前栅格的下一栅格可以是其任意一个连续相邻的栅格。

对于栅格地图中的边界栅格，处理方式如下。

当0

栅格越过地图的下边界，与N互为非连续相邻栅格。

当9≤N/10≤10时，栅格为地图中的上边界栅格，N+10栅格越过地图的上边界，与N互为非连续相邻栅格。

当mod（N，10）=1 mod时，栅格为地图中的左边界栅格，N-1栅格是地图的右边界，与N互为非连续相邻栅格。

当mod（N，10）=0时，栅格为地图中的右边界栅格，N+1栅格是地图的左边界，与N互为非连续相邻栅格。

1.2 巡检任务介绍

变电站常规巡检承担着变电站日常巡检的主体任务，但因其巡检范围大，所需的巡检强度和巡检成本较高，加之一些突发状况的干扰，常规巡检模式不能完全满足变电站巡检的可靠性要求。针对某些需要多次巡检的重要设备和一些特殊情况，需要增加重点设备巡检和设备分级巡检对常规巡检进行补充。

依据图1所示的环境地图，重点设备巡检和设备分级巡检的描述如下。

1.2.1 重点设备巡检

设机器人充电室在栅格N1处，某个重点巡视设备对象停靠工位在栅格Nm处，机器人从充电室出发，根据规划路径运动到重点设备处工位，巡视完毕后原路返回充电室，最优规划路径要求路径最短。

1.2.2 设备分级巡检

设机器人充电室在栅格N1处，多个需要区分先后巡视顺序的设备的停靠工位分别位于栅格N2，N3，…，Nm处，机器人从充电室出发，根据规划路径依次运动到各个重点设备工位处，巡视完毕后原路返回充电室。设备分级巡检是变电站巡检模式之一，从算法上可以将其分解成多个、单个重点设备巡检的依次衔接。

2 改进遗传算法的路径规划

2.1 染色体编码

一般的遗传算法对解空间的编码采用二进制形式。对于栅格地图中机器人的路径规划问题，采用路径经过的栅格序号序列进行编码，机器人从起点达到终点的完整路径表示1条染色体，每个栅格序号是1条染色体的基因之一。存储算法所产生的路径，有利于实现编程和节省存储空间，无须解码。

2.2 种群初始化

假定初始化种群染色体的个体数目为M=50，种群用1个染色体集合表示为：

Xt={X1，X2，…，Xm}. （2）

第i条染色体表示为：

Xi={N1，i ，N2，i，N3，i，…，Nj，i，…，Nm，i，}i∈{1，2，…，M}.

（3）

初始种群产生方法为：从起点栅格N1开始，根据“连续的相邻栅格”原则，从与之相邻的8个栅格中，选取任一个连续相邻栅格作为此染色体的第二个基因；从围绕第二个基因的相邻栅格中，选取一个连续相邻栅格作为此染色体的第三个基因，依此类推，直到目标栅格Nm为止。在搜索过程中，每个连续相邻栅格被选取的概率相等，且当前所选基因与间隔的上一基因不重复。

2.3 适应度函数

取每条路径的距离长度为机器人路径的目标函数，记作f（D），则路径规划目标函数为：

. （4）

式（4）中：d（Nj，iNj+i，i）为第i组染色体中的栅格Nj，i到栅格Nj+i，i的中心距离。

第i组染色体中的栅格Nj，i到栅格Nj+i，i的中心距离可表示为：

. （5）

适应度函数取目标函数的倒数，距离越短，适应度值越大：

Fitness（Ni）=1/f（D）. （6）

2.4 遗传操作

2.4.1 选择算子

采用竞争策略，令每一代染色体按适应度优劣竞争，从中选出优胜个体进入下一代种群，直到充满种群为止。轮盘赌是一种正比选择策略，能根据与适值成正比的概率选出新种群，具体步骤如下。

第一步，分别计算每一个染色体的累积概率：

. （7）

式（7）中：Fitness（Xk）为第k个染色体的适应值；

为一代所有个体适应值的和。

第二步，在[0，1]区间随机产生M个均匀分布的伪随机数r.

第三步，对于每一个rk，如果pk-1

第四步，重复第三步，直到充满种群得到大小为M的新种群。

2.4.2 交叉算子

交叉操作是结合来自父代交配种群中的信息产生新个体的过程，通常有单点交叉、多点交叉和均匀交叉等方法，本文选择单点不等长交叉的方法。只要2条路径除首、尾栅格外通过相同的栅格，就可以以相同栅格为交叉点交叉。如果相同的栅格不止一个，则在这些相同的栅格中任选一个交叉；如果没有相同的栅格，则不交叉。用交叉后的子代个体代替原种群中的父代个体，以产生新的种群。比如，2条染色体分别为：{64，75，86，77，78，79，89，99}和{64，65，66，76，86，96，97，98，99}，2条染色体有共同栅格86，以86栅格为交叉点交叉，交叉后得到新的2条子染色体为{64，75，86，96，97，98，99}和{64，65，66，76，86，77，78，79，89，99}。

2.4.3 变异算子

由于所产生的初始路径个体均为机器人的连续路径，一般的变异操作必然会产生不连通的路径个体，对个体的优越性产生破坏，进而造成种群退化。为了克服这一不足，本文在保证路径连续性的前提下进行变异操作，具体过程如下。

第一步，随机从种群中挑选出M×Pm个待变异的个体，Pm为变异概率。

第二步，选取每个个体靠近中间位置的2个栅格，并将其中部分删除，将原染色体分成前、后两段。

第三步，以前段路径的最后栅格作为路径起点，后部分路径的起始栅格作为终点，采用节种群初始化方法搜索一段新的子路径，将前、后两段分开的路径连接起来构成一条连续的路径，作为新一代种群中的个体。

2.5 交叉和变异概率

选取常值交叉概率Pc和变异概率Pm，想要达到满意的遗传算法行为和性能，就需要反复试验，其过程烦琐且不易得到适应于每个问题的最优解。采用自适应遗传算法计算群体的平均适应度时，对于适应度高于种群平均适应度的个体需保护优质解，对其采用较低的Pc和Pm；对于适应度低于种群平均适应度的个体，需淘汰劣质解，对其采用较高的Pc和Pm.

Pc和Pm的自适应调整公式如下：

. （8）

. （9）

式（8）（9）中：Fmax为种群中最大的适应度；Fav为每代种群的平均适应度；F'为交叉的两个个体中较大的适应度；F为要变异个体的适应度。

3 仿真结果分析

在Matlab仿真环境中，对上述算法进行了仿真测试。变电站环境设备区栅格分布情况如图3所示，分别对机器人的两种不同巡检模式进行了仿真，结果如下。

3.1 重点设备巡检

从图3中可以看出，机器人充电室在栅格“1”处，重点巡视的设备停靠工位在栅格“100”处，图3中的实线为机器人最优规划路径，单程路径用栅格序号依次表示为：1→12→22→33→34→45→56→66→77→78→79→90→100. 单程路径的最小距离长度值为144.852.

图3 重点设备巡检规划路径

3.2 设备分级巡检

仿真结果如图4所示，机器人充电室在栅格“1”处，多个先后巡视的设备停靠工位分别位于栅格“52”“46”“17”“100”处。从算法上看，将中间停靠点“52”“46”“17”依次当作前、后寻优路径的终点和起点。图4中的实线为机器人最优规划路径，“o”表示各个不同的停靠工位。单程路径用栅格序号依次表示为：1→12→22→32→42→52→63→64→55→46→36→26→17→18→19→39→49→60→70→80→90→100.单程路径最小距离长度值为238.9949.

图3和图4中的2种巡检模式的仿真结果表明，本文采用的栅格法建模和遗传算法避障规划路径的方法简单、有效，能快速、有效地得到最优规划路径。

4 结束语

本文对变电站的工作环境进行了分解建模，结合巡检机器人的2种巡检模式，并采用一种改进的遗传算法对巡检机器人进行了全局静态规划。

基于不等长染色体编码和连续相邻栅格的随机搜索算法初始化种群，能够保证初始化种群的多样性和可行性。同时，适当改进了遗传算子，自适应地调整了交叉概率和变异概率，能够避免早熟现象。

2种巡检模式的仿真结果显示，本文采用的遗传算法简单、有效，对变电站巡检机器人实际应用中的全局路径规划具有一定的借鉴意义。

图4 分级设备巡检规划路径

参考文献

[1]毛琛琳，张功望，刘毅.智能机器人巡检系统在变电站中的应用[J].电网与清洁能源，2009，25（09）：30-33.

[2]刘满禄.路径规划在巡逻机器人中的应用[D].绵阳：西南科技大学，2009.

[3]鲁守银，钱庆林，张斌，等.变电站设备巡检机器人的研制[J].电力系统自动化，2006，30（13）：94-98.

[4]高青，冯李军，张鹏.智能巡检机器人的研究[J].电气时代，2012（4）：74-76.

[5]朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，25（7）：961-967.