空地异构机器人系统协作巡逻路径规划方法

1 引言

对风险区域开展持续全覆盖巡逻任务是实现有效的治安管理和边防保卫的重要手段.这些巡逻任务都具有巡逻范围广、监视频次高、任务时间长等特点,已很难完全依靠人工完成上述持续巡逻任务.机器人辅助的巡逻形式应运而生.微型无人机运动灵活、监测视角大、不易受遮挡,在发现和跟踪目标方面具有不可取代的优势,但是面临单次航程小的能量约束限制;地面无人车虽然航程大,但监视范围小、运动范围受地形和实际路网限制.由两者组成的空地异构机器人系统能够弥补单一机器人系统的缺陷,已在灾后救援[1]、大型建图[2]、侦察[3—4]目标追踪[5]等领域表现良好的应用前景.如果将之应用于巡逻领域,无人车可作为着陆平台为无人机充电或提供备用电池[6—7],使得大范围的无人巡逻成为可能.然而,异构系统的引入却为巡逻路径规划带来了挑战.

无人机应用于巡逻问题必须解决其能量补给问题,现有方法可以分为两类,即静态补给和动态补给.本文主要从这两个方面分别阐述异构系统路径规划研究现状.采用静态补给的方法比如Kim[8]采用在不同地理位置建立多个共享静态充电站的方式来解决无人机能量约束问题,建立了一个基于混合整数线性规划（mixed integer linear program,MILP）的路径规划模型,通过遗传算法来寻找无人机最优飞行路径.Sundar[9]研究了多无人机和地面多个静态充电站路径规划问题,并建立了混合整数线性规划模型进行求解.Park[10]也是采用静态充电站的形式,在优化无人机路径的同时还对充电站的数量进行优化,从而减少经济投资.Maini[11]采用贪婪算法的思想在简单路网中计算出满足能够覆盖所有目标点的静态充电站最小数量及位置.

实际应用中,单个静态补给站很难满足各种复杂巡逻任务的要求,而建立多个静态补给站又会大大抬高成本,所以采用移动补给站便具有较大的优势.Mathew[12]研究了使用一组异构机器人协作执行持续任务,是在无人机路线提前设定好的基础上进行地面车的路径规划,为每架无人机设置一个时间窗,地面车只需要在时间窗范围内到达汇合点为无人机补充能量即可,且未考虑地面车的路网限制.Ren[13]研究了一个地面移动机器人充当加油站为两架交替飞行的无人机补充能量的路径规划问题,但两架无人机路径是建立在地面移动机器人轨迹已知基础上的.Mathew[14]研究了采用空地异构机器人系统进行包裹投递,但同样地面车也只能在提前预设好的路径中运动,然后在此路径上为无人机寻找满足能量约束的起降点,从而得到无人机的运动路径.Chen[15]在此基础上考虑了地面车的实际路网约束,采用“两步法”,先用蚁群算法在路网中规划出一条地面车路径,将地面路径离散之后再用遗传算法求解最短的无人机路径.Mathew[16]研究了移动充电站为无人机补充能量的路径规划问题,但文中假设无人机的路线是先验已知的.Yu[17—18]研究了空地异构机器人协作访问任务点的路径规划问题,考虑了无人机能量约束,但未考虑地面车的路网约束和任务的持续性.Maini[19]将空—地协作的覆盖监测转化成一个两阶段优化问题,建立了一个复杂的混合整数线性规划模型,优化出无人机路径和访问加油点的顺序.但当地面车处于某个加油点时,会等待无人机访问完此加油点所覆盖的所有目标点,导致任务时间增加,无人机路径规划结果出现较多重复路径.

现有关于空地异构机器人系统路径规划的研究,大多都未考虑无人车在地面真实路网中的运动路线约束,或者只是将地面车限制在预设的简易路线中规划无人机路径.在极少的研究中考虑了路网的约束,但也只是将空中和地面机器人的路径单独进行规划,而且未考虑任务的持续性.与之不同的是,本文不仅考虑了地面车在真实复杂路网中的约束,而且还在整个覆盖巡逻任务的持续性基础上将无人机和地面车的路径进行同步优化.

