车机协同多区域覆盖侦察路径规划方法

夏阳升 石建迈 陈超 黄金才 程光权

在现代战争中,无人驾驶飞机具有成本低、生存能力强、无人员损失风险、机动性好等优点,被广泛用于执行枯燥、恶劣、危险的作战任务,已经成为世界各国战场侦察的重要工具[1],并在第四次中东战争、海湾战争、科索沃战争和后来的伊拉克战争中发挥了重要的作用[2].

无人机战场侦察是利用无人机获取战场信息的活动,其中路径规划是无人机执行侦察任务的关键支撑技术,是无人机侦察任务规划领域的重要研究课题[3].当前无人机侦察路径规划研究主要针对地面固定目标的侦察任务进行路径优化[4].此外,也有一些考虑敌方雷达探测和地面障碍物的规避路径[5],以及目标的侦察时间约束[6]等贴近战场实际情况的研究,研究领域也从单无人机向多无人机协同方向发展[7].在实际战场侦察中,除了固定点目标,有些时候还需要获取某些特定区域内的所有详细信息,此时一般应用小型无人机对整个侦察目标区域进行覆盖扫描.小型无人机具有成本低、隐蔽性好、可以低空高精度扫描等优点,在军事和民用领域的区域覆盖扫描中有着广泛的应用[8].龙国强等[9]提出集中式预先规划与分布式局部在线再规划相结合的方法,解决多无人机协同区域覆盖侦察问题.吴青坡等[10]研究了如何提高对复杂区域的侦察效率,高春庆等[11]首先将含障碍物的区域单元格化,然后为每一架无人机划分子覆盖区域,最后使用最小生成树的方法为每个子区域规划侦察路径.在民用方面,如评估灾区的破坏情况[12],观察农业生产中的作物生长情况[13]和地形图的测绘[14]等,都需要优化无人机对目标区域的扫描路径.

当前无人机区域覆盖研究中,大多研究无人机如何对一个区域进行覆盖,通过规划无人机飞行路径,以尽可能低的成本完成整个区域的覆盖扫描[15].很多时候,需要对多个战场区域进行扫描侦察,当多个区域分散在大范围战场的不同位置时,小型无人机续航能力低成为其完成任务的关键制约因素.

为了扩大小型无人机执行侦察任务的范围以完成多区域覆盖侦察任务,引入汽车作为无人机的移动平台,携带无人机在战场上进行大范围机动,构建车机协同战场侦察系统.汽车作为无人机的指控与保障平台,携带无人机从一个侦察区域机动到另一个侦察区域,并在机动过程中为无人机充电或更换电池.当汽车携带无人机达到某个目标侦察区域附近时,无人机从汽车起飞,飞到侦察区域上空完成该区域的覆盖侦察后返回汽车.汽车和无人机的结合可以有效扩大小型无人机的任务范围,提高战场多区域侦察的效率.Grocholsky 等[16]为汽车和无人机协作进行空中和地面监视构建了模型和算法框架.罗志浩、刘忠等[17]建立了一个由地面车辆和无人机协作对多个点目标执行情报,监视和侦察(ISR)任务的数学模型,并通过试验表明车机协同模式可以显著提高ISR 任务的完成效率.在民用领域,刘瑶等[18]使用模拟退火算法求解车载无人机协同配送的双层路径规划问题.Tokekar 等人[19]结合了地面车辆和无人机的优势,设计了一个用于在农场的特定位置收集氮含量的系统,可以帮助农民有效减少肥料的使用.汽车和小型无人机协同系统在执行多种军事和民用领域的任务中具有显著优势.

