考虑机器人尺度的变电站路径规划

江 南，吴振辉，吴凌健杰

(1.国网福州供电公司，福建 福州 350000；2.福建杭润科技有限公司，福建 福州 350000)

1 引言

随着科技的发展和进步以及电力系统自动化水平的提高，变电站的数量急剧增多，对变电站进行巡检的工作量也越来越大。传统的巡检方式还是以人工为主，不仅效率低下，且由于受到巡检员的素质、状态、心理等自身因素以及电磁辐射、风雪天气等外部环境因素的影响，巡检任务中容易发生事故或对潜在的风险无法及时发现。因此，变电站智能辅助巡检机器人的意义就显得十分重大，而智能机器人的路径规划是变电站巡检机器人导航的重要组成部分。

路径规划是个交叉领域，研究者众多，与自动化、工业生产、交通运输行业均密切相关，应用在机器人、无人机、USV等无人控制器中。根据环境建模方式的不同可以分为基于决策论、物理、数学的三种建模方法。如模糊控制、状态聚类等方法的属于基于决策论的建模方式，通过在环境中采取不同的决策来进行路径规划，通过与环境的不断交互来训练被控制目标，主要用的求解方法是神经网络和强化学习；如线性规划、最小树规划、动态规划等方法属于数学类的建模方式，通常应用在VRP等路线规划当中，通过单纯形法、分支定界法等传统算法或者如禁忌搜索、PSO算法等智能算法进行求解；最后一类是物理的建模方式，主要用到的方法有人工势场法[1]、路线图法、栅格法[2]、决策树法等等，这一类方法都是考虑实际的物理空间而不是抽象的运筹建模，通常使用启发式算法来进行求解，例如蚁群算法[3]、粒子群算法、模拟退火算法[4]或者多种智能算法融合后的混合启发式算法[6]。

链接图法[7](Maklink)是路线图的一种建模方式，通过将复杂的障碍物空间进行简化，成为简单的多边形体，再通过一系列的步骤以及规则连接多边形的顶点或做顶点到边界的垂线，将自由空间进行划分。该方法通常将被规划目标视为质点，并把障碍物区域进行一定扩展，从而避免规划目标与障碍物发生碰撞。但是，在变电站的巡检区域中，会有许多狭窄的通道，对障碍物区域进行扩展会使得这些通道消失，从而导致巡检机器人无法到达检测区域。

人工势场法[8]在路径规划中应用的也非常广泛，这是因为其具有简洁的数学模型以及较为平滑的规划路线。但是，人工势场法也有其自身的缺陷[9]，尽管计算过程中可以输入全局的环境信息，但只有被规划目标周围的力的作用才会对其移动造成影响，这就导致人工势场法无法使用的全局环境信息，容易陷入极值点。例如：当终点处在障碍物区域之中时，斥力的作用可能导致机器人无法到达终点[10]；在狭窄的区域中斥力和引力的影响，可能导致规划路线来回抖动，无法前进。

本文将链接图法与人工势场法进行结合，首先通过dijkstra算法在链接线上的节点上规划出一条初始路线，并将路线上的节点作为人工势场的引力牵引点，障碍物边界进行离散化处理，将其上的点作为斥力点；然后，通过人工势场法规划出一条平滑的路线；最后，利用遗传算法对节点的选择进行优化，不断的迭代寻优，最终可以在有凹多边形的仿真环境中得到一条安全性高且较为平滑的可通行路径。该方法可以解决人工势场法容易陷入极值点的问题。

2 环境模型

2.1 改进的Maklink图路径规划环境建模方法

Maklink图是一种简洁且有效的路径规划环境建模方法，它最早由Habib于1991年提出，并被广泛应用在机器人路径规划等领域当中。在Maklink图的传统应用当中，为了避免障碍物与被规划目标发生碰撞，通常是将障碍物的边界进行一定的缓冲扩大，并且将被规划目标视作一个质点，不考虑其碰撞体积。该方法在障碍物相对总体空间较小的情况下是可行的，但当总体空间较小，对障碍物的扩张会导致原本可以通行的区域被覆盖，尤其像是在变电站这样过道狭窄的场景下。并且，如果障碍物的顶点较为尖锐，在该点处的扩张会占据更多的可通行空间，导致路线变长。同时，在尖锐的顶点处的规划出来的路线会有急剧的转折，如果通过圆的切线对路线进行平滑处理，可能会导致被规划目标与障碍物发生碰撞，从而产生危险，如图1(b)所示。如果要避免这种情况发生，障碍物的扩张至少是半倍的被规划目标长度，这样势必会占据更多的原本可通行的空间。