本文所研究的协作巡逻区域如图1所示,其中无人机执行持续覆盖巡逻任务,无人车充当无人机的着陆平台和移动补给站,可以在路网中合适的位置与无人机汇合并为其补充能量,从而实现无人机持续航行.本文研究的目标是为无人机找到一条满足能量约束的飞行巡逻路径,同时在路网中找到一条对应的无人车提供能量补给的路径.无人机和无人车相互协作是完成整个覆盖巡逻任务的关键,也直接影响整个任务的执行效果与代价.由于两者的路径高度耦合,以及能量约束、路网约束等实际困难,如何建立异构系统的协作路径规划模型并进行求解面临很大的挑战.本文的主要贡献包括:

图1 武汉市某区二环至三环卫星地图
Fig.1 Satellite map between the second ring and the third ring in a somewhere of Wuhan

1）充分考虑了空地协作持续覆盖巡逻过程中地面机器人路网、空地汇合时间、无人机能量、任务持续性等约束,建立了空地协作持续覆盖巡逻路径规划模型,并将模型由单机器人系统推广至多机器人系统;

2）提出一种结合遗传算法的改进蚁群优化算法（genetic algorithm-ant colony optimization,GA—ACO）,对本文无人机和地面车的协作路径同步优化求解.

本文的其余部分组织如下:第2节详细阐述了空地协作巡逻路径规划问题;第3节建立了协作巡逻路径规划模型;第4节详细介绍了采用改进蚁群优化算法求解上述路径规划问题的方法和步骤;第5节介绍了仿真实验结果分析;第6节是结论.

2 问题描述

为了更直观表达空地协作覆盖巡逻场景,将图1转化为无向拓扑图G=(V,E),如图2所示,V=[v1 v1··· vn]为路网中道路节点的集合,n为节点数目.引入邻接矩阵l ∈{0,1}n×n,当li,j=1时表示图中顶点vi和vj之间存在一条无向边,其他情况时为li,j=0,于是则构成了路网中边的集合E={ei,j,∀i,j}.用权重w ∈Rn×n表示各个顶点之间的权重,di,j表示从顶点vi到顶点vj之间的欧几里得距离. wi,j的计算方式如下:

图2 路网及其拓扑图
Fig.2 Road network and its topology

本文将对区域的覆盖简化为对点的覆盖,如图3所示.如果无人机在每个巡逻周期内完成对所有红色方块点不重复的访问则表示无人机对此区域进行了一次覆盖巡逻.图中地面车在基地S给无人机补满能量后与无人机一同出发,无人机可在区域内朝任意方向飞行,而地面无人车的运动轨迹严格限制在路网中,即无向图G中的边上.当无人机能量耗尽之前与地面车汇合进行能量补给后继续执行巡逻任务,那么就要求每次汇合时无人车至少在无人机之前到达汇合点,这样才能保证无人机不间歇的执行任务.

图3中无人机沿着黑色线段所表示的路径完成对多个目标点的巡逻,在能量耗尽之前降落在无人车上进行补能操作,红色线段表示无人车在路网中前往汇合点的运动路径.完成一个周期的覆盖巡逻后无人机和地面车都回到基地S,无人机进行能量补给后重复执行下一周期的巡逻任务.所以想要得到一条无人机最优的覆盖巡逻路径,关键在于优化出无人机在每个周期内访问这些点的顺序以及每次能量补充的位置和顺序.

图3 路网约束下空地协作能量补给示意图
Fig.3 Schematic diagram of air-ground cooperative energy supply under road network constraints

由于地面车只能限制在路网中运动,所以无人机与地面车的汇合位置必然属于无向图G中的边集合E上.为了方便计算,本文采用等距离散化的方法,将无向图G内的每条边进行等距离离散化,首先将每条边的两个端点均设为汇合点,然后在两个端点之间每间隔距离γ插入离散点作为汇合点.图4中所有青色的圆点表示离散化后的结果,每个圆点均代表无人机与无人车汇合并补充能量的可能位置,本文称之为潜在汇合点.

图4 潜在汇合点
Fig.4 Potential meeting points

3 路径规划模型

3.1 假设条件

针对上述空地协作巡逻路径规划问题提出以下假设:

1）忽略无人机起飞、降落过程,无人机仅在二维空间自由飞行,并且可向各方向飞行.

