基于采样的输电线路避障规划算法研究.pdf

123基于采样的输电线路避障规划算法研究http:/ 工程勘测 增刊1 的地形勘测结果进行路径规划。为了提高规划效率以及避免重复改线造成的经济损失，探索与选择优秀的路径规划算法是一条必经之路1，也是当前电力勘测线路规划的难点之一，具有重要的应用价值和研究意义。DOI：10.13500/j.dlkcsj.issn1671-9913.2023.S1.023基于采样的输电线路避障规划算法研究崔东东，陈 醒，郝安华(中国能源建设集团辽宁电力勘测设计院有限公司，辽宁沈阳110000)摘要：避障路径规划算法为电力勘测线路优化提供理论支持，具有重要的现实意义。借助MATLAB R2019a平台，以简单和复杂的仿真地形作为研究对象，采用 RRT、RRT-Connect、RRT*、Informed-RRT*4 种采样算法进行避障路径规划设计。实验结果表明：在障碍区地形简单和复杂条件下，RRT-connect 算法的规划所需时间最少，规划效率高，Informed-RRT*算法规划的路径是最优结果，随着障碍区地形复杂程度的提高，4 种算法的规划效率均表现为下降趋势。关键词：输电线路；避障规划算法；RRT；RRT-Connect；RRT*；Informed-RRT*中图分类号：P2 文献标志码：A 文章编号：1671-9913(2023)增刊1-123-07Research on Sampling Based on Obstacle Avoidance Planning Algorithm for Transmission LinesCUI Dongdong,CHEN Xing,HAO Anhua(China Energy Construction Group Liaoning Electric Power Survey&Design Institute Co.,Ltd.,Shenyang 110000,China)Abstract:The obstacle avoidance path planning algorithm provides theoretical support for the optimization of power survey lines,which has important practical significance.With the help of MATLAB R2019a platform,this paper takes simple and complex simulated terrain as the research object,and adopts four sampling algorithms of RRT,RRT-Connect,RRT*,and Informed-RRT*to plan and design obstacle avoidance paths.The experimental results show that under the simple and complex terrain conditions of the obstacle area,the planning time of the RRT-connect algorithm is the least,the planning efficiency is high,the path planned by the Informed-RRT*algorithm is the optimal result,and the planning efficiency of the four algorithms shows a downward trend with the increase of the terrain complexity of the obstacle area.Keywords:transmission line;obstacle avoidance planning algorithm;RRT;RRT-Connect;RRT*;Informed-RRT*收稿日期：2023-02-28 第一作者简介：崔东东(1993)，男，硕士，工程师，主要从事电力勘测等工作。0引言电力建设作为国民经济发展不可缺少的支柱，为各行各业能够健康、稳定运行提供了重要保障。建设电力线路的首要任务是根据实时124http:/电 力 勘 测 设 计增刊1电力勘测线路规划的核心在于快速、精确地避开障碍物，得到两地之间最优的送电路径。目前常见的路径规划算法包括基于搜索的Dijkstra 算法、A*算法以及基于采样的快速扩展 随 机 树(rapidly exploring random tree,RRT)算法、双向扩展平衡的连结型双树(rapidly exploring random tree-connect,RRT-Connect)算法、渐进最优快速扩展随机树(rapidly exploring random tree star,RRT*)算法、椭圆采样的渐进最优快速扩展随机树(informed rapidly exploring random tree star,informed-RRT*)算 法，其 中，Dijkstra 算法、A*算法因其规划效率普遍较低且不适应复杂地形而被较少应用于实际规划中2。鉴于 RRT 算法无需对搜素区域和系统进行划分建模，可以在复杂环境下实现路径规划的优点，其在避障路径规划应用上得到了各行各业学者的追棒，并衍生出了多种改进方法3。KARAMAN 和 FRAZZOLI 于 2010 年 提 出 了RRT*算法，该算法将新增节点半径 R 的范围内随机树上所有的节点作为备选节点，提高了路径规划效率以及解决了 RRT 算法生成避障路径时存在非最优的问题4。KUFFNER 和LAVALLE 于 2013 年提出基于多树搜索的双向搜索算法(Bi-RRT)，该算法通过在起始点和目标点并行生成两棵随机树的方式来提高算法的扩展效率和收敛速度5。不久他们又提出了在节点扩展时采用指向性扩展策略的 RRT-connect算法，将其与桥梁检测(Bride Test)算法融合，很好地解决了 RRT-connect 在障碍物较窄空间中采样难的问题6。GAMMEL 和 SRINIVASA 于2014 年提出了 Informed-RRT*算法，该算法的先进性在于引入的椭圆状态子集能够对采样空间进行限制和优化，并最终获得最优路径，但其存在的缺点是搜索时间较长7。由上述学者的研究成果可以看出：不同的路径规划算法都存在一定的局限性，需要根据路径的实际情况去选择对应的规划算法。为了探索 4 种基于采样的规划路径算法在不同地形条件下的电力线路避障路径规划的能力与优势，本文借助 MATLAB R2019a 平台，以简单和复杂的仿真地形作为研究对象，验证 4 种算法在电力勘测线路避障路径规划中的适用性和可行性，并对得到的结果进行分析。1算法的基本原理主要对 RRT 算法、RRT-connect 算法、RRT*算法、Informed-RRT*算法的基本理论、以及实现步骤进行叙述。1.1 RRT算法原理RRT 算法生成路径的核心思路是：在状态空间中，将起始节点作为随机扩展搜索树的根节点，采用增量采样的方式随机获取一个采样点，并使随机树向着采样点位置扩展生长出与障碍物区域无碰撞的树节点，重复上述过程，直到达到目标点为止8。RRT 随机树进行扩展的流程如图 1 所示。RRT 算法的具体流程如 图 2 所示。?图1 RRT随机树扩展流程示意图?图2 RRT算法具体流程125基于采样的输电线路避障规划算法研究http:/ 工程勘测 增刊1 1.2 RRT-connect算法原理RRT-connect 算法即为连接型 RRT 算法，该算法是在 RRT 算法的基础上，在目标点处也生成一棵随机树，与根节点生成的随机树一起进行路径的搜索9。每一次迭代中，开始时的步骤和原始 RRT 算法一样，都是利用增量的方式采集随机点，然后进行扩展，将扩展得到的新节点作为另一棵随机树扩展的方向，若中间未遇到障碍物，则继续向前扩展，直到与另一棵树的扩展节点相连为止，结束路径搜索。这种双向的 RRT 技术具有良好的搜索特性，比原始 RRT 算法的搜索速度、搜索效率有了显著提高，被广泛应用。如图 3 所示给出了 RRT-connect 算法扩展的具体流程示意图。VsZsVgZgZnearZnewZrand(a)双随机树节点扩展 ZsZgZnew(b)双随机数节点连接图3RRT-connect算法具体流程由图 3 可以看出：RRT-connect 算法相较于之前的 RRT 算法在扩展时步长更长，使得随机树的扩展速度加快。另一方面，RRT-connect 算法中两棵随机树产生的节点朝着对方的方向不断地扩展，而不是像一棵随机树扩展时杂乱无章，尤其是在两棵随机树的根节点和目标节点处于障碍物限制区域时，两棵树可以在朝着对方扩展时而逃离障碍物限制区。这种带有启发性的扩展使得树的扩展更加具有明确性，提高了路径规划效率。1.3 RRT*算法原理RRT*算法是在 RRT 算法的基础上加入了寻优过程，解决了 RRT 算法生成路径非最优的问题。该算法不仅将利用增量采样得到的新节点加入到随机树中，并且搜索以新节点为圆心的区域中是否存在新的父节点，若新节点与搜索到的新的父节点之间的路径更小，则将新节点与新的父节点进行重连10。此外，搜索以新节点为圆心的区域中是否存在其他的树节点，并把新的节点作为该树节点的父节点，若二者之间连接得到的路径距离比之前的短，则进行随机数的重连操作11。RRT*算法的路径寻优过程如图 4 所示，具体的算法流程如图 5 所示。XnewXnearestXstart(a)节点扩展 XnewXnearestXminXstart(b)父节点重连 XnewXnearestXminXstart(c)随机树重连 图4RRT*算法路径寻优过程126http:/电 力 勘 测 设 计增刊1Start?Z=(V,E)Prand()()sampleXrand?goalrandXX?nearestrandXX?newX?freenewXX?rXXinew?-nearX?),(cosminminnewineariXXtXXX?minXXnew?ZXnewFinishNYNYY图5RRT*算法具体流程图 5 RRT*算法具体流程中：Z 表示随机数；V 表示迭代过程中符合约束节点的集合；E 表示节点连线构成边的集合；sample 表示随机采样函数；Xrand 表示采样得到的随机点；Xgoal表示目标点；Xnearest 表示利用 Nearest 函数得到的离随机点 Xrand 最近的节点；Xnew 表示利用 steer 函数以 Xnearest 为基点，沿着随机点Xrand 的方向生成的一个新节点；Xnear 表示符合约束条件的节点的集合；Xmin 为路径成本代价最低的节点。1.4 Informed-RRT*算法原理Informed-RRT*算法的优势在于引入了直接对椭圆状态子集范围内的节点进行随机采样，相较于 RRT*算法，Informed-RRT*算法的优势主要有2：保留了 RRT*算法的完备性和渐进最优性；利用基于椭圆状态子集的采样方法，提高了路径规划效率；路径优化的能力优于RRT*算法。图 6 给出了基于椭圆状态子集采样方法的流程，其中 cmin为椭圆两个焦点之间的距离，也是随机树中根节点与目标节点之间路径的理想距离12；cbest为椭圆的长轴；c2best-c2min为椭圆的短轴。CminCbestXstartXgoalC2best?C2min?图6基于椭圆状态子集的采样空间2仿真环境及算法伪代码2.1 仿真环境为了验证 4 种算法在电力勘测线路避障路径规划的优势，文章借助 MATLAB R2019a 平台进行简单与复杂地形进行采样对比实验，所用的软硬件配置见表 1 所列。表1软硬件配置项目配置处理器Intel(R)Core(TM)i7-8700 CPU 3.20GHZ 3.19GHZ内存8.00 GB系统版本Windows 10编程平台MATLAB R2019a2.2 算法伪代码由于 RRT 算法与 RRT-connect 算法的代码基本一致，故此处仅给出了 RRT 算法的伪代码，RRT-connect 算法的伪代码不再赘述。1)RRT 算法伪代码如下：RRT AlgorithmINPUT:M,Zinit,Zgoal;Result;A path T from Zinitto Zgoal;Result:A path T from ZinittoZgoal;for i=1 to n doZrand Sample(M);Znear Near(Zrand,T);Znew Steer(Zrand,Znear,StepSize);EiEdge(Znew,Znear);if CollisionFree(M,Ei)then T.addNode(Znew);T.addEdge(Ei);if Znew=Zgoal then Success();127基于采样的输电线路避障规划算法研究http:/ 工程勘测 增刊1 2)RRT*算法伪代码如下：RRT*AlgorithmINPUT:M,Zinit,ZgoalResult:A path T from Zinit to Zgoalfor i=1 to n doZrand Sample(M);Znear Near(Zrand,T);Znew Steer(Zrand,Znear,StepSize);EiEdge(Znew,Znear);if CollisionFree(Znew)then T.addNode(Znew);Znear Near(Znew,T);Zmin ChooseParent(Znear,Znear,Znew);T.addNodEdge(Zmin,Znew);T.rewire();3)Informed-RRT*算法伪代码如下：Informed-RRT*AlgorithmSample(Zstart,Zgoal,cmax)if cmax thencmin Zgoal-Zstart2;Zcentre (Zstart+Zgoal)/2;；ri i=2,n(c2max-c2min)/2;Ldiag r1,r2,rn;Zball SampleUnitNBall;Zrand (CLZball+Zcentre)Z;elseZrand U(Z);return Zrand;3仿真实验结果及分析为 了 测 试 RRT 算 法、RRT-connect 算 法、RRT*算法、Informed-RRT*算法在电力勘测线路路径规划的避障性能，本节分别在简单地形和复杂地形进行仿真实验，并对得到的结果进行分析。3.1简单地形仿真实验结果及分析仿真的环境区域设置为 60 km50 km，根节点的位置为(10，10)，目标点的位置为(50，40)，总共设置了 6 个障碍物。障碍物的位置坐标分别为障碍物 113,18;19,18;19,21;16,24;13,21，障碍物 230,25;36,25;38,28;32,28，障碍物 340,36;44,36;44,40;40,40，障碍物 440,30,2，障碍物 535,15,3，障碍物 625,10,3。50604030201050403020100Y?/kmX?/km(a)RRT算法 50604030201050403020100Y?/kmX?/km(b)RRT-connect算法 50604030201050403020100Y?/kmX?/km(c)RRT*算法 50604030201050403020100Y?/kmX?/km(d)informed-RRT*算法 图7不同算法路径规划结果图 7 为 4 种采样算法得到的路径规划图，其中蓝色的小点表示随机数利用增量采样的方法得到的随机点，红色的图形表示路径上的障碍物，2 个红色的正方形小块表示初始根节点位置和目标节点的位置，黑色线条表示得到的规划路线。分析图 7 不同算法路径规划结果可以得出：RRT 算法规划的结果不是最优路径；RRT-connect 算法的规划是从根节点与目标节点同时 出 发 的，效 率 较 高；相 较 于 RRT*算 法，informed-RRT*算法缩小了路径搜索的范围，且128http:/电 力 勘 测 设 计增刊1规划出的路径是最优的。由于每次规划路径均不一致，文章共做了12 次实验，并将其结果进行了统计，见表 2 所列。表2 算法对比数据算法名称迭代次数均值搜索时间均值/s路径成本均值RRT376.8890.5370.36RRT-connect50.2512.2566.95RRT*610.83363.2866.84Informed-RRT*378.86225.4265.24通过对表 2 的数据进行对比分析可得：在迭代次数方面：RRT*算法所需迭代次数最多，RRT-connect 算法所需的迭代次数最少。在搜素时间均值方面：RRT-connect 算法所需时间最少，RRT*算法所需时间最多。在路径成本均值方面：Informed-RRT*算法的路径最短，RRT 算法的路径最长，即 Informed-RRT*算法可以规划出最优路径。3.2 复杂地形仿真实验结果及分析仿真的环境区域设置为 80 km60 km，根节点的位置为(12，10)，目标点的位置为(64，42)，总共设置了 11 个障碍物。障碍物的位置坐标分别 为 障 碍 物 140,14;48,14;48,18;44,22;40,18，障 碍 物 240,50;48,50;48,46;44,42;40,46，障 碍物 320,28;24,24;28,28;24,32，障 碍 物 448,30;60,30;60,35;48,35，障碍物 520,16,3，障碍物630,8,2，障碍物 730,14,2，障碍物 836,38,2，障碍物 940,26,2，障碍物 1054,13,4，障碍物1154,53,4。图8为4种采样算法得到的路径规划结果。50606070804030201050403020100Y?/kmX?/km(a)RRT算法 50606070804030201050403020100Y?/kmX?/km(b)RRT-connect算法 50606070804030201050403020100Y?/kmX?/km (c)RRT*算法 50606070804030201050403020100Y?/kmX?/km(d)informed-RRT*算法 图8不同算法路径规划结果分析图 8 不同算法路径规划结果可以得出：RRT 算法规划的结果路径不是最优路径；RRT-connect 算法的规划是从根节点与目标节点同时出发的，效率较高；相较于 RRT*算法，informed-RRT*算法由于引入了椭圆状态子集，缩小了路径搜索的范围，且规划出的路径是最优的。表 3 给出了 12 次仿真实验得到的统计 结果。129基于采样的输电线路避障规划算法研究http:/ 工程勘测 增刊1 表3算法对比数据算法名称迭代次数均值搜索时间均值/s路径成本均值/kmRRT500.35133.9580.36RRT-connect100.1221.2576.95RRT*665.89464.3976.84Informed-RRT*478.36305.6875.24通过对表 3 的数据进行对比分析可得：实验结论和表 2 的结论基本一致，即无论是简单障碍地形还是复杂障碍地形，RRT-connect 算法规划所需要的时间最少，Informed-RRT*算法规划处的路径最优。随着地形的复杂程度增高，各种算法的规划效率相较于简单地形均表现为下降趋势。4结论论文借助 MATLAB R2019a 平台，以简单和复杂障碍物地形为仿真条件，测试 4 种不同的路径规划采样算法在电力勘测线路避障中的性能。得出如下结论：1)RRT-connect 算法因其从根节点和目标节点分别进行避障路径的随机树采样，在规划效率上是 4 种算法中最优的。2)Informed-RRT*算法引入了椭圆状态子集的采样方法，相较于 RRT*算法，缩小了采样范围，节省了规划时间。由于该算法在采样时受到椭圆状态空间的限制，其规划得到的路径是 4 种算法中最优的。3)随着障碍区地形复杂化程度的提高，4 种算法的规划效率相较于简单地形，均表现为下降趋势。参考文献1 FULVIA QUAGLIOTTI 戴光明.避障路径规划的算法研究D.武汉：华中科技大学，2004.2 张玉伟，左云波，吴国新，等.基于改进Informed-RRT算法的路径规划研究J.组合机床与自动化加工技术，2020(7)：21-25.3 LIN W M，TU C S，YANG R F，et al.Particle swarm optimization aided least-square support vector machine for load forecast with spikesJ.IET Generation，Transmission&Distribution，2016，10(5)：1145-1153.4 S KARAMAN，M R WALTER，A PEREZ，et al.Anytime motion planning using the RRT*C/International Conference on Robotics and Automation，IEEE，2011：1478-1483.5 A H QURESHI，SABA MUMTAZ，K F IQBAL.Triangular geometry based optimal motion planning using RRT*-motion plannerC/Advanced Motion Control(AMC)13th International Workshop on，IEEE，Japan，2014：380-385.6 M JORDAN，A PEREZ.Optimal Bidirectional Rapidly-Exploring Random TreesJ.Computer Science and Artificial Intelligence Laboratory，Massachusetts Institute of Technology，Cambridge，2013，21(1)：12-29.7 J D GAMMELL，S SRINIVASA.BARFOOT.Informed RRT*：Optimal sampling-base path planning focused via direct sampling of an admissible ellipsoidal heuristicC/International Conference on Intelligent Robots and Systems I-EEE，shanghai，2014：2997-3004.8 孔迎盈.机器人路径规划算法的研究D.上海：复旦大学，2012.9 AOWABIN RAHMAN，VIVEK SRIKUMAR，AMANDA D SMITH.Predicting electricity consumption for commercial and residential buildings using deep recurrent neural networksJ.Applied Energy，2018.10 王嘉琦.基于改进RRT*算法的无人机避障路径规 划D.南昌：南昌航空大学，2019.11 朱宏辉，明瑞冬，朱轶.基于改进RRT*算法的路径规划J.武汉理工大学报，2017，39(2)：72-76.12 代军，李志明，李艳琴，等.基于改进Informed-RRT*算法的机器人路径规划J.河南理工大学学报(自然科学版)，2022，41(4)：95-100.(编辑 卢靖冉)