当前车机协同路径规划的研究主要关注无人机对点目标的访问顺序和飞行路径,还没有多个区域覆盖侦察路径规划的相关研究.车机协同多区域覆盖侦察的路径规划面临更多新的研究挑战.问题中存在两层路径,其中空中无人机飞行路径与汽车在地面路网的行驶路径在不同的节点上相互连接.由于车辆和无人机之间在速度、续航时间和行驶方式方面的差异,在规划过程中需要考虑两种路径相互之间的影响.这种双层路径的交互作用使问题的解空间比传统路径问题更为复杂,求解难度更大.成整个侦察任务,但无人机的续航能力是有限的,能够完成一个区域的覆盖侦察,在对不同区域侦察时,需要进行充电或更换电池.车机协同多区域覆盖侦察过程中,一辆汽车搭载一架小型无人机从基地出发,当行驶到需要侦察区域附近时,放飞无人机,由无人机飞到侦察区域上空进行全覆盖扫描并收集信息;无人机完成目标区域的覆盖扫描后,返回汽车,由汽车携带无人机行驶到下一个侦察区域,并在行驶过程中完成无人机的充电或更换电池工作;如此循环,汽车携带无人机在战场上机动,完成所有目标区域的侦察后,返回基地.汽车只能在侦察区域附近的一些特定点(称为临时停点)放飞和回收无人机,放飞无人机后,汽车可以等在原地回收无人机,也可以行驶到其他临时停点回收无人机.

图1 车机协同多区域覆盖侦察示例Fig.1 An example of multi-area coverage reconnaissancewith cooperated ground vehicle and drone

1 数学模型

1.1 问题描述

在车机协同完成多个区域的覆盖侦察任务中,道路网络和侦察区域的位置、形状等信息都是已知的.汽车作为小型无人机的移动搭载平台,在行驶过程中可以为无人机充电和更换电池,同时也是无人机的指控中心.汽车的续航能力足以携带无人机完

图1 给出了车机协同对3 个区域进行侦察的示例.可以看出车机协同侦察过程中,汽车只能在地面路网上行驶,其访问所有侦察区域的路径规划属于典型的旅行商问题;无人机从汽车上出发,飞到侦察区域上空,对侦察区域进行连续覆盖扫描,属于典型的无人机航迹规划问题.同时汽车的路径需要和无人机的路径密切配合,在满足无人机的续航能力约束条件下,快速完成所有区域的侦察.如何优化车辆和无人机的路径,使得在不超出无人机最大续航能力的前提下以最短的时间完成对所有区域的覆盖,比单纯的求解旅行商问题和无人机航迹规划问题更加复杂,需要考虑两类路径的交互影响.

1.2 问题建模

为了便于模型描述,表1 给出了建模过程中应用的所有符号及其含义.

数学规划模型如下:

表1 符号及其含义Table 1 Notations and their meaning

目标函数式(1)最小化完成所有区域侦察的总时间,其中第1 部分是汽车携带无人机在所有覆盖区域和基站之间转移的总行驶时间,第2 部分是车载无人机在所有侦察区域进行覆盖扫描的飞行总时间.为了减少第1 部分的时间,在不同侦察区域周围选择停点的标准之一是选择彼此之间Floyd 距离较小的停点.为了减少第2 部分的时间,一方面,在同一个区域内选取彼此之间Floyd 距离小的停点;另一方面,选择合适的临时停点以使无人机的总飞行距离更短.

约束条件式(2)确保车载无人机必须从基站出发,完成所有覆盖任务之后返回同一个基站.约束条件式(3)确保每个临时停点的出度等于入度,从而确保车辆行驶路线的连通性.约束条件式(4)确保车辆进入每个侦察区域一次并离开该区域一次,即每个侦察区域只能访问一次.约束条件式(5)确保无人机只能在车辆所访问的临时停点起飞,而约束条件式(6)确保无人机只能在车辆所访问的临时停点降落.约束条件式(7)确保无人机只能在每个侦察区域起飞和降落一次.约束条件式(8)确保无人机在每个侦察区域飞行路径的连通性,并且与约束条件式(7)一起确保在每个侦察区域仅进行一次全覆盖扫描.约束条件式(9)确保无人机在扫描每个侦察区域时的飞行时间都不会超过其最大续航时间.约束条件式(10)和式(11)定义0-1 变量的取值范围.

2 三阶段启发式算法设计

这里提出一种三阶段启发式算法来快速求解车机协同多区域覆盖侦察路径规划问题.第1 阶段是分析侦察区域的几何特征,计算无人机的覆盖扫描路径;第2 阶段是在无人机候选扫描路径的基础上,借鉴节约算法思想,规划汽车的行驶路径以及无人机在每个区域的放飞与回收点;第3 阶段,采用局部搜索算法改进第2 阶段构造的可行解,得到问题的最优解或近似最优解.