Maklink图原理是按一定规则将障碍物区域的顶点进行连接，从而构成全局连通图，但原初的算法无法解决凹多边形的问题，存在凹多边形构建的全局连通图会导致链接线穿过障碍物区域，从而导致无法规划出安全的避开障碍物的可通行路线。因此，本文在考虑机器人尺度的前提下，对Maklink图进行了改进，从而可以解决存在凹多边形的情况。

首先，在考虑了巡检机器人尺度之后，Maklink链接线所连接的通行区域可能无法满足机器人的通行条件，所以应当对链接线的绘制进行进一步的限制。在Maklink法的中，连接某一顶点与其它某一障碍物的顶点之前，计算该顶点到该障碍物的最短距离，最短距离产生的位置可能在该顶点与定点的连线(如图2(a))或者与障碍物某一条边做的垂线(如图2(b))，当该连线小于巡检机器人的宽度时，表示不满足通行要求，从而构建连通图时不在考虑该连接线。

其次，如上所述，原本的Maklink算法无法处理有凹多边形的情况，会导致规划出的路线穿过障碍物区域。事实上，在巡检过程中，凹多边形的情况会大量遇见，尤其是在复杂的变电站与配电房之中。如果要解决凹多边形，一种可行的方法是对凹多边形进行划分，从而形成多个凸多边形后在进行全局连通图的构建，具体分解凹多边形的方法如下：

a)依次选取凹多边形的顶点，将该顶点相邻的两个凹多边形顶点进行连接，如果这条连线没有从凹多边形中穿过，则该顶点被记录为一个凹顶点，不断重复找出所有的凹顶点。

b)随机选取一个凹顶点p，将该顶点与该凹多边形所有与其不相邻的顶点进行连接，组成集合S。

c)选取集合S中最短的线段，该线段将凹顶点p所在的内角切分成两个内角，判断两个内角是否都小于180°，若是则记录该连线，进入步骤e；若有一个内角大于180°，则将该连线放入备选连接线集合A中

d)备选连接线结合中的线段将凹顶点p所在的内角划分为多个内角，判断是否每个内角都小于180°。若存在大于180°的内角，则返回步骤c，若不存在，则进入步骤e。

e)检查是否将该凹多边形的顶点都遍历的一遍，若否，则返回步骤b，若是，则结束整个流程。

通过如上方法，可以将一个凹多边形分解为多个凸多边形，随后便可绘制链接图。但由于划分后的凸多边形的顶点有所重合，因此需要对凸多边形进行一定的收缩，使凸多边形的顶点不再重叠。通过对凸多边形的每条边进行向内移动，距离选取为单位长度的一半。此时凸多边形之间有着狭窄的通道，但由于对链接线区域的约束，其间巡检机器人不可通行，于是可以使整片区域近似为一个不可通行的障碍区域，如图2(c)所示。

图2 改进Maklink示意图

2.2 改进的人工势场法的路径规划环境模型

在传统的人工势场法中，障碍物用一个质点来表示，障碍物的实际大小由影响距离和斥力系数的大小来控制。规划的目标只被终点的牵引力所吸引，这使得算法很容易进入到极值点或在一定范围内来回抖动。本文提出了一种基于Maklink图的人工势场法环境模型的改进。

在上文改进Maklink建模之后，通过Dijkstra算法在选取链接线上的节点中找到一条起止点的最短路径来作为人工势场法的预规划路线，将该路线中的节点依次作为人工势场法的引力牵引点。对于障碍物区域的描述，通常人工势场法中都是简化成一个质点，但该方法精度较低，尤其凹多边形更无法简化成一个质点的情况，因此本文将障碍物的边界进行离散化处理，以巡检机器人宽度的一半作为间隔，在障碍物的每个边上放置斥力点，将一个障碍物边界上的所有斥力点的合力来代表一个障碍物的对被规划目标的影响，如图3所示。通过该方法构建的路径规划环境模型，通过人工势场法进行求解，就可以得到一条安全性高且平滑的路径，并解决算法原本容易陷入极值点的问题。

图3 变电站环境模型

3 考虑巡检机器人尺度的路径规划算法设计

3.1 算法流程图

本文将人工势场法与Maklink链接图法进行结合实现了对变电站区域的路径规划，提高路线安全性的同时也避免了人工势场法容易陷入极值点等问题。同时，本文又通过遗传算法对每条链接线上节点的位置进行优化，将节点位置进行遗传编码，每一条染色体对应所有节点的位置，再通过Dijkstra算法在节点中找到一条最短路径，把该路径作为人工势场法的预规划路径，人工势场法求解之后得到的路径长度作为染色体的适应度值，最后不断地通过遗传算法的选择、交叉、变异进行循环迭代，最终得到最优的规划路径。算法具体流程图如图4所示。

