史红玉, 刘淑芬

(1. 河南理工大学 计算机科学与技术学院, 河南 焦作 454150； 2. 吉林大学 计算机科学与技术学院, 长春 130012)

无人机的航路规划是指在最低油耗、最小威胁和最短距离等约束条件下, 对无人机在起点与终点间的路径进行的优化设计. 考虑到一般无人机的巡航高度, 其无法利用地形躲避威胁, 所以航路规划可简化为一个二维模型问题, 只考虑其水平航迹.

Voronoi图作为一种基本的几何结构, 目前已被广泛应用于无人机航路规划中[1]. 根据威胁区域分布的情形生成由初始可选路径集构成的Voronoi图, Voronoi边是离散威胁源的中垂线, 能使无人机在飞行过程中有效降低威胁代价. 目前, 基于Voronoi图规划航路的方法已有许多, 如赵文婷等[2]根据威胁源基于Voronoi图建模, 计算航路代价, 并针对算法中存在的优缺点, 提出了对算法的改进； 赵艳丽等[3]首先基于Voronoi图建模, 然后获得初始规划解集, 最后通过引入Cauchy变异随机数和扰动对量子粒子群(QPSO)算法进行改进, 确定了最终航路规划的改进算法; 刘平等[4]首先由Voronoi图生成了初始航路, 然后在各种约束条件下赋予各边相应的权值, 最后应用离散型粒子群算法搜索出满意的规划解； 刘森琪等[5]根据威胁源生成Voronoi图, 计算航路代价, 采用改进的蚁群算法计算最优航路； Asano等[6]通过给定一组线段, 在线段中点视角的大小确定属于线段的Voronoi区域, 提出一种寻找最大视角的有效算法; Bhattacharya等[7]基于Voronoi图算法, 在简单分离的情形下计算起点与目标节点之间的距离. 这些算法虽然都能实现无人机的航路规划, 但仍存在收敛速度慢、易陷入局部优化等问题[8-9]. 无人机在战场上对环境的预先设想不一定与实际环境一致, 因此为实现航路规划的准确快速, 需要初始路径有一个更精确合理的优化. 本文在得到初始路径的基础上, 针对传统算法的不足, 提出一种新的快速优化算法, 并通过仿真实验验证了该算法的可行性.

1 基于Voronoi图的威胁区域建模

Voronoi图是在其组成点集中连接两个邻点直线的垂直平分线构成的一组连续多边形, 它是计算几何的重要组成部分, 广泛应用于与区域划分相关的领域, 其中的最近点、n点的凸包和最小树问题均可由Voronoi图解决[10].

1.1 Voronoi图的定义与性质

定义1[11]在二维空间2上, 有n个离散的生成元p={p1,p2,…,pn}, 其中任意两个生成元互不重叠,p对应的Voronoi图是平面的一个子区域划分, 整个平面S被划分为n个单元,Vs={Vp1,Vp2,…,Vpn}. 对于生成元pi的Voronoi区域, 有

