基于多旋翼无人机的输气管道巡检路径规划研究*

刘 凯，秦 锋，徐 浩，袁志祥

(1.安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243032; 2.安徽工业大学 数理科学与工程学院，安徽 马鞍山 243032)

0 引 言

工业输气管道作为输送工业气体的主要途径，在其工作期间由于自然环境或者气体压力等各种因素，会出现管体破损、管道接口脱离而导致气体泄漏事故，极易引发环境污染、大规模火灾、人员集体中毒等重大问题，因此输气管道的安全巡检工作变得尤为重要。传统的管道巡检工作主要是由人工来完成，但是依靠人工无法满足管道巡检的需求，一方面不仅工作量大而且效率较低，另一方面工业输气管道一般处于室外，相对位置较高并且比较密集，工作难度大且危险系数高。随着无人机技术的发展，多旋翼无人机的远程遥控性、高机动性以及空中可达性已经能够弥补常规输气管道巡检方法的不足，使巡检工作变得高效便捷[1]。

多旋翼无人机在实际工程应用中，对于长距离的飞行任务，通常采用全局静态规划生成航迹点来构建一条完整的航迹，当无人机在执行巡检任务过程中遇到障碍物时，以当前位置的上一个航迹点为起点，下一个航迹点为目标点，进行局部航迹重规划来避开威胁[2-3]。对于无人机航迹重规划问题，国内外研究者提出多种解决方案，包括蚁群算法[4]、遗传算法[5]、粒子群算法[6-7]、A-star算法[8-9]、RRT算法[10]等。文献[4]指出蚁群算法易与其他方法相结合、鲁棒性强，但是存在搜索效率低且易于停滞的问题。遗传算法通过模拟自然进化过程搜索最优解，文献[5]指出其搜索性能较好，但是路径规划所需时间较长，难以满足动态复杂环境下算法的实时性。粒子群算法具有显著的特点，处理一些优化问题时能够取得较优结果，但是后期收敛速度慢，容易陷入局部最优解[11]。A-star算法是静态路网中求解最短路径最有效的搜索方法，但是在执行路径规划任务时需要建立数学模型，内存需求较大，算法的实时性较低[12]。RRT算法通过随机采样在空间寻求路径，不需要建立任务空间信息模型，相对于上述算法，具有实时性强和运算速度快的特点，适合在多维动态环境下快速开拓路径[13]。

综合上述算法分析和工业输气管道空间环境的特点，RRT算法更适用于输气管道的巡检工作。尽管RRT算法能够满足复杂环境下的路径规划需求，但是由于其随机采样机制，无法得到较优的结果。近些年来， 国内外学者提出多种改进RRT算法，虽然都能提高RRT算法的性能，但是未能结合空间环境的特点进行研究，缺乏一定的应用性。

根据RRT算法路径规划效率的影响因素和空间环境特点，在随机点采样方式、路径曲折度两方面做出了优化并进行了仿真实验。实验结果表明，改进后的RRT算法在路径规划时间消耗上以及路径代价上都有了比较明显改善。

1 RRT算法

RRT算法是一种以树形结构存储数据的方法，通过不断在空间中随机采样来增加树的节点，当树的节点到达目标点或者在目标点规定的范围内时停止采样，从目标点反向搜索便可得到一条从起点到目标点的完整路径。RRT构建随机树的具体过程如图1所示。

图1 RRT算法

假设图1中Tree表示当前空间S中的随机树，Pstart为无人机的航行起点,Pgoal为目标点，r为目标点一定范围的半径，Lstep为扩展步长。以起点Pstart为树的根节点，开始在空间S中随机选取采样点Prand作为树的扩展方向，Prand∈S。通过遍历随机树总节点数，计算出离采样点Prand最近的节点Pnear。在扩展方向上选取一个距离Pnear为Lstep的Pnew节点，Pnew∈S，将Pnear和Pnew两节点之间进行碰撞检测，若路径上没有障碍物，则保留新的树节点Pnew，否则删除Pnew节点，重新选取扩展方向Prand。直到新产生的节点Pnew在目标点Pgoal范围内且Pnew和Pgoal的连线上没有障碍物或者Pnew=Pgoal时停止生长。从Pgoal反向搜索，形成从起点到目标点的可行路径，则完成RRT算法路径规划。