2）假设无人车限制在路网中行驶,可长期持续运动,能够为无人机提供足够多的备用电池.

3）一架无人机同时最多需要一辆无人车为其服务,一辆无人车同时最多能为一架无人机更换电池.

4）假设仅当无人机检测到自身能量剩余比例大于或等于δ时,无人机持续执行巡逻任务,不允许前往汇合点补能,当剩余能量比例小于δ时无人机随机选择巡逻操作或补能操作.无人机不必要也不能等到能量即将完全耗尽时才考虑飞往汇合点补充能量.

5）为避免无人机能量耗尽发生意外,每次补给能量时地面车须不晚于无人机到达汇合点.

3.2 变量定义

设巡逻区域内有M个待访问的巡逻目标点,离散的潜在汇合点数量为N,若求出无人机对巡逻点访问序列和补能汇合点序列,那么无人机的飞行总距离也就随之确定.假设无人机的数量为H,最大持续航程为U,在空中的飞行速度为Va,地面车的数量为A,在路网中运动速度为Vg.

待巡逻的目标点集合为P={p1,p2,···,pM},H架无人机和A辆地面车同时从S点出发,协作完成覆盖巡逻任务,则一共存在H条无人机路径.用表示第h架无人机的巡逻路径,用表示无人机h巡逻路径的第i个目标点,由于每架无人机从起点出发,那么=S.

3.3 数学模型

1）巡逻点全覆盖约束.

在进行每个周期的覆盖巡逻时各个目标点必须只被访问一次,则有如下约束:

2）无人机连续巡逻多个目标点的约束.

图5 无人机连续访问多个目标点
Fig.5 UAV continuously accesses multiple target points

所有无人机同时从起点出发,则有如下约束:

3）无人车为无人机补能操作的约束.

地面车配备有电池自动更换装置,当无人机降落后地面车可以自动为无人机更换电池实现能量补给,假设更换电池时间为tr.如图6所示无人机降落在地面车后,地面车在汇合点为无人机补能时保持静止,补能结束后无人机飞往下一目标点,地面车向下一个汇合点运动.由于能量补给过程中地面车没有发生位移,所以无人机的降落点和飞往下一目标点的起飞点在路网中是重合的,则有以下约束:

图6 无人机与地面车汇合示意图
Fig.6 Schematic diagram of the convergence of UAV and ground vehicle

4）无人机最大航程约束.

当无人机访问完目标点后选择飞往汇合点进行能量补给,那么无人机从上一汇合点起飞至到达下一汇合点降落期间所飞行的距离须小于最大航程,则有如下约束:

其中:

5）补能操作的时间约束.

由于多无人机多无人车系统实现的是多机器人整体调度,所以每次汇合后,需要对地面车与无人机的时间信息进行更新.用t=(t1,t2,···,tA)保存所有地面车到达汇合点的时间,T=(T1,T2,···,TH)保存所有无人机到达汇合点的时间.假设地面车a为无人机h补充能量,能量补给时间为tr,那么在汇合之后无人机h的时间更新为Th=Th+tr,而地面车要等待无人机到达完成补能之后才能出发去下一汇合点,所以地面车a的时间更新为ta=Th,这样才能保证两者的时间轴对应.用集合L=(L1,L2,···,LA)保存所有地面车位置信息,初始位置均为S,当地面车a到达汇合点后将La更新为当前汇合点的位置.多无人机多无人车协作执行覆盖巡逻任务时,只要保证每次补能时存在一辆地面车能够在无人机之前到达即可,不局限于某辆地面车单独为某架无人机补充能量.则至少存在一个a ∈(1,2,···,A)满足约束式（10）即可.

其中:

为避免多地面车任务冲突和资源浪费,每次汇合补能时一架无人机只允许一辆地面车为其补充能量.并且当存在多辆地面车均符合空地汇合时间约束时,无人机选择与距离最近的地面车汇合,则有如下约束:

Ch,a ∈{0,1},Ch,a=1表示地面车a为无人机h补能,其它情况Ch,a=0.

6）考虑多无人车避碰的路径规划模型.

所有无人机飞行总距离如式（12）所示:

本文以多无人机协作完成给定区域全覆盖巡逻任务的飞行总距离为代价构建路径规划模型.但还需满足多地面车协同为无人机补能时的避碰要求,因此对不同车辆的重复路径进行惩罚.假设多辆地面车重复路径的长度为lg,惩罚项系数为λ,则得到完整的路径规划模型P1如下:

4 模型求解算法设计

本文所建立的空地协作持续覆盖巡逻模型是一个复杂的多约束非线性优化问题,而且可看成是经典旅行商问题（travelling salesman problem,TSP）的变形.很多智能仿生算法,如蚁群算法、粒子群算法、遗传算法等被提出并应用于旅行商问题和机器人路径规划问题的求解中[20—21].本文所研究的路径规划问题与传统TSP问题不同的是,无人机除了访问目标点之外,还要访问一些汇合点来补充能量.而汇合点的访问次数和位置都是未知的,不同的路径需要补能的次数也可能不同,这就造成可行解集中路径点序列个数不同,即解的维度不确定.而蚁群算法通过轮盘赌与禁忌表的设计,可以使蚂蚁寻找路径时构建维度不一的初始解,并利用信息素反馈机制来不断优化路径.

但是传统蚁群算法求解时很难确定初始信息素分布,导致求解速度慢,本文提出一种遗传算法和蚁群算法相结合的方法（GA—ACO）,采用遗传算法生成初始信息素分布,再利用蚁群算法求精确解.首先,在不考虑无人机能量约束的情况下采用遗传算法求取能够完成全覆盖巡逻任务的最优路径,依据该路径计算蚁群算法的信息素初始分布.然后,再通过蚁群算法求解带能量和汇合时间约束的无人机最优巡逻路径,这样可以避免初始信息匮乏导致求解速度慢的缺点.

4.1 目标点的选择

采用蚁群算法求解本文路径规划模型时,所有无人机初始位置均为S,即蚁群算法中每个解的第1个数值为S,此操作保证算法满足约束式（7）.将无人机剩余能量Ur初始化为最大持续航程为U,当剩余能量比例≥δ时无人机选择飞往目标点.先结合距离、信息素计算出从当前点到目标点集合P中所有目标点的选择概率,再采用轮盘赌算法为无人机选择下一目标点,并判断剩余能量是否能够支撑无人机飞行到下一目标点.若满足则更新无人机位置和剩余能量,并将此目标点从集合P中删除,以保证每个目标点仅被访问一次,满足约束式（2）—（3）.若剩余能量不足以支撑无人机飞行到下一目标点,此时无人机放弃飞行到所选择目标点而是前往潜在汇合点,图7为无人机访问目标点流程.

图7 无人机访问目标点流程
Fig.7 UAV access target point process

4.2 汇合点选择

无人机在巡逻过程中既要访问所有目标点又要访问某些汇合点,于是在算法执行过程中可将汇合点看成带有特定约束的目标点,这样就可以将目标点和汇合点看成一个整体.本文算法的信息素也不仅仅只在目标点之间的路径上释放,在目标点和汇合点之间的路径上也同样会释放.所以,在汇合点选择策略上就与目标点一致,首先结合所有点之间的距离、信息素等信息计算出从当前点到所有汇合点的选择概率,再采用轮盘赌算法选择汇合点,保证了整个算法的随机性的和全局搜索能力.

假设目标点和汇合点的数量分别为M和K,蚂蚁在寻路过程中采用轮盘赌法,选择概率表示为

式中Pk ∈R(M+K)×(M+K),包含了蚂蚁在模型的所有点中互相到达的转移概率.当第m只蚂蚁选择目标点作为下一到达点时,allowedm表示更新后的目标点集合P,当选择汇合点时,allowedm表示无人机的剩余能量能到达的所有汇合点的集合.

同样τ ∈R(M+K)×(M+K),表示所有点之间的信息素浓度.η ∈R(M+K)×(M+K)为启发函数,表示蚂蚁从点集中任意一点选择其他点作为下一到达点的期望程度,与各点之间的距离成反比.α为信息素重要程度因子,β为启发函数重要程度因子.