Vpi={q∈2|d(pi,q)

(1)

其中d(q,pi)和d(pj,q)分别为q到pi和pj的距离.

性质1对于Voronoi多边形中的点q, 若q在pi所在的多边形中, 用d(q,pi)表示两点间的直线距离, 则有d(pi,q)

性质2Voronoi图中任意n个基点(n>3)的平面, 平面顶点数不超过2n-5, 且边的数目不超过3n-6.

性质3Voronoi图在增减生成元时, 通过局域动态特性只影响相邻的空间区域, 不影响整个空间的划分.

由Voronoi图的定义和性质可知, Voronoi图各边上的点到相对应的两个点距离相等, 即Voronoi边上的点是到威胁点最远的点, 无人机沿Voronoi边飞行可获得相对的安全保障.

1.2 Voronoi图算法的主要思想

基于Voronoi图的航路规划算法思想： 首先确定所有威胁源, 将该威胁源等价为点, 作为Voronoi图的点集, 将威胁源范围的大小作为Voronoi图相邻区域的“距离”度量长度, 然后生成Voronoi图, 图上各条边在相应的领域内与威胁源“距离”越大, 则受到的威胁相应越小. Voronoi图中线段与线段相交的点构成了无人机飞行时的航迹节点, 且可以由威胁源的强度大小和Voronoi图各边的长短计算出各边相应的权值. 其次, 利用最短路径搜索算法[12]得到初始的最优路径, 该初始路径根据威胁代价有效避开了威胁值较大的区域, 同时也尽可能以较短的路径抵达目标点. 最后利用本文提出的优化初始航路算法, 求得最终的航路图.

1.3 Voronoi图建模

在无人机执行任务时, 经常会在飞行环境中遇到一些包括地形威胁、雷达探测威胁等情形, 针对上述威胁信息, 本文基于威胁作用半径, 以威胁场空间形状的威胁信息量化处理方法建模. 根据地貌特征, 将绝对高度在500 m以上的地形概括为高山和陡坡. 地形威胁主要指地面上的山峰或一些较高的物体, 模拟公式为

(2)

其中： Temp(x,y)为地图中该点的高度值;k为威胁区域的威胁程度;x,y为坐标点; VarX,VarY为方差, 方差数越小, 表示沿对应轴方向的地形越陡峭. 将威胁元素山峰定高在H的二维平面时, 威胁模型可表示为

{(x,y)}={(x,y)|(x-ox)2+(y-oy)2≤max{a,b}2},

(3)

其中:a,b分别为地形威胁模型椭圆横切面的长、短轴长； max{a,b}表示a,b中最大值; 点o为地平面横切面的中心点. 该区域定义为无人机禁飞区, 无人机在该区域内的损坏概率为1, 存活率为0.

在无人机航路研究中, 雷达探测威胁也是构成威胁点的一个主要因素, 雷达方程可表示为

p=K/R4,

(4)

其中：p是距雷达接收机R处收到的回波信号功率, 表示雷达的威胁强度;K表示对应于具体雷达的常数. 飞行器对目标的距离R是影响p的重要因素,p与距离R的四次方成反比,R表示为

(5)

其中(x1,y1)与(x2,y2)分别为无人机的坐标和雷达位置的坐标. 第i个雷达对无人机的威胁程度表示为

(6)

图1 威胁分布的Voronoi图Fig.1 Voronoi diagram of threat distribution

其中:j表示由n个航迹点组成的航路上的一点;pj表示该点的回波强度. 假设无人机在飞行过程中遇到n个雷达, 则无人机受到的雷达威胁Wz可表示为Wz=f(W1,W2,…,Wn).

无人机在高空平飞时, 其航路规划区域可认为是一个二维平面. 在平面内的威胁分布主要是雷达等设备或很高的山峰, 可以把这些雷达或山峰在地图上等效为点, 然后以这些点作为基点集, 构造出由威胁点分布的Voronoi图, 最后可在构造好的Voronoi图中进行航路规划. 图1为根据威胁模型建立的Voronoi图, 图中的圆点表示威胁源.

2 基于Voronoi图的航路代价计算

无人机航路规划是在满足约束条件的基础上规划出一条由起点到目标点的飞行轨迹. 它是一个约束条件较复杂的多目标规划问题[13], 其约束条件一般包括无人机的安全性能和燃油性能[14], 因此, 本文考虑的航路代价包括与距离有关的威胁代价和燃油代价.

2.1 威胁代价

图2 威胁代价的计算Fig.2 Calculation of threat cost

雷达作为威胁源构成了与其相接的Voronoi边的威胁元素, 假设无人机具有的雷达反射截面均相同, 则可用Voronoi图每条边的积分表示该边的雷达威胁代价, 如图2所示. 无人机反射雷达回波的强度与其到雷达距离的四次方成反比[15], 则Voronoi图中边的雷达威胁代价为

(7)

其中,r1,r2为加权系数, 分别表示威胁和距离在弧的权值中所占的比.

将线上的积分转化为线上5个点的积分, 本文采用十等分法, 用ftemp(Vi,pj)表示经过十等分后威胁源对Voronoi边的威胁权值, 则

(8)

2.2 燃油代价

假设无人机在飞行过程中速度恒定, 则其在飞行过程中所消耗的燃油与飞行航路的长度成正比, 燃油代价为

ffurl=kli,

(9)

其中k为比例系数.

2.3 总代价

由于无人机航行过程中的代价主要包括威胁代价fweight(Vi)和燃油代价ffurl, 所以无人机的航路总代价可表示为

fzong=kfweight(Vi)+(1-k)ffurl,

(10)

其中,k为安全性能与燃油性能的系数, 若要求无人机安全性能最大, 则k=0； 若要求航路最短, 则k=1.

3 对初始航路的优化

3.1 B样条插值

由Voronoi图经过最短路径搜索算法计算后, 可得到一条初始的优化路径, 由于未考虑到无人机的运动约束, 所以该路径必须进一步优化路径中包含的一些不可飞的尖锐转弯角. 一般情形下, 使用B样条插值[16-17]、三次样条插值法或K-path法解决航路中存在的尖角问题. 下面以B样条插值法为例进行说明.

B样条插值(简称B-Spline插值)属于逼近样条类, 与控制多边形的外形更接近, 而且还具有局部修改能力, 应用广泛.

定义2由(m+n+1)个平面或Pi(i=0,1,2,…,m+n)个空间顶点组成的曲线, 称为n次参数曲线段：

(11)

其中：Pk,n(t)表示第k段n次B样条曲线段(k=0,1,2,…,m), 曲线段全体构成n次B样条曲线, 由点Pi(i=0,1,2,…,m+n)构成的多边形表示B样条曲线的特征多边形;Gi,n(t)表示基函数, 可定义为

(12)

在无人机给定的航路离散点中, 选取(n+1)个控制点Pj(j=0,1,2,…,n), 则K阶B样条曲线方程为

(13)

其中, 参数u的范围由B样条其他参数的选取确定.

B样条插值函数一般用于消除路段间的转折, 使整条航路趋于平滑, 满足了无人机的可飞条件, 但仅解决了路径的尖角问题, 使初始航路的路线变得圆润平滑适合飞行. 无人机在飞行过程中对时间节点的要求较严格, 期望优化后的航程基本不变, 在遇到紧急任务或燃料告急时, 则希望航程最短, 因此, 在出现上述情形时就需要采取其他规划方式实现规划要求. 本文提出一种新的快速对初始航路优化的算法, 不仅能解决航路不能飞的问题, 同时也对威胁代价和燃油代价进行进一步的优化.

3.2 优化初始航路改进算法

本文提出的优化初始航路改进算法描述如下.

1) 初始化. 首先备份原始路径中的节点坐标, 确定当前的迭代次数和迭代次数最大值.