基于RRT算法路径规划的无人机不光要考虑障碍物因素，还要将周围空间环境特点、无人机自身的约束条件以及RRT算法扩展方式结合起来，通过一些特殊的改进，降低算法本身缺陷的影响后，将优化后的RRT算法引入到特定的环境中去[14]。

2 约束条件

多旋翼无人机路径规划目的是搜索一条从起点到目标点的最优或者近似最优的无障碍物路径[15]，其将要执行的飞行任务必须能够满足约束条件，否则无人机无法执行该任务。

2.1 安全飞行距离

无人机能够拥有一个完美的飞行轨迹，最重要的是拥有较强的避障能力，而无人机与障碍物之间的安全距离则是避障能力的保证。假设A代表无人机，obs代表障碍物，无人机与障碍物的安全距离为D，则安全飞行距离可以如下：

Dis(A,obs)≥D

(1)

2.2 机身尺寸

工业输气管道具有错综复杂、输送距离长的特点，利用无人机巡检时可能需要穿越局限性较大的区域，此时无人机的尺寸将会是影响路径规划的重要因素。图2代表水平方向输气管道与桥梁的YOZ截面图，管道和桥梁之间构成一个限制空间，假设H为限制空间的高，W为限制空间的宽，图3中T为无人机的高，L为无人机对角线最大的宽度。结合安全飞行距离，则无人机的机身尺寸约束可以表示为

图2 桥梁与管道

图3 无人机

H=Z2-Z1

T≤H-2D

(2)

W=Y2-Y1

L≤W-2D

(3)

当条件满足式(2)、式(3)则表示无人机可以通过，否则将限制空间视为障碍物。

2.3 飞行范围

多旋翼无人机在执行管道巡检任务时，由于任务的特殊性，距离管道的位置必须控制在一定的范围内，距离较远会导致巡检结果出现误差，距离较近会与管道碰撞发生安全事故。图4代表水平方向的管道YOZ截面图，图5代表垂直方向的管道XOY截面图，则飞行范围如下：

图4 水平方向

图5 垂直方向

Z1≤HA≤Z2

Y1≤WA≤Y2

(4)

(5)

3 三维航迹规划

3.1 目标偏向采样策略

传统RRT算法通过不断地在空间中选取随机点Prand来达到扩展随机树的目的，并以此找到一条从起点Pstart到目标点Pgoal的可行路径。虽然这种扩展方式能够充分探索空间，保证了算法的成功性，但是由于算法的随机性较高，导致生成的路径较曲折，并且产生许多冗余节点，在一定程度上会增加算法的运算量，降低算法的实时性。

针对算法的随机采样机制，引入了目标偏向采样策略[13,16]，设定一个固定值α(0≤α≤1)，算法通过函数随机产生一个θ(0<θ<1)。当0<θ<α时，随机点Prand为空间的任意一点，当α≤θ<1时，随机点Prand=Pgoal，朝着目标点方向扩展随机树。若遇到障碍物，则将固定值α设为1，提高避开障碍物的概率，当在α=1下产生一个新的树节点Pnew时，重新将固定值设定为原来的α，重复上述操作。这种优化思想使传统RRT算法在工业输气管道的场景中更加具有目标性，降低算法的运算时间，提高算法的实时性和收敛速度，也可降低随机树的节点数。

3.2 随机点选取范围