在选择汇合点之前首先计算无人机剩余能量能够支撑无人机飞行到哪些汇合点,可保证算法满足约束式（9）.若结果为空集则当前蚂蚁寻路失败,若不为空则无人机飞往汇合点.当选择某个汇合点之后,计算是否至少存在一辆地面车能够在无人机之前到达,若不能则当前蚂蚁寻路失败,若可以则仅分配一辆地面车前往汇合点,算法满足约束式（10）—（11）,然后更新无人机和地面车的位置.汇合后将无人机剩余能量Ur重置为U,此时≥δ,那么蚂蚁会在目标点集合P中选择一点作为下一目标点,满足约束式（5）.循环执行上述操作,直至P变为空集后,则表示当前蚂蚁成功找到一条满足所有约束的巡逻路径,生成一个可行解.图8为无人机选择汇合点流程图.

图8 无人机选择汇合点流程
Fig.8 The process of UAV choosing a meeting point

4.3 信息素释放

传统的蚁群算法解决TSP问题时,通常每只蚂蚁都能够完成对所有城市的遍历操作,即表明每只蚂蚁都可以生成一个可行解.而本文所研究的空地协作路径规划问题中存在无人机的能量约束和异构机器人汇合的问题,所以不是每只蚂蚁都能完成对所有目标点遍历.部分蚂蚁寻路失败,形成无效解,而无效解信息素的释放会影响整个算法的求解性能.针对此问题本文对传统蚁群算法的蚁群数量和信息素释放方式进行如下改进:每次迭代时,蚁群数量不固定,若当前蚂蚁寻路失败生成无效解,则删除路径记录,若为有效解则保存路径,直到有效解达到设置的数量要求才进行当前代所有蚂蚁的信息素更新,然后进行下一次迭代.信息素更新方式为

式中:ρ ∈(0,1),表示信息素的挥发因子,ρ越大信息素挥发越快,反之信息素挥发越慢.表示蚂蚁m在经过的边E(i,j)上所释放的信息素.与传统蚁群算法不同的是,本文规定当某只蚂蚁寻路失败,不进行信息素的释放,计算方式为

式中:信息素增量Q为常数,fm为蚂蚁m所寻找的有效路径的总距离.设每次迭代时必须找到W个可行解,具体求解步骤如图9所示.

图9 蚁群算法求解空地协作路径规划流程
Fig.9 Ant colony algorithm to solve the air-ground cooperative path planning process

5 仿真实验结果分析

本文针对空地异构机器人系统的不同组合,做了多组仿真实验,以验证本文所提方法的有效性和通用性,并增加了一组每周期巡逻任务结束后无人机和地面车必须回到起点的对比仿真实验.实验验证了在持续巡逻中,无人机和地面车完成一个周期的巡逻任务后不回到起点,而是从当前位置出发继续执行下一周期的巡逻任务具有更高的巡逻效率.仿真实验过程中,δ=0.5,路网离散精度γ=0.6（离散化后的间隔长度）.

蚁群算法参数和其它参数分别如表1—2所示.

表1 蚁群算法参数
Table 1 Ant colony algorithm parameters

表2 其它参数
Table 2 Other parameters

5.1 无人机数量小于地面车数量路径规划结果

仿真结果如图10所示,其中S为无人机和地面车的出发点,红色方块为无人机一个周期内所要访问的目标点,蓝色线段为无人机的覆盖巡逻路径,绿色虚线表示地面车1的能量补给路径,红色虚线表示地面车2的能量补给路径.图中黑色实心点表示无人机与地面车汇合的位置,标记的数字为能量补给顺序,可以看出无人机从起点S出发后,一共需要5次能量补给才能完成全部区域的巡逻任务.每次汇合补能时无人机和地面车的到达时间如表3所示.从表3看出,每次汇合时地面车到达时间均小于无人机的到达时间,没有出现无人机等待地面车的情况,并且由于在目标函数中加入了地面车重复路径的惩罚项,在仿真结果中并未出现地面车路径重复或发生碰撞的情形.

表3 无人机与地面车到达汇合点时间
Table 3 The time when the drone and the ground reach the meeting point

图10 一架无人机两辆地面车路径规划结果
Fig.10 Path planning results of one UAV and two ground vehicle

5.2 无人机数量与地面车数量相等路径规划结果

