时间最优的无人机巡检避障路径规划_田小壮.pdf

计算机与现代化JISUANJI YU XIANDAIHUA2023年第3期总第331期文章编号：1006-2475（2023）03-0043-05收稿日期：2022-05-08；修回日期：2022-05-26基金项目：国家自然科学基金资助项目（61903033）；新疆电力公司科技项目（5230CD20006U）作者简介：田小壮（1972），男，宁夏固原人，高级工程师，本科，研究方向：变电站智能化，E-mail：；李松（1986），男，湖北随州人，工程师，本科，研究方向：变电智能化，E-mail：；付国萍（1988），女，山东肥城人，工程师，本科，研究方向：变电智能化，E-mail：。0引言随着无人机软硬件技术的不断成熟，无人机巡检已广泛应用于输电线路1、变电站2、油气管道3、铁路4、矿井5等领域。为了实现无人机智能巡检，需要根据巡检任务和飞行环境，为无人机规划生成安全可行的飞行路径，以保障无人机飞行安全6-7。无人机路径规划方法主要包括基于搜索的方法、基于采样的方法和基于优化的方法等8-10。基于采样的方法中，快速扩展随机树算法原理简单，节点扩展不需预处理，具有较强的搜索能力11-14，但该类算法由于随机产生采样点导致其路径结果具有随机性，与实际应用对结果确定性的期望存在矛盾15。基于优化的方法将路径规划建模为静态数值优化问题，然后主要采用进化类16-18或群体类19-21算法进行求解，具有获得全局最优解的能力，但算法耗时相对较大，而且也具有随机性。基于搜索的方法中，A*算法是一种具有代表性的启发式搜索算法，通过增加启发信息，大幅减少了搜索节点规模，具有储存空间占用小和路径规划效率高等优点，在工程实际中得到了广泛应用22-24。由于A*算法具有计算效率高、最优性可保证、结果确定性等优势，因此本文以A*算法为基础，开展巡检避障路径规划方法研究。针对不同的应用需求，时间最优的无人机巡检避障路径规划田小壮1，李松1，付国萍1，谭启昀2，单德帅1，王伟光1，王祝3（1.国网新疆电力有限公司超高压分公司，新疆 乌鲁木齐 830001；2.北京御航智能科技有限公司，北京 100193；3.华北电力大学自动化系，河北 保定 071003）摘要：无人机执行实际任务时，完成时间是衡量任务效能的重要指标，而路径规划方法一般以路径长度最小为目标，难以准确直接地反应完成任务时间。对此，在构建路径时间代价的近似计算方法基础上，本文提出一种最小化任务时间的无人机避障路径规划算法。通过路径跟踪特性试验，获取不同机动方式下的飞行时间，作为路径搜索过程中的代价计算依据。设计节点扩展方式和代价函数计算方法，提出一种改进A*搜索算法以实现障碍规避和路径时间优化。通过随机场景下的仿真试验对所提方法的有效性和性能优势进行验证。最后以变电站巡检为例，验证改进算法能够引导无人机以更短的时间完成避障巡检。关键词：路径规划；无人机；时间最优；障碍规避；A*搜索中图分类号：TP391.8文献标志码：ADOI：10.3969/j.issn.1006-2475.2023.03.008Time-optimal Obstacle Avoidance Path Planning for UAV InspectionTIANXiao-zhuang1，LISong1，FUGuo-ping1，TANQi-yun2，SHANDe-shuai1，WANGWei-guang1，WANGZhu3（1.State Grid Xinjiang Extra-high Voltage Company，Urumqi 830001，China；2.Beijing Yuhang Intelligent Technology Co.，Ltd，Beijing 100193，China；3.Department of Automation，North China Electric Power University，Baoding 071003，China）Abstract：For real-world missions by quadrotors，complete time is an important index to measure the mission effectiveness.However，the path planning methods usually aim at the minimum path length，which can not reflect the task time accurately anddirectly.Thus，based on the approximate computation method of path time costs，a minimum-time obstacle-avoidance path planning algorithm is proposed for unmanned aerial vehicles.Through path tracking tests，the flight time of different maneuver stylesis acquired and is used as the basis for cost calculation in the path search process.By tailoring the node expansion mode and cost-function computation method，a modified A*algorithm is proposed to achieve obstacle avoidance and path-time optimization.The simulations in radon scenarios are conducted to test the effectiveness and prior performances of the proposed method.Finally，taking substation inspection as an example，it verifies that the improved path planning method can guide the quadrotor tocomplete the task within a less time.Key words：path planning；unmanned aerial vehicles；time optimal；obstacle avoidance；A*search计算机与现代化2023年第3期A*算法已发展出双向A*25、动态A*26、即时A*27、Theta*28等改进算法，但它们主要通过对节点扩展方式进行定制改进，提高算法在特定条件下的计算效率，本文则主要从改进代价函数的角度展开研究，以获得时间最优的路径规划结果。面向实际的无人机应用，最小化飞行时间是一类常用的性能指标。但是，路径规划为了保证计算效率，仅考虑代数方程形式的质点运动约束，无法直接衡量飞行时间。对此，一种直接的方式是假设飞行速度恒定，以飞行距离近似描述飞行时间，但该方式没有考虑转弯机动引起的时间增量。文献 29 在基本代价函数的基础上，引入人为设定的转弯代价，减少路径结果的转弯次数，从而减少路径时间，但人为设定的代价与实际时间相差较大。为了在路径规划中更准确地优化无人机的飞行时间，本文提出一种改进A*算法，记为T*算法，其通过定制设计基于试验数据的飞行时间代价计算方法和节点扩展方法，在保证对环境障碍进行有效规避的前提下，实现时间最优的快速路径规划。1问题建模无人机避障路径规划需要在满足避障约束和运动约束的条件下，生成从给定起点到终点的可行路径，并使得特定的性能指标达到最优或次优，其示意图如图1所示。对于时间最优路径规划问题，即期望使得无人机沿规划路径运动时，从起点到达目标点所对应的飞行时间最短。图1无人机避障路径规划示例无人机避障路径规划考虑的目标函数和约束条件如下所述。1）路径规划目标。无人机的飞行路径L可由一系列路径点表示，记为L=Pi，i=1，2，N，其中Pi表示第i个路径点，N为路径点的总数量。时间最优路径规划问题的目标函数可表示为：min tf=i=0N-1ti（1）其中，tf表示无人机完成整条路径飞行的时间，ti表示第i段路径的飞行时间，第i段路径即为第i个和第i+1个点间的路径。2）障碍规避约束。无人机执行任务过程中，需要对环境中的障碍进行规避，保障飞行安全。采用三维栅格地图对环境进行建模，其中存在障碍物的栅格被设置为不可飞行区域，不存在障碍的栅格设置为可飞行区域，记为Cfree。为了满足障碍规避约束，要求路径点必须在可飞行区域Cfree内，如式（2）：Pifree（2）在路径搜索过程中，可以根据节点位置和栅格地图信息，通过查询的方式确定节点是否满足障碍规避约束。3）无人机飞行约束。无人机在飞行过程中，由于受到运动学和动力学的约束，无人机无法瞬时进行反向飞行。对于时间最优路径规划，应尽量避免无人机大幅减速进行方向调整，因此在无人机路径搜索过程中，将可行扩展空间限制为沿当前速度方向确定的半空间。图2给出了下一航点可行半空间的示意图。图中，无人机当前点的速度方向向右，则下一航点的可达范围为当前点右侧的半空间，而左侧的半空间认为是下一航点所不可达的，以减少无人机在路径跟踪时的速度变化，提高无人机的平均飞行速度。图2无人机下一航点可行空间2时间最优的改进A*算法面向最小化飞行时间的目标，在A*算法基础上，本文设计节点扩展方式、节点代价计算方法，提出一种时间最优的改进A*算法，记为T*算法。2.1 算法基本流程图3基于T*算法的避障路径规划流程T*路径规划算法在A*搜索框架的基础上，通过节点扩展方式和代价函数的设计，实现飞行时间最小目标点路径点障碍物 速度方向不可扩展空间可行扩展空间开始OPEN表为空？当前节点是否为目标点？扩展新节点更新 OPEN 表和CLOSE表输出路径结束是是否起点放入OPEN表CLOSE表置为空节点可行性检测OPEN表中时间代价最小节点作为当前节点否可行节点的时间代价计算442023年第3期田小壮，等：时间最优的无人机巡检避障路径规划化的目标。T*算法流程如图3所示，其关键步骤包括：1）初始化：起点放入待扩展节点列表（OPEN表），已扩展节点列表（CLOSE表）置空。2）节点选择：根据节点代价值，从OPEN表中弹出时间代价最小的节点，作为当前节点。3）节点扩展：根据设定的节点扩展方法，搜索获得当前节点的相邻节点。4）节点检测：判断扩展节点是否满足约束和是否已被扩展。5）列表更新：对通过检测的新节点，计算其代价值并放入OPEN表，同时将当前节点放入CLOSE表。2.2 节点扩展方式T*算法在节点扩展中，考虑到无人机飞行约束，扩展的邻居节点必须位于图3所示的半空间内，确定当前节点可达的邻居节点。扩展节点坐标的一般计算方式如式（3）：cnew=cthis+c，c x，y，z（3）其中，c用于统一化表征x、y、z坐标，cthis表示当前节点的坐标，cnew表示扩展的新节点坐标，c表示坐标增量，其取值需根据扩展方式确定。对于全向扩展方式，c的取值范围为-1，1，考虑半空间约束下的扩展时，c的取值范围为：|c cmin，cmaxcmin=0，cthis-cf 0-1，cthis-cf 0cmax=0，cthis-cf 01，cthis-cf 0（4）其中，cf表示父节点的坐标。根据式（4）可知，当前节点的新扩展节点不会位于父节点的半空间内。图4以爆炸图的形式给出了半空间约束下节点扩展的一个示例，其中填充的中心点表示当前节点，其左侧节点为父节点，实线节点为满足半空间约束的扩展节点，虚线节点为不可扩展节点。由图可知，由于父节点到达当前点的方向指向x轴方向，因此可扩展节点均位于当前点的右半空间，即可扩展节点的x值均大于等于当前点x值。图4满足半空间约束的扩展节点示意图2.3 节点代价函数路径搜索过程中，节点代价值f根据累计代价g和启发代价h计算得到，如式（5）所示。其中，累计代价g表示从起点到当前点的飞行时间，启发代价h表示从当前点到目标点的估计时间，g和h为权重系数。f=gg+hh（5）为了实现时间最优，T*算法中的节点代价基于飞行时间来表示，如式（6）所示。考虑无人机的运动特性，从父节点飞抵当前节点时，随着飞行对应的水平转角、垂直转角的高度变化值h的不同，飞行时间往往是不同的。对此，本文通过路径跟踪试验来更准确地获得不同转角和高变化下的飞行时间，具体见2.4节。gthis=gf+tf this(,h)（6）其中，gf表示父节点的累计时间代价，tfthis（，h）表示不同机动情况下父节点到当前节点的时间代价。启发代价h的计算方式如式（7）所示，式中lh表示当前点到目标点的估计距离，Vmax表示无人机最大速度。hthis=lh/Vmax（7）其中，估计距离lh按式（8）计算。|lh=(3-2)lmin+(2-1)lmid+lmaxlmin=min(|x|，|y|，|z|)lmax=max(|x|，|y|，|z|)lmid=|x|+|y|+|z|-lmin-lmax（8）其中，x、y、z为当前节点与目标点在不同方向的坐标差。2.4 基于路径跟踪的代价计算为了获取T*算法搜索时节点代价计算的所需参数，对不同的节点扩展路径进行跟踪试验，测试不同机动下的飞行时间。本文无人机路径跟踪试验在ROS和Gazebo环境下进行。无人机路径跟踪控制基于广泛应用的PX4控制器，无人机选用3DR-IRIS，无人机的最大速度设为1 m/s，无人机最大加速度设为2 m/s2。由于多旋翼无人机在水平方向运动具有对称性，垂直方向不具有对称性，所以根据不同的水平机动和垂直机动形式，设定不同的扩展路径跟踪试验，路径长度均归一化为1 m。考虑控制误差，每个扩展路径进行10次跟踪试验，获得跟踪飞行时间的均值，得到的统计结果如表1所示。其中，start表示由无水平运动转为有水平运动，stop表示由有水平运动转为无水平运动。表1无人机路径跟踪试验结果（，h）（0，0，0）（/2，0，0）（stop，/2，1）（stop，-/2，-1）时间/s1.311.721.951.33（，h）（start，/2，0）（0，0，1）（0，/2，0）（start，0，-1）时间/s1.632.001.690.983试验结果与分析为了说明所提T*算法的有效性和性能优势，分别基于随机障碍场景和变电站巡检实例，对基于T*算法和A*算法的路径规划结果进行对比测试。3.1 随机场景测试试验随机场景测试试验中，将起始点设置为原点，目标点在非障碍区内随机生成，获得100组测试场景。xzy45计算机与现代化2023年第3期然后针对每组场景，分别采用T*和A*算法进行路径规划，记录2种算法所生成结果的路径长度和路径时间指标，以验证T*算法的有效性及其结果在路径时间上的优势。图5和图6给出了100次试验所得的路径长度和路径时间数据曲线。根据图5可知，2种算法针对100次随机场景所生成路径的长度基本相同，100次的均值为51.53 m。但根据图6中的数据可知，T*算法所生成路径对应的飞行时间均小于或等于A*算法所生成路径的时间，均值分别为74.45 s和66.90 s。这是因为从路径长度角度，结构化环境中常常存在不唯一的最优路径，而考虑时间最短的路径规划可以从上述路径中选出转弯角度更小的路径，通过减少机动次数和幅值，有利于提高跟踪飞行的速度。图5100次测试试验的路径长度结果图6100次测试试验的路径时间结果为了具体分析2种算法的特点，以一组测试结果为例进行分析，测试得到的路径结果见图7。考虑路径规划得到的时间代价估计值并不能无误差地反应实际飞行时间，对规划路径进行跟踪飞行试验，以更准确地对比路径时间指标，跟踪试验获得的飞行时间和速度曲线如图8所示图7中，T*算法和A*算法生成的路径长度均为75 m，但A*生成路径的跟踪飞行时间为105.84 s，而T*规划的路径飞行时间计算值则为95.36 s。通过分析路径结果图可知，由于T*算法以飞行时间代价为搜索指标，且构建时间代价时考虑了不同机动方式的影响，从而规划生成的路径中包含的转弯机动更少，有利于无人机保持更快的平均速度。图8所示的跟踪速度曲线进一步验证了上述结论，即当无人机沿T*规划的路径飞行时，速度变化曲线更加平缓，平均飞行速度更快，无人机完成相同长度路径的跟踪飞行时间更短。图7无人机路径规划结果图8无人机跟踪飞行速度曲线3.2 变电站巡检路径规划试验为了进一步说明所提算法在实际应用中的有效性，以变电站巡检路径规划为例进行试验测试。试验中采用的变电站模型如图9所示。无人机执行巡检任务时，先从给定起点起飞，然后根据设定的任务目标点，不断利用路径规划算法生成飞行路径，并控制无人机沿规划路径进行跟踪飞行，依次抵达设定的一系列任务点，最终返回起始点。图9变电站三维模型示例针对上述变电站巡检任务，基于T*和A*算法进行路径规划及跟踪飞行所得的飞行路径结果分别如图10和图11所示，其中变电站以三维点云的形式呈现，图中五角星表示设定的巡检任务点，0号点为起始点和返航点。由图可知，无人机在T*算法或A*算路径长度/m试验次数/次020406080100120100806040200A*T*时间代价/s150100500020406080100020406080100试验次数/次A*T*010203040 x20100yz403020100T*A*462023年第3期法所规划路径的引导下，均能够依次抵达12个任务点，并与变电站的设备保持有效的安全距离，保证无人机的飞行安全，顺利完成变电站巡检任务。但同时，通过对无人机从起飞、巡检、降落的任务总时间进行统计，得到基于T*和A*算法实现巡检任务的完成时间分别为407.13 s和432.49 s，即基于T*算法完成上述巡检任务可以减少约6.23%的巡检时间。根据无人机巡检应用实例可知，面向时间最优的T*算法能够生成飞行时间更短的无人机任务路径，有利于提高无人机执行任务的效率。图10基于T*算法的变电站巡检飞行路径图11基于A*算法的变电站巡检飞行路径4结束语针对无人机巡检避障应用需求，本文提出了一种时间最优的T*路径规划算法。以路径时间最短为目标，定制设计路径搜索过程中的节点扩展方式和节点代价计算机制，实现无人机跟踪飞行时具有更快的平均速度，从而缩短无人机的飞行时间。通过仿真试验验证了T*算法的有效性，仿真结果表明该算法可以生成飞行时间更短的无人机避障巡检路径，能够减少无人机执行任务的所需时间。参考文献：1 隋宇，宁平凡，牛萍娟，等.面向架空输电线路的挂载无人机电力巡检技术研究综述 J.电网技术，2021，45（9）：3636-3648.2 胡金磊，朱泽锋，林孝斌，等.变电站无人机机巡边缘计算框架设计及资源调度方法 J.高电压技术，2021，47（2）：425-433.3 陈艳，吴佳欢，任新华，等.无人机巡查技术在油田集输系统的应用研究 J.石油和化工设备，2021，24（12）：57-59.4 姚建平，蔡德钩，安再展，等.铁路无人机巡检研究应用现状与发展趋势 J.铁道建筑，2021，61（7）：1-4.5 江传龙，黄宇昊，韩超，等.井下巡检无人机系统设计及定位与避障技术 J.机械设计与研究，2021，37（4）：38-42.6 黄郑，王红星，周航，等.基于混合算法的电力杆塔巡检实时航迹规划 J.中国电力，2021，54（11）：214-220.7 朱程雯，黄晓明，龚庆武，等.基于ACO的无人机巡线路径规划研究 J.电网与清洁能源，2021，37（3）：71-77.8 陈麒杰，晋玉强，韩露.无人机路径规划算法研究综述J.飞航导弹，2020（5）：54-58.9 张宏宏，甘旭升，毛亿，等.无人机避障算法综述 J.航空兵器，2021，28（5）：53-63.10熊超，解武杰，董文瀚.基于碰撞锥改进人工势场的无人机避障路径规划 J.计算机工程，2018，44（9）：314-320.11 TANG Z L，CHEN B W，LAN R S，et al.Vector fieldguided RRT*based on motion primitives for quadrotorkinodynamic planning J.Journal of Intelligent&RoboticSystems，2020，100（3）：1325-1339.12李克玉，陆永耕，鲍世通，等.基于改进RRT算法的无人机三维避障规划 J.计算机仿真，2021，38（8）：59-63.13黄壹凡，胡立坤，薛文超.基于改进RRT-Connect算法的移动机器人路径规划 J.计算机工程，2021，47（8）：22-28.14 肖支才，尹高扬，闫实.基于循环寻优RRT算法的无人机航迹规划 J.计算机与现代化，2020（2）：16-20.15 YANG L，ZHENG Z，QIN F Y.Homotopy based optimalconfiguration space reduction for anytime robotic motionplanning J.Chinese Journal of Aeronautics，2021，34（1）：364-379.16ALLAIRE F，TARBOUCHI M，LABONTE G，et al.FPGAimplementation of genetic algorithm for UAV real-timepath planningJ.Journal of Intelligent&Robotic Systems，2009，54（1）：495-510.17 刘鑫，杨霄鹏，刘雨帆，等.基于GA-OCPA学习系统的无人机路径规划方法 J.航空学报，2017，38（11）：287-297.18 周毅，李东武，孟浩，等.遗传算法路径规划在无人机电力巡线中的应用 J.自动化技术与应用，2021，40（2）：29-33.19 PHUNG M D，HA Q P，Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization J.Applied Soft Computing，2021，107（2）：1-15.20 SUN P，SHAN R.Predictive control with velocity observerfor cushion robot based on PSO for path planning J.Journalof Systems Science&Complexity，2020，33（4）：988-1011.21 谭建豪，马小萍，李希.无人机3D航迹规划及动态避障算法研究 J.仪器仪表学报，2019，40（12）：224-233.22 梁文勇，吴大伟，谷山强，等.输电线路多旋翼无人机精细化自主巡检航迹优化方法 J.高电压技术，2020，46（9）：3054-3061.23 韩忠华，毕开元，杨丽英，等.室内复杂环境下多旋翼无人机动态路径规划 J.中国惯性技术学报，2019，27（3）：366-372.24王云常，戴朱祥，李涛.基于A星算法与人工势场法的无人机路径规划 J.扬州大学学报（自然科学版），2019，22（3）：36-38.25 姜月秋，李紫嫣，关启学，等.基于改进A*算法的无人机路径规划研究 J.兵器装备工程学报，2020，41（9）：160-164.26张飞，白伟，乔耀华，等.基于改进D*算法的无人机室内路径规划 J.智能系统学报，2019，14（4）：662-669.27王生印，龙腾，王祝，等.基于即时修复式稀疏A*算法的动态航迹规划 J.系统工程与电子技术，2018，40（12）：2714-2721.28任天祥，贺建良，邹杰.基于改进Theta*算法的直升机三维航路规划 J.电光与控制，2022，29（2）：45-48.29牟德君，初鹏祥.基于改进A*算法的仓储环境AGV路径规划 J.自动化与仪表，2022，37（4）：40-45.田小壮，等：时间最优的无人机巡检避障路径规划47