2) 根据初始的航路路线, 首先从起点开始确定两条线段, 即确定3个顺序排列的节点坐标， 如图3所示.

3) 图3中point2,point1,point3分别对应Voronoi图中节点坐标Pi-1,Pi,Pi+1, 利用夹角公式计算两条线段构成的夹角, 如果该夹角大于120°, 则符合航行要求不做处理; 如果该夹角小于120°, 则进行以下处理：

① 如图4所示, 分别在两条线段上用linspace函数在对应的线段上选5个点, 以一边为例.

② 由中间节点到两边线段最近的间隔点pointA和pointB再次用linspace函数将对应的线段划分成中间节点到该间隔点线段长度10倍的小段, 即将每条线段都以长度0.1分隔开.

③ 由interp2函数可分别求得由中间节点到两端最近间隔点的权重值以及两个间隔点间的权重值, 如图5所示. LengthWeightA=interp2(x,y,Plane,SegXA,SegYA,‘linear’) 存放point1到pointA上由②中划分后每个间隔点的油耗值和威胁值, 其中:x,y表示坐标点； Plane表示初始化带有Voronoi图上每点油耗值和威胁程度值的矩阵； SegXA和SegYA表示插值后的坐标点. point1到pointA线段的权重值为

WeightA=sum(LengthWeightA).

同理可求出另外两条边的权重值.

图5 权重比较示意图Fig.5 Schematic diagram of weight comparison

④ 将①中一条线段上的间隔点遍历另一条线段上的所有间隔点, 根据③可求出对应的权重值. DifWeighti,j=WeightAi,j+WeightBi,j-WeightABi,j(i,j∈[2,5])表示三边权重值的比较: 其中i,j分别表示两条线段上第i个和第j个间隔点.

由max(DifWeight((:)))获取最优的节点, 即在该两点时油耗和威胁值均最小. 假设图5两边大于第三边的权值是在所有间隔点中最大的, 则pointA,pointB即为本文新获取的节点, 原来的节点为point2,point1,point3, 现在新路径节点为point2,pointA,pointB.

4) 根据对权重值的比较, 找到最优线路的节点坐标, 获取新的两点坐标若是初始节点中的坐标则不做改变, 如果不是则替换相应的初始节点坐标.