为进一步缩短巡逻周期,本文考虑多架参数相同无人机与多辆参数相同地面车协作执行覆盖巡逻任务.实验分为两组,第1组实验中无人机和地面车均不需要回到起点,而是直接从当前位置出发执行第2周期的巡逻任务.第2组实验中无人机和地面车在完成一个周期的巡逻任务后要求回到起点,再从起点出发进行下一周期巡逻任务.

1）无人机和地面车均不回到起点路径规划结果.

不回到起点的仿真结果分为两个周期,第1周期仿真结果如图11所示.图11中两架无人机协作完成覆盖巡逻,两辆地面车在路网中共同为无人机进行能量补充.两架无人机与两辆地面车同时从起点S出发,黑色实线表示1号无人机的飞行路线,蓝色实线表示2号无人机的飞行路线.1号无人机补能两次,图中字母编号f11,f12分别表示1号无人机两个汇合点位置;2号无人机补能两次,图中字母编号f21,f22分别表示2号无人机的两个汇合点位置.地面车的能量补给路径以及加油点的分配情况分别如表4—5所示,从表中可以看出,每次汇合时地面车到达时间均小于无人机的到达时间,没有出现无人机等待地面车的情况.从图中可以得出,总共62个巡逻目标点,每架无人机都访问了31个目标点,均衡的分配了巡逻任务.

图11 第1周期路径规划结果
Fig.11 First cycle path planning result

表4 第1周期地面车补给路线
Table 4 First cycle ground vehicle supply route

表5 第1周期无人机地面车到达汇合点时间
Table 5 The time of UAV and ground vehicle arrive at the meeting point of first cycle

然后,无人机和地面车以第1周期的最终位置为起点,继续协作执行下一周期巡逻任务,此时要对无人机和地面车的初始时间进行更新.无人机的初始时间分别为到达各自的路径中最后一个点的时间,初始剩余能量为到达上一周期最后一个目标点之后所剩余的能量.而地面车的初始时间分别为到达各自路径中最后一个汇合点的时间加上一次补能时间,因为地面车到达汇合点补能结束后才能出发去下一个汇合点.

第2周期路径规划结果如图12所示,由于第1周期巡逻任务结束后无人机不回到起点补充能量,而是从当前位置直接进行第2周期的巡逻任务,所以无人机剩余能量小于最大航程,第2周期2号无人机补能三次,比第1周期多补能一次.地面车补给路径如表6所示,无人机与地面车到达汇合点的时间如表7所示.

表6 第2周期地面车补给路线
Table 6 First cycle ground vehicle supply route

表7 第2周期无人机地面车到达汇合点时间
Table 7 The time of UAV and ground vehicle arrive at the meeting point of second cycle

图12 第2周期路径规划结果
Fig.12 Second cycle path planning result

从第2周期仿真结果可看出,无人机和地面车从各自第1周期的终点出发,算法仍然能够找到一条最优巡逻路径,同样满足空地汇合的时间约束和地面车避碰约束.在第1周期里2号地面车为1号无人机服务,在第2周期里既为1号无人机服务还为2号无人机服务,实现了地面车在路网中整体调度.

2）无人机和地面车均要求回到起点路径规划结果.

无人机与地面车均回到起点的路径规划结果如图13所示,每次汇合补能时无人机和地面车的到达时间及最终回到起点的时间如表8—9所示.从表中可以看出,每次进行汇合补能时地面车到达时间均小于无人机的到达时间,没有出现无人机等待地面车的情况.最终,在最后到达的无人机返回起点之前,所有地面车均已经返回起点,也进一步验证了本文所提算法的有效性.

表8 地面车补给路线
Table 8 Ground vehicle supply route

图13 无人机与无人车回到起点路径规划结果
Fig.13 Path planning results of UAV and UAV back to starting point

三组仿真实验的无人机巡逻总距离如表10所示.通过表10可以看出,每周期巡逻结束后,无人机和地面车不回到起点的巡逻效率要明显高于回到起点的情况.实际上,不回到起点的路径使巡逻规律更加隐蔽,从而可以提高巡逻安全性.

表9 无人机地面车到达汇合点时间
Table 9 The time of UAV and ground vehicle arrive at the meeting point

表10 无人机巡逻路径总距离对比
Table 10 Comparison of UAV patrol path total distance

5.3 无人机数量多于地面车数量路径规划结果