对于输气管道巡检任务，为了保证巡检结果的正确率，无人机的飞行路径在不碰撞障碍物的前提下，必须尽可能贴近管道，则随机点的取值必然有一个范围，如式(6)、式(7)所示。假设随机点Prand在三维空间中坐标为(xrand,yrand,zrand),当管道处于水平方向时，则根据飞行范围约束可知：

Prand=(xrand,WA,HA)

(6)

当管道处于垂直方向时，则根据飞行范围约束可知：

Prand=(WA,HA,zrand)

(7)

3.3 节点扩展方式

随机树Tree的扩展方式是从总节点数中找出距离随机点Prand最近的Pnear节点，再以扩展步长Lstep在Prand方向上生成一个新的节点Pnew，最近点的计算公式和新节点坐标的计算公式如式(8)、式(9)所示：

Dis(Pnear,Prand)≤Dis(Pi,Prand)

(8)

(9)

其中，Pi表示Tree的第i个树节点，可知随机树Tree={Pi|i=1,2,3,…,M}，M为总节点数，Lstep为扩展步长，Dis(Prand,Pnear)为Prand和Pnear的欧氏距离。若节点Pnew满足约束条件并且Pnear和Pnew连线上没有障碍物，则将节点Pnew添加到随机树Tree中。

3.4 路径优化

无人机的飞行轨迹无论是基于全局静态规划还是局部重规划，都是通过航迹点构成的，因此真正规划的是这些航迹点[17]。对于传统RRT算法，虽然在其随机点选取上引入了目标偏向采样策略，但是最后生成的路径从无人机飞行效率方面考虑，仍然存在节点多、曲折度大的问题。

文献[18]中提出了一种带路径修正的启发式RRT，由终节点开始，通过逐步迭代的方式对启发式RRT生成的路径进行优化，更新各节点的父节点，直到父节点无法迭代时结束[18]。受到文献[18]的启发，针对工业输气管道巡检工作的特点，提出一种迭代试探的优化方法，主要思想是通过对路径裁剪和平滑处理，降低飞行路径代价，提高飞行效率。

假设图6中有4个连续的航迹点，按顺序分别为P1、P2、P3、P4,其中Bn为△P1P2P3底边P1P3的中点，P2Bn为△P1P2P3的中线，Bj为中线P2Bn上的点，B1=P2。路径优化步骤如下：

图6 路径优化

Step1:首先以P1为起点与P2、P3组成△P1P2P3，在其中线P2Bn上取n个均匀点，n的取值与步长Lstep的大小有关，两者为正比关系。

Step2:选取均匀点中的任意点Bj依次分别与P1、P3连接，其中j的取值顺序为{n,n-1,n-2,…,1}。

Step3:对连接线P1Bj和BjP3分别进行碰撞检测和约束条件检查，若有任何一条线不满足条件，则j-1，直到第一次两条线同时满足条件时结束，此时j的取值可分为：

(1)当j=n时，删除P2，航迹点顺序更新为P1、P3、P4，起点P1不变，与P3、P4组成△P1P3P4，进行下一段的优化操作。

(2)当j≠n时，则将P2替换成Bj，航迹点顺序更新为P1、Bj、P3、P4,接着以Bj为起点与P3、P4组成△BjP3P4，进行下一段的优化操作。

在上述步骤中，步骤1、步骤2的作用是建立优化模型，步骤3主要是对路径的裁剪和平滑处理，当裁剪条件不充分时，通过角度的变化近似达到路径平滑的效果。从路径的第一个节点开始，不断地重复执行上述操作，删除多余路径，增加拐角度数，直到路径的终点，则优化处理完成。

4 仿真实验

4.1 实验环境搭建

仿真实验环境：操作系统Windows 10，处理器AMD Ryzen 3 1200，主频3.10 GHz，内存8 GB，编译工具Matlab R2015b。

为了让实验结果更准确，基于工业输气管道环境特点进行地图建模，如图7、图8所示。