作为三阶段启发式算法的基础输入,需要首先计算出任意两点之间的Floyd 距离.令表示从点i到点j的Floyd 距离,由Floyd 算法计算得出.Floyd算法(也称为插值方法)是一种使用动态编程的思想在给定加权图中找到多个点之间最短路径的算法,与Dijkstra 的算法相似.Floyd 算法的主要过程如下.

算法1:Floyd算法Input:The coordinates of N0 and N and Ps Output:Floyd distance matrix dis 1Compute adjacency matrix dis[w][w],w is the total number of all points 2FOR k=1:w DO 3FOR i=1:w DO 4FOR j=1:w DO 5 IF dis(i,k)+dis(k, j)＜dis(i, j)THEN 6 dis(i, j)=dis(i,k)+dis(k, j)7END IF 8END FOR 9END FOR 10 END FOR 11 RETURN dis

2.1 无人机路径规划算法

当无人机对一个区域进行覆盖扫描侦察时,首先需要分析侦察区域的形状,为无人机选择合适的扫描模式,如割草式扫描或螺旋式扫描;如果选择了割草式扫描,需要进一步检查侦察区域的凹凸性,当该区域为凹多边形时,要将其分解为多个凸多边形子区域;最后,根据无人机的相关性能参数计算覆盖区域的扫描飞行路径.

2.1.1 扫描方式的选取

应用无人机对一个区域进行覆盖扫描时,主要有两种扫描模式,即割草式扫描模式[20]和螺旋式扫描模式[21].如图2 给出了两种扫描模式下无人机的飞行路径.在图2 中,用黑色边框包围的多边形表示侦察任务区域,黄色的圆表示扫描路径的起点和终点,蓝色虚线轨迹表示无人机的飞行路径,箭头表示无人机的飞行方向.两种扫描模式具体定义如下.

螺旋式扫描模式:无人机从侦察区域的中心开始,然后以恒定的螺旋间距向外逐渐扫描,直到覆盖完整个区域.也可从最外开始,螺旋向内扫描.

割草式扫描模式:无人机以平行航迹往复推进的方式从侦察区域边缘开始以等间隔距离扫描,直到覆盖完整个区域.

图2 螺旋式扫描模式和割草式扫描模式Fig.2 Spiral pattern and lawn mowing pattern

当前研究中大部分采用割草式扫描模式[22-23],少数采用螺旋式扫描模式,没有研究多种扫描模式的选择优化.而实际工作中,同一区域采用不同的扫描模式时,扫描路径的总长度可能相差很大.例如,在图2 中,由螺旋式扫描模式生成的飞行路径明显长于使用割草式扫描模式生成的飞行路径.然而,当侦察区域越接近圆形,使用螺旋式扫描比割草式扫描模式效果会越好.因此,可以根据覆盖区域与圆的接近程度选择不同的扫描模式.

多边形的圆度定义如下:

其中,S是侦察区域的面积,L是其周长.如果该区域更接近圆,则其圆度C更接近1.

为了分析对比两种典型扫描模式对不同圆度的多边形区域的扫描效率,表2 给出了几种典型多边形分别采用两种扫描模式时的扫描时间.表2 中所有的多边形的面积相等,取值为84 个平方单位,无人机的扫描宽度设为2 个单位,速度为1 单位/s.从表2 中可以看出,当多边形的圆度较小时,割草式扫描模式的扫描时间明显小于螺旋式扫描模式的扫描时间.随着多边形的圆度逐渐变大,它们之间的差距越来越小.当多边形是正五边形(C= 0.86)时,两种扫描模式的扫描时间基本相同.当多边形的圆度继续增加时,螺旋式扫描模式的时间变得比割草式扫描模式的时间更短.因此,通过试验观测可以总结如下近似规律:当侦察区域的圆度小于0.86 时,割草式扫描模式较优;当圆度大于0.86 时,螺旋式扫描模式较优.

表2 对于典型多边形使用两种扫描模式得到的扫描时间Table 2 Scanning time for typical polygons by the two scanning patterns

2.1.2 凹多边形的判定与分解

