基于改进Fleury算法的无人机巡线路径规划_束庆霏.pdf

第 42 卷 第 1 期2023 年1 月Zhejiang Electric PowerVol.42，No.01Jan.25.2023基于改进Fleury算法的无人机巡线路径规划束庆霏，蔡佳澄，王思凡，肖美岑，何杨阳，陈宇晨（国网江苏省电力有限公司张家港供电公司，江苏 张家港 215600）摘要：基于图论知识，结合中国邮递员问题的研究方法，采用改进的Fleury算法，添加随机选择元素（主线分支节点随机，支线端点随机），得到近似最优的无人机巡线路径。通过算法结果可知：简单线路的巡线路径一般按照主线杆塔顺序，复杂线路的巡线路径没有明显规律。经验证，所提算法程序实用性强，容错率高，适用于所有简单线路和复杂线路，巡线里程一般比实际里程多出10%30%，效果较为理想。关键词：无人机；路径规划；Fleury算法；图论；中国邮递员问题DOI:10.19585/j.zjdl.202301011 开放科学（资源服务）标识码（OSID）：UAV Path planning for line patrol based on improved Fleury algorithmSHU Qingfei，CAI Jiacheng，WANG Sifan，XIAO Meicen，HE Yangyang，CHEN Yuchen（State Grid Zhangjiagang Power Supply Company,Zhangjiagang,Jiangsu,215600,China）Abstract:The knowledge of graph theory，the research method for the Chinese postman problem，and the improved Fleury algorithm are applied with the addition of random selection elements（i.e.，random branch nodes on the main line and endpoints on the branch line）to obtain the near-optimal UAV patrol paths.The calculation results show that the patrol path of simple lines generally follows the order of mainline towers，while there is no clear rule for the patrol path of complex lines.It is verified that the proposed algorithm procedure is practical and fault-tolerant，applicable to all simple and complex lines；the patrol mileage is generally 10%to 30%more than the actual mileage，ideally effective.Keywords:UAV；path planning；Fleury algorithm；graph theory；Chinese postman problem0引言近年来，在国家数字新基建、能源互联网等战略需求驱动下，无人机业务迎来跨越式的发展。其中，无人机智能巡线是重点项目。张家港市电网目前共有输电线路 1 711 km，配电线路 6 473 km，全社会用电量、工业电量均名列全省乃至全国前茅。面对如此庞大的体量，无人机自主巡线的必要性得到了大大提高1-4。无人机巡线的关键技术有很多，如：超低空飞行、超视距巡检、自主避障、路径规划、远程自主精准降落技术、抗电磁干扰能力、数据安全策略等5-9。本文主要研究无人机巡线路径规划问题。当前国内外学者多用启发式算法进行路径规划。启发式算法是一种基于直观或经验的局部优化算法ADDIN，由大自然的运行规律或者从具体问题的经验和规则中总结而出。在无人机路径规划中，启发式算法通过计算当前位置到目标点的代价值来进行路径选择，当总代价全局最小时，可认为当前路径为全局最优路径。常用的启发式算法有模拟退火算法、虚拟力法、A*算法、势场法、遗传算法等。李游等10综合利用最短距离算法，动态规划算法和A*算法，提出了一种智能航线算法模型，可实现变电站复杂条件下的航线规划。Linhui Cheng11等建立了多基地、可充电续航多无人机道路巡逻任务分配模型，提出了一种time-priority immune clonal selection算法，得到最优任务点序列，并采用时间优先法对任务点序列进行划分。实验结果表明，与粒子群优化算法和改进的动态规划蚁群算法相比，该算法得到的巡线时间大大减少。崔敬魁12利用遗传算法和蚁群算法寻得符合条件的最优巡线路径。李成雷等13基于RRT-connect（快速搜索随机树）算法设计了无人机飞行最优路径，经验证，路径长度接近理论最优值。除了启发式路径规划，也有其他方法用于无人机的路径规划。赵甜甜等14利用百度导航设计了自动巡航机器人。施孟佶等15研究了双无人机第 42 卷协同巡检方案。韦立富等16基于三维激光点云数据，构建模型，生成航线，并评估高危区，设置禁飞区，最终生成可自动往返的飞行路线。Hu等17采用北斗导航系统为无人机巡线提供路径规划。曾懿辉等18首先通过人工巡检，记录关键轨迹的经纬坐标和无人机飞行俯仰角，当自主巡线时，便可以遵照预定的轨迹和飞行俯仰角进行航拍。陈洪亮等19采用基于关键坐标点的路径规划算法对配电网线路进行规划，确保了无人机巡线的高效性和安全性。上述研究工作大多因地制宜，研究了当地电网的无人机巡线路径规划，很多并没有结合实际的线路坐标。本文基于张家港市电网典型线路的杆塔经纬坐标，根据图论知识，结合中国邮递员问题的研究方法，采用改进的Fleury算法进行路径规划。1研究方法本文基于图论和中国邮递员问题的研究方法，对张家港市电网的典型输配电线路进行无人机巡线路径规划。1.1数据处理由于杆塔坐标具有保密性，本文征求到8条典型线路的杆塔坐标用于研究。数据为Excel形式，包含了杆塔名称、杆塔经纬坐标等信息，可利用python语言的pandas库读取Excel，并通过编程得到线路的平面分布图和线路长度。杆塔线路分为主线和支线，某些支线又会分出新的支线，所以不能按顺序将所有的点连接组成线路。本文采用矩阵理论，设 gps是初始值为nn的零矩阵，n为此线路的杆塔数量。两次遍历所有杆塔，若杆塔i、j间存在线路，则记gps（i，j）=1。张家港市输配电线路的杆塔数量大多在100200，计算量不是很庞大，大概几秒就能遍历结束。识别杆塔间是否存在线路的方法如下：太字甲线35-1-14-1-3号是杆塔编号样例，其中，太字甲线为线路名称，“35”为主线第 35 号杆塔，“1-14”为由主线35号杆塔分支出来的第一条支线的第14号杆塔，“1-3”为由支线14号杆塔分支出来的第一条支线的3号杆塔。相邻编号的杆塔在地理位置上也是相邻的，支线的编号包含了分支节点编号，因此可通过正则表达式识别出是否存在线路的相邻杆塔。同样，设置nn的初始零矩阵D，遍历两次杆塔坐标，记D（i，j）=Ds，Ds为两杆塔之间的距离。已知两点的经纬坐标，求两点之间的距离，计算方法如下。假设地球是一个完美的球体，半径为6 371.004 km，记为R。若以0经线为基准，两点的经纬坐标分别为（X1，Y1）和（X2，Y2），则可通过地球表面任意两点的经纬度计算出两点的地表距离Ds（忽略前地球表面地形带来的误差）。张家港市地处北纬3143 12 3202，东经 12021 57 12052，可用式（1）、式（2）计算。C=sinY1sinY2+cosY1cosY2sin(X1-X2)（1）Ds=RarccosC/180（2）式中：为圆周率。1.2模型建立1.2.1建模目标本文的模型旨在建立一套算法流程，工作人员从PMS3.0系统导出杆塔坐标信息，放入模型后自动运行，最后导出近似最优的巡线路径。算法只能得到近似最优路径，因为实际最优路径需遍历所有情况，计算机算力达不到。而得到近似最优耗时较短，适用于所有的简单线路和复杂线路，具有较好的应用价值。1.2.2算法理论无人机巡线需遍历一条线路的主线和所有支线，属于行遍性问题。典型的行遍性问题有中国邮递员问题：邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，希望选择一条行程最短的路线。解决行遍性问题，需参考图论里的欧拉图和Fleury算法。欧拉图：G是一个由点集和边集构成的无向图，经过G的每条边的迹叫做G的Euler迹；闭的Euler 迹叫做 Euler 回路；含 Euler 回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰好通过一次最后回到出发点的图，即不重复地行遍所有的边再回到出发点。根据Fleury算法可得：1）v0V(G)，令W0=v0。90 第 1 期束庆霏，等：基于改进Fleury算法的无人机巡线路径规划2）假设迹Wi=v0e1v1eivi已经选定，则按下述方法从E-e1，ei中选取边ei+1。ei+1和vi相关联。除非没有别的边可选择，否则ei+1不是Gi=G-e1，ei的割边。所谓割边是一条删除后使连通图不再连通的边。3）当第2步不能再执行时，算法停止。本文研究的无人机巡线问题与中国邮递员问题相近，但有以下不同点：邮递员需回到起点，而无人机可以使用移动车载平台，将车载平台直接停在巡线路径终点；邮递员的投递路径具有约束性，必须是两个城镇之间存在道路才能同行，无人机可在任意两个杆塔之间飞行。因此，本文对Fleury 算法进行改进，添加随机选择的元素，并采用python编程，得到近似最优的无人机巡线路径。1.2.3模型假设1）一架无人机每次只巡一条线路，不考虑多条线路一起巡视的情况。2）无人机续航里程大于整个巡线里程。张家港市大多数线路的长度小于15 km，满足无人机的续航里程（见表1），个别线路较长（最长达20.10 km），可采用移动机载平台，充电后再继续巡航，或采用人工巡线和无人机巡线结合的方式。3）整个飞行过程畅通无阻，不考虑线路通道周围的阻碍和两杆塔直线空间内的阻碍。张家港市全境地势平坦，无山岭阻碍无人机飞行，线路通道的障碍主要有树木障碍、交叉线路、路灯障碍等，无人机的感知系统可实现自主避障。4）飞行环境是无风环境，无人机匀速飞行。5）无人机感知系统（见表1）正常，可始终保持跟踪导线飞行。6）无人机定位系统（见表1）正常，可准确定位目标杆塔。张家港在役无人机的部分参数见表1，部分缺失数据厂家未提供。1.2.4算法流程1）根据杆塔经纬坐标得到线路分布的平面二维图。2）设置 nn 的初始零矩阵 gps，遍历所有杆塔，若两杆塔 i、j 之间存在线路，则标记 gps（i，j）=1。3）设置nn的初始零矩阵D，遍历所有杆塔，计算两杆塔 i、j 之间的地表距离 Ds，令 D（i，j）=Ds。4）遍历所有杆塔得到线路的起点和终点。5）设置空白路径route，线路的起点（或终点）作为路径起点，并设置当前杆塔位置state，state初始值为路径起点，以state为基准，遍历所有的杆塔。若遍历到杆塔i与杆塔state之间存在线路，即gps（state，i）=1，则将杆塔i加入路径route，对于存在支线的线路节点，设置随机选择，并将选择支线的概率设置大一点，选择支线的概率是选择主线概率的23倍，因为对于大部分线路，优先巡完支线再回到主线继续巡线是一个比较好的选择。同时将gps（state，i）和gps（i，state）更新为0，将当前杆塔位置state更新为i。若遍历完所有杆塔，不存在与杆塔state相连的杆塔，则搜寻state附近的杆塔，该杆塔需满足条件：有其他杆塔与之相连。搜寻13个与杆塔stat