5) 更新完节点后, 回到初始化, 对新得到的路径节点进行再次判断是否符合无人机的飞行条件, 然后再次进行优化、更新、迭代, 从而得到最终的符合飞行要求的新路径节点, 生成最后的路径图.

本文得出的最终路径不仅解决了航路中存在的尖角不可飞问题, 减少了路程时间, 而且航行中的油耗和威胁值也是最优的.

4 仿真实验

为了验证本文提出的对初始路径优化算法的有效性, 对图1所示的具有40个威胁源的区域进行航路规划. 实验环境为: Inter CPU 2.20 GHz, 4.00 GB内存, 操作系统为Win7专业版, 仿真环境采用MATLAB R2014a实现.

假设飞机在飞行中一直匀速行驶, 飞行高度固定. 图1中的点表示航路中存在的雷达、山峰等构成的威胁源, 规划空间中共有40个威胁. 航路的起始点坐标为(-30,-40), 目标点坐标为(18,30). 下面分3种情形讨论.

情形1) 图6和图7分别为不考虑燃油代价, 只考虑航行中威胁代价时生成的初始航路和优化后的航路. 由图6和图7可见, 无人机在规划路线时基本避开了威胁区, 威胁代价最小, 选择了一条路径最远的航路, 此时燃油代价最大. 航路的数据信息列于表1. 由表1可见, 当不考虑燃油只考虑威胁代价的权值时, 新规划的航路比初始航路值在航程、时间等方面均有明显改善, 证明了本文提出优化算法的正确性.

图6 情形1)的初始航路Fig.6 Initial route chart of case 1)

图7 情形1)优化后的航路Fig.7 Optimized route chart of case 1)

无人机航路点数/个航路航程/km生存概率航路时间/s迭代次数航路代价原航路18162.12117.882001 731.66新航路25131.41113.252001 405.56

情形2) 图8和图9分别为考虑50%权重燃油代价和50%权重威胁代价后生成的初始航路和优化后航路. 由图8和图9可见, 与图6和图7相比, 此时无人机规划的航路移动到了威胁点较集中的区域, 威胁代价增加, 燃油代价相对减少. 航路的数据信息列于表2. 由表2可见, 当将燃油和威胁代价各考虑50%权重时, 新优化的航路较初始航路, 多项数据都得以更新, 航路具有可行性, 航路所用算法能规划出一条最优路线.

图8 情形2)的初始航路Fig.8 Initial route chart of case 2)

图9 情形2)优化后的航路Fig.9 Optimized route chart of case 2)

无人机航路点数/个航路航程/km生存概率航路时间/s迭代次数航路代价原航路17148.72115.732001 512.43新航路25125.75113.162001 277.32

情形3) 图10和图11分别为只考虑了燃油代价, 未考虑威胁代价生成的初始航路和优化后航路. 由图10和图11可见, 航路将进一步移动到威胁更集中的区域, 此时的燃油代价最小, 但威胁代价最大. 航路的数据信息统计列于表3. 由表3可见, 该算法能快速为无人机规划出新的满足各项约束的航路, 在威胁区域密度相对小的情形下, 航路避开了威胁区, 减少了不必要的代价.

图10 情形3)的初始航路Fig.10 Initial route chart of case 3)

图11 情形3)优化后的航路Fig.11 Optimized route chart of case 3)

无人机航路点数/个航路航程/km生存概率航路时间/s迭代次数航路代价原航路16117.44112.432001 279.63新航路893.67110.01200956.78

以上生成的3条最优航路显示了无人机航路由威胁点较少的区域移动到威胁点较集中区域的过程, 新航路对比原航路不仅缩短了航行路程, 同时也减少了航路时间和航路代价. 无人机航路规划路线合理, 航路规划结果显示了权值变换对该结果的影响. 实验结果表明, 本文提出的无人机航路规划算法计算原理简单、易于实现, 生成的最优航路既可以保证整个飞行任务的全局最优特性, 也可以满足飞行任务的需求.

综上所述, 本文根据威胁源的分布, 基于Voronoi图建模生成了初始的航路规划图, 并运用新的优化初始航路算法得到了最终航路. 仿真实验验证了由该算法在Voronoi图中进行航路规划的可行性和有效性. 实验结果表明, 该航路图保证了无人机能在航行时间和花费代价更少的情形下成功回避航路中的各种威胁, 并顺利到达目标点.