当采用螺旋式扫描模式时,多边形的凹凸性对扫描时间的影响很小.然而,当采用割草式扫描模式时,多边形的凹凸性对其影响较大.使用割草式扫描模式生成的扫描路径需要在侦察区域为凸多边形的前提下进行规划的.当侦察区域是凹多边形,必须将凹多边形分解为一系列凸多边形子区域.

1)多边形凹凸性的判定

向量的叉积可以用来判断一个侦察区域的凹凸性.判定原理如下:具有相同转向的顶点是凸点,凸多边形的每个顶点都是凸点;具有不同转弯的顶点是凹点,若多边形中存在一个以上的凹点,则一定是一个凹多边形.假设多边形P具有n个顶点(v1,v2,···,vn),P的凹凸性由P是否具有凹点确定.设vi为P的一个随机顶点,vi-1和vi+1为vi的两个相邻顶点.顶点vi的凹度由向量QQQ的叉积决定.

其中,当P的所有顶点都为凸点时,该多边形是凸多边形,否则P是凹多边形.

2)凹多边形的分解

使用割草式扫描模式生成的扫描路径通常称为Boustrophedon 路径.将一个凹多边形分解为一系列凸多边形子区域,然后为每个凸多边形规划Boustrophedon 路径称为Boustrophedon 分解(BCD)[24].Li等人[25]提出了一种基于梯形分解的精确BCD 方法,算法复杂度为O(n).在文献[26]中,使用凹多边形的凸包将BCD 方法扩展为外部细胞分解方法,有效地减少了分解的凸多边形的数量.本文设计了一种基于梯形分解的BCD 方法.由于沿不同角度分解凹多边形的效果不同,为了减少分解的凸多边形的个数和无人机的转弯次数,沿与凹多边形长轴平行的方向分解凹多边形.

对于凸多边形的每一条边,分别计算不属于该边的其他顶点与这条边的距离.将这些距离的最大值标记为该边的跨度.比较所有边的跨度,最小跨度所对应的边称为该凸多边形的长轴.为了找到凹多边形的长轴,采用凸包生成算法首先生成了一个凹多边形的凸包[27].凸包是包含凹多边形的所有顶点的最简单的凸多边形.该算法总结如下:

①找到所有顶点中的极点并删除所有落在由极点形成的多边形内部的点,将剩余的点划分到4 个区域.

②对于区域1 和2,按其升序对其中的点进行排序,对于区域3 和4,按降序对它们进行排序.

③对于每个区域,找到从一个极点到另一个极点的凸路径.

然后,将凸包的长轴视为凹多边形的长轴.在沿与长轴平行的方向将凹多边形梯形分解为一系列凸多边形之后,通过使用割草式扫描模式为每一个凸多边形生成Boustrophedon 路径.

图3 给出了一个凹多边形的分解示例.图3(a)中用实线包围的图形是要分解的凹多边形,在添加虚线之后,它变成凸多边形,其中蓝色边表示凸多边形的长轴,并且也是凹多边形的长轴.图3(b)表示将凹多边形沿着与其长轴平行的方向进行梯形分解,而图3(c)表示将梯形分解后的一系列凸多边形合并的过程.当两个相邻的凸多边形的一条边彼此重合并且两者长轴彼此平行时,可以将它们合并.该过程可以有效地减少凸多边形的数量,并避免无人机在不同凸多边形之间的不必要转移.图3(d)显示了使用割草式扫描模式产生的Boustrophedon 路径.

图3 凹多边形的BCD 分解和Boustrophedon 路径生成过程Fig.3 BCD decomposition of concave polygon and Boustrophedon path generation process

2.1.3 算法流程

基于无人机扫描模式选择和多边形区域分割方法,设计无人机对侦察区域进行覆盖扫描的飞行路径规划算法,总体流程如算法2所示.首先在给定侦察区域的几何信息、潜在临时停点的位置信息以及无人机飞行速度的条件下,计算侦察区域的周长和面积(第1 行),然后计算侦察区域的圆度(第2 行).如果该区域的圆度大于0.86,则采用螺旋式扫描模式,然后获得扫描路径(第4 行)以及路径的起点和终点(第5 行).扫描路径的长度在第6 行中计算.如果圆度小于0.86,则采用割草式扫描模式.在这种情况下,首先检查该区域的凹凸性(第9 行).如果该区域是凹多边形(第10 行),则使用上节设计的BCD 方法(第11 行)将其分解为一系列凸多边形,然后规划侦察区域的Boustrophedon 路径.沿着平行于长轴的方向开始,有两条扫描路径(第13 行),分别对应两对起点和终点(第14 行).计算两条路径的长度(第15 ～16 行).