图4 考虑机器人尺度的路径规划算法流程图

3.2 人工势场法基本原理及改进

人工势场法[12]的基本思想仿照电磁场对电荷的作用而构建的虚拟力场，被规划目标视为正电荷，障碍物同样为正电荷对其产生斥力，斥力的大小与两点间距离成反比，目标点为负电荷对被规划目标产生引力，引力大小与两点间距离成正比，最终被规划目标在合力的影响下像着目标点前进。传统人工势场法路线规划示意图如图5(a)所示。

图5 人工势场法作用原理示意图

为了方便计算并且提高计算效率，本文对巡检机器人的形状进行了简化，通过多边形线段集对巡检机器人的形状进行表述，以便不会减少机器人的实际尺度以及占用过多的自由空间。如图5(b)所示，在通过线段集对机器人外形进行描述之后，障碍物对机器人的排斥力不再由原来质点间距离进行计算，而是通过点到多边形的最短距离来进行计算，如前所述，点到多边形的最短距离只会在点到多边形的顶点或边的垂线之间。这样之后，可以有效地考虑机器人的尺度，从而保证了在狭窄的通道之下也能找到一条安全的可行路径。

引力场和斥力场函数公式如下所示

Uatt(X)=0.5αρ2(X，Xg)

(1)

(2)

式中：α、β分别为引力与斥力系数；X、Xg、XO分别表示巡检机器人模型的中心点、目标终点引力点、障碍物斥力点的笛卡尔系坐标位置；ρ(X，Xg)、ρ(X′，Xo)分别表示机器人中心点到目标点的距离和机器人边界到障碍物的最短距离；ρ0为障碍物斥力点的斥力作用范围。机器人所具有的的势场势能随着距离越近就会越大，距离越远则会越小，当机器人处在障碍物的最大影响距离之外时，所具有的的势场势能则为零。

通过对引力场和斥力场函数计算负梯度公式，则可以得到机器人受到的作用力：

(3)

(4)

机器人所受的合力为：

(5)

3.3 基于回转半径的最大转向角控制

(6)

图6 机器人最大转向角约束

(7)

(8)

l=vn+1*t

(9)

图7 计算机器人运动示意图

3.4 切换目标点的判别方法

人工势场法是通过中间引力点接续的引力作用指导巡检机器人到达最终目标点，当中间节点距离障碍物较远时，可以在到达该目标点一定距离之内切换到下一个中间节点，直到到达最终点。但当节点距离障碍物过近的情况下，会导致无法到达目标点的一定范围之内，从而陷入来回徘徊的情形之中，此时需要在合适的时候跳出极值点，选取下一个节点作为目标点，本文给出的判别方法如下。

图8 切换目标点的判别方法

4 仿真研究

为了验证本文算法的有效性，在CPU为Intel Core3的计算机上用MATLAB软件进行仿真。在200*200的区域内设置变电站工作区域，共8个，其中右下角的障碍物区域为凹多边形区域，仿真目标为寻找一条从起点到终点的安全性较高的可通行路线。参数设定为：巡航机器人宽度为4、长度为10、引力系数α的值为5、斥力势场系数β的值为10、斥力作用范围为10，起止点坐标分别为(10，130)、(150，50)。

仿真结果如图9所示，图中的虚线为Maklink图和遗传算法求解出的可行路径，Dijkstra为预规划路线，实线为本文算法计算出的结果。可以看出，本文算法相较于传统的Maklink图计算出的路径会更为平滑，且与障碍物留有一定的安全距离，从而提高了路线安全性。下面通过相关指标对两个路线进行定量分析。

图9 原算法与改进后的机器人路径规划仿真结果

本文定义障碍物到机器人边界的最小距离为最小安全距离，单纯Maklink求解路线与本文算法结果的最小安全距离与机器人方向角的变化曲线图如图10所示，可以看出原算法某些时刻的最小安全距离小于零，会发生碰撞风险。比较航线角的变化情况也可以发现本文算法得到的路线更为平滑，而原算法会有突然地转角，不符合巡检机器人的运动规律。

图10 规划安全距离和路径方向角曲线图

5 结论

本文提出了一种对机器人进行路径规划的新方式，结合Maklink图和人工势场法得到优化路径，再利用遗传算法迭代寻优，最终可以在包含凹多边形的变电站工作区域中得到一条平滑且安全性高的最短路径，并且可以解决人工势场法本身的局限问题，避免陷入极值点和消除震荡点。最后利用计算机仿真并与原算法对比，验证了本文算法的可行性与有效性。