在图7中，圆柱体表示水平方向的工业输气管道，obs1和obs3表示固定障碍物，obs2表示突发威胁，bridge代表需要经过的桥梁，start和goal分别为起点和目标点，同时也是两个相邻的航迹点，此时该空间S={(x,y,z)│0≤x≤300,-10≤y≤160,-10≤z≤80}，起点和目标点的坐标分别为(10,80,13)和(290,80,13)。

图7 水平地图模型

在图8中，圆柱体表示垂直方向的工业输气管道，obs表示突发威胁，start和goal分别起点和目标点，同时也是两个相邻的航迹点，此时空间S={(x,y,z)│0≤x≤250,-10≤y≤160,-10≤z≤160},起点和目标点的坐标分别为(105,80,13)和(105,80,160)。

图8 垂直地图模型

4.2 实验对比与分析

为了验证改进RRT算法的性能，按照表1中的参数设置与传统RRT算法、带路径修正的启发式RRT算法[18]分别在图7、图8所示的地图模型中进行了仿真实验，其中图7分为桥梁可通过和不可通过两种实验场景。

表1 参数设置

在图9—图11中，各分图分别为传统RRT算法、启发式RRT算法和改进RRT算法路径规划结果图，表2—表4是路径规划500次后得到的规划时间、路径节点数和路径长度的平均值和方差，其中表4中为了更好地展示改进RRT和启发式RRT规划时间的方差，将值扩大了1 000倍。

表2 桥梁可通过数据

表3 桥梁不可通过数据

表4 垂直管道数据

(a)传统RRT算法

(a)传统RRT算法

(a)传统RRT算法

如图9—图11所示，虽然3种算法都能找到一条从起点到达目标点的无障碍路径，但是传统RRT算法的路径曲折度和长度都要远远的大于启发式RRT算法和改进RRT算法，并且启发式RRT算法和改进RRT算法相比较，启发式RRT算法的路径存在局部曲折度高的现象。

再结合表2—表4中的实验数据可知，改进RRT算法和启发式RRT算法在时间消耗、节点数和路径长度上的平均值和方差都要远远小于传统RRT算法；改进RRT算法和启发式RRT算法相比，时间消耗、路径长度平均值和方差在总体上前者要小于后者，但是在表3中路径长度的方差前者相对较大，并且在节点数上平均值和方差前者也要大于后者。

构成这种数据现象的原因一方面是改进RRT算法和启发式RRT算法针对传统RRT算法的不足都做出了改进，前者以一定的概率将目标点goal选为采样点，引导随机树向目标点goal方向扩展，同时在遇到障碍物时修改α的值，提高了算法搜索能力，可以快速地找到目标点goal；后者利用结合目标信息的启发式方法，通过在候选节点中寻找距离目标点goal最近的节点作为随机树的采样点，虽然能够避免算法随机性大的问题，但是在候选节点选取上花费了大量的时间且也有一定的随机性。另一方面，改进RRT算法和启发式RRT算法都加入了路径优化处理，前者通过裁剪和增大角度的方式来优化路径，相比较于后者利用更新父节点的方式优化路径，通过局部角度的变化可以更好地绕开障碍物，虽然节点数较多且受障碍物的大小影响较大，但是路径长度短而平滑。

综上可得，在非特殊空间环境中，改进RRT算法和传统RRT算法及带路径修正的启发式RRT算法相比，能够快速地规划出一条路径短且平滑的路径。

5 结束语

为了多旋翼无人机在执行工业输气管道巡检任务时，能够快速地规划出一条较优的避障路径，针对传统RRT算法存在的问题，提出一种结合了目标偏向采样策略和路径优化的改进RRT算法，并在不同的管道地图模型中和传统RRT算法、带路径修正的启发式RRT算法进行了仿真实验对比。实验结果表明：改进后的算法既降低了传统RRT算法随机性，又保留了算法的搜索能力，加快了算法的收敛速度；同时优化了路径，使得路径更短且平滑，能够满足工业输气管道巡检工作的需求。