算法2:无人机区域扫描路径规划算法Input:The vertexes(v1,v2,···,vn)of area A Output:All scanning paths U and their start and end points(s,e)1Compute L and S 2C ←4*π*S/L2 3IF C ≥0.86THEN 4U ←spiralpattern(A)5Compute the start and end points 6d ←dis(U)7END IF 8ELSE 9Q ←vi-1vi×vivi+1 10IF Q ＜0 THEN 11Decompose A by the BCD method 12END IF 13U ←lawn-movingpattern(A)14Compute two pairs of start and end points(s1,e1;s2,e2)15d1 ←dis(U1)16d2 ←dis(U2)17 END ELSE 18 RETURN U,d,(s,e)

2.2 车辆路径规划算法

车辆路径规划是通过优化汽车访问侦察区域的顺序和选择每个侦察区域附近的临时停点,一方面配合无人机的扫描路径使无人机的飞行时间较短,一方面优化汽车的行驶距离,使得汽车在整个任务过程中的行使时间较短.结合这两个方面,基于节约算法思想,设计了车辆的路径规划算法,如算法3所示.首先,根据全部点的位置信息计算Floyd 距离矩阵dis(第1 行),然后为每个区域选择扫描路径(第2行),得到扫描路径的起点和终点(第3 行).在每个侦察区域附近随机选择两个临时停点,然后计算无人机从一个临时停点起飞到扫描路径起点的距离和从扫描路径终点飞到另一个临时停点的距离,其中Dis是两个距离的和(第4 ～10 行).在每个侦察区域中,找到与最小距离Dis对应的两个临时停点作为该区域选定的停点(第12 行)以形成停点集合goal(第14行),然后计算节约矩阵(第15 ～19 行),并将其降序排列(第20 行).从最大值开始,将对应的两个侦察区域连接起来,直到包括所有的侦察区域,从而得到汽车和无人机路径规划的可行解(第21 行).

算法3:车辆路径规划算法Input: N0,N and NS and the start and end points of all scanning paths Output:Solution s 1Compute the Floyd distance matrix dis 2Routei ←randomselect(areai),i=1,2,3,···,m 3p1i,p2i ∈Routei 4FOR i=1:m DO 5FOR k ∈Ni DO 6FORt ∈Ni DO 7 Dis(i,k,t)←dis(k,p1i)+dis(p2i,t)8END FOR 9END FOR 10 END FOR 11 FOR i=1:m DO 12Find the k, t corresponding to the smallest Dis(i, k, t)to form Choicei 13 END FOR 14 goal ←(Choice1,Choice2,···,Choicem)15 FOR i=1:(m-1)DO 16FOR j=i+1:m DO 17jieyue(i, j)← dis(N0,goal(i,2))+ dis(N0,goal(j,1))-dis(goal(i,2),goal(j,1))18END FOR 19 END FOR 20 W ←descendsort(jieyue)21 Starting from the W(1),the corresponding two area numbers are connected until all areas are included,and s is obtained 22 RETURN s

2.3 局部搜索算法

通过前面两个阶段无人机和车辆路径规划算法可以得到车机协同多区域侦察的较优方案,但很多时候可能还不是问题的最优解,还有改进的空间.因此,进一步设计车辆路径和无人机路径的局部搜索算法来改进解的质量.这里主要采用两类随机算子来进行局部搜索,第1 类是随机交换两个侦察区域的访问顺序,搜索改进汽车行驶距离的可行解;第2类是随机交换汽车在某个侦察区域附近放飞和回收无人机的临时停点,搜索减少无人机飞行距离和(或)汽车行驶距离的可行解.通过随机调用这两类算子搜索不同的可行解,直到连续Nmax 次没有改进时,停止搜索得到最终方案.

3 实验分析