当继续增加无人机的数量时,意味着地面车可能要在短时间内为多架无人机补能.为进一步验证本文所提方法的通用性,考虑由三架参数相同无人机与两辆参数相同地面车协作执行覆盖巡逻任务.

仿真结果如图14所示,图中三架无人机协作完成覆盖巡逻,两辆地面车在路网中共同为无人机进行能量补充.两架无人机与两辆地面车同时从起点S出发,黑色实线、蓝色实线、褐色实线分别表示1号、2号、3号无人机的飞行路线.三架无人机各补能一次,汇合点位置分别为图中标记f1,f2,f3的位置.地面车的能量补给路径以及汇合点的分配情况分别如表11—12所示.

图14 三架无人机两辆地面车路径规划结果
Fig.14 Cooperative path planning results of three UAVs and two ground vehicles

表11 地面车补给路线
Table 11 Ground vehicle supply route

表12 无人机地面车到达汇合点时间
Table 12 The time of UAV and ground vehicle arrive at the meeting point

仿真实验表明,在无人机数量大于地面车时,实现了无人机错峰补能,在满足空地汇合时间约束的情况下规划出一条较好的巡逻路线,进一步减少了车辆投入成本.以上多组实验结果说明本文所提方法具备有效性和通用性,不仅能够规划出不同数量下无人机、无人车协作持续巡逻路径,还能实现多地面车的避碰.

5.4 算法性能分析

为了验证本文算法的有效性,本文将本文算法GA—ACO与传统ACO算法进行对比.在同样参数下分两组实验,第1组实验为一架无人机与两辆地面车协作,第2组实验为两架无人机与两辆地面车协作.重点比较两种方法的时间复杂度和迭代曲线.两组实验的迭代曲线分别如图15—16所示,时间复杂度比较如表13所示.

图15 一架无人机与两辆地面车协作算法对比迭代曲线
Fig.15 Iterative curve of algorithm comparison between one UAV and two ground vehicles

图16 两架无人机与两辆地面车协作算法对比迭代曲线
Fig.16 Iterative curve of cooperation algorithm comparison between two UAVs and two ground vehicles

表13 算法性能（运行时间）对比
Table 13 Comparison of algorithm performance（running time）

对比结果表明,本文方法的计算时间随着空地机器人组成变化而变化.由于两架无人机与两辆地面车协作时,模型中增加了较多约束,因此与仅有一架无人机巡逻时的情形相比计算时间有大幅增加.本文引入遗传算法计算初始信息素后,虽然路径最优值没有明显提升,但算法的收敛速度更快.一架无人机时,算法运行速度提升了48.6%;两架无人机时算法运行速度提升了74.4%.结果表明当无人机和无人车数量增加时,GA—ACO算法与传统ACO算法相比,求解效率和收敛速度得到了较大的改善.

6 结论

本文研究了空地异构机器人系统协作持续巡逻的路径规划问题.考虑了无人机能量、路网、空地汇合时间、任务持续性等多种约束,以无人机飞行总距离最短为目标建立数学模型.采用遗传算法与蚁群优化结合的GA—ACO算法来求解路径规划,仿真实验表明该方法计算效率高,可以得到无人机的最优巡逻路径以及与之对应的地面车能量补给路径.

此空地协作持续巡逻路径规划方法还适用于其它具有共性问题的领域,例如空气质量采样、发电厂巡检、交通监控以及自然灾害监测等.本文空地协作模型能够考虑无人机的能量限制,实现无人机对某些特定区域的持续巡逻和监测.本文所提出的算法能为求解不同领域的基于真实路网的空地协作路径规划问题提供实际经验和理论基础.

由于本文重点研究路径规划问题,所以将区域覆盖巡逻简化成为对均匀离散点的访问,离散点的选择忽略了无人机的观察视野的具体约束,后续工作将对其深入研究.另外,本文未考虑航迹优化问题和巡逻障碍区域的影响,为了更加贴近实际,后期拟将障碍区域增加到任务中,对机器人的轨迹做进一步优化.并考虑将该算法移植于空地异构多机器人平台（地面移动机器人与无人机）,在异构机器人系统精确定位、无人机自主降落、无线通讯等方面开展相关实际实验.