下面通过一个典型算例给出模型和算法的应用示例,并说明车机协同进行多区域侦察的优势.所有计算实验均在华为笔记本电脑上进行,该笔记本电脑使用Core i7 1.8 GHz 四核处理器,16 GB 内存,Windows 10 操作系统,并且应用Matlab R2018a 进行算法编码.

3.1 实验设计

在平面上生成7×7 的道路网络,该道路网络将平面分为49 个正方形网格.将每个网格的边长设为10 个单位,从49 个网格中随机选择20 个网格,在每个选中的网格中生成一个不规则多边形,如图4所示.按从左到右,从下到上的顺序对20 个多边形区域进行编号.在所有多边形的每一条边上生成一个随机的临时停点,以蓝色星号表示,红色正方形表示基站.最后,将道路网络与覆盖区域用线段连接起来.汽车搭载无人机从基站出发对20 个区域进行覆盖侦察,并在完成任务后返回基站.找到汽车和无人机的最佳路线,以完成对所有区域的扫描侦察.

图4 侦察区域和路网分布Fig.4 Reconnaissance area and road network distribution

车辆的平均速度设置为0.5 单位/s,无人机的飞行速度设置为1 单位/s.将无人机的扫描宽度设置为1 个单位,最大续航时间设为140 s.局部搜索算法中Nmax 设置为200.应用式(12)计算20 个侦察区域的圆度,如表3所示.

从表3 可以看出,区域1、3、6、11 的圆度明显大于0.86,因此,采用螺旋式扫描模式,其余区域采用割草式扫描方式.区域2、12、14、16、17、18 是凹多边形,使用先前设计的基于梯形分解的BCD 方法分解它们,然后使用割草式扫描模式为它们规划Boustrophedon 路径.

表3 20 个侦察区域的圆度Table 3 Roundness of 20 reconnaissance areas

3.2 实验分析

如果单纯采用无人机对这些区域进行侦察,考虑到无人机的最大续航时间,以及无人机必须安全返回基地等限制,无人机无法飞到区域14、17、19、20,从而无法对这些区域进行侦察,剩下的区域虽然都在无人机的侦察范围内,但是只有区域1、2、3、5、8、9、11、12 能够在无人机一次飞行过程中侦察完毕,其余区域都需要无人机不断地返回基站进行充电之后,再次前往区域进行侦察才能完成总的任务.因此,对于大范围的多区域侦察问题,单纯的小型无人机很难完成侦察任务.

如果采用车机协同侦察的模式,应用三阶段启发式算法计算得到的可行解如图5所示,其中汽车访问20 个区域的顺序为2-1-3-6-4-7-10-14-20-17-19-13-16-18-15-12-9-5-8-11.无人机扫描路径如图中所示,完成所有区域扫描侦察的总时间为2 379.71 s.三阶段启发式算法求解20 个侦察区域的路径规划方案耗时18′32′′.可以看出,车机协同模式可以高效完成单纯采用无人机无法完成的侦察任务,同时三阶段启发式算法可以有效解决车机协同带来的复杂路径规划问题,满足实际作用应用需求.

图5 汽车和无人机的路径规划方案Fig.5 Path planning solutions for cooperated ground vehicle and drone

4 结论

随着智能化、无人化、自主化战争的快速发展,小型无人机在战场情报侦察中发挥着越来越大的作用.如何充分利用小型无人机在战场侦察中隐蔽性强、成本低、风险小的优势,同时克服其续航能力小的缺点,更好地发挥小型无人机的作战能力,是无人机指控领域的一个重要课题.车机协同是一种可行且高效的应用模式.针对车机协同多区域覆盖侦察的路径规划问题,提出了侦察区域扫描方式判定、无人机扫描路径规划以及汽车路径规划等系列方法,在此基础上,设计了一种三阶段启发式算法,来快速优化汽车和无人机的行驶路径.

车机协同多区域覆盖侦察路径规划属于路径规划领域的一个全新方向,当前的研究还处于起步阶段.通过解决一车一机协同区域覆盖侦察路径规划问题,验证了车机协同的优势.下一步该方向还有很多扩展研究方向,如一车多机、多车多机等更广泛的应用模式.同时,在车机协同规划中考虑敌方威胁规避、无人机随机损失等战场对抗因素的影响,研究更加体现战场不确定性的优化方法,也是车机协同领域具有重要实际价值的研究.