考虑中继充电的小型无人机侦察路径规划

毛慧婷 石建迈 周玉珍 刘 忠

1.国防科技大学系统工程学院信息系统工程重点实验室 湖南长沙 410073

随着高技术作战体系日趋完善,现代战争对战场信息的及时获取和空间的争夺日趋激烈,对作战对象的目标侦察以及位置获取等提出了更高的需求.当前军事侦察技术主要包括有人驾驶飞机侦察、无人机侦察以及卫星遥感侦察,在这些技术中,无人机侦察技术由于其响应及时、部署灵活且无人员伤亡风险等特点,得到了广泛的应用.同时传感器技术、信息传输网络以及飞行器平台的飞速发展,为无人机在战场上的侦察提供了强有力的技术支撑[1].

在实际作战过程中和军事运筹研究中,无人机路径规划都属于十分重要的课题[2].无人机侦察路径规划主要是指在某一特定战场中,尽可能地减少无人机的使用数量,在较短时间内完成所有既定目标的侦察任务,提高侦察效率.Shetty 等考虑了基于目标优先级的多无人机任务分配以及路径规划问题,采用禁忌搜索算法对问题进行求解[3].Mufalli 等在多无人机路径规划过程中考虑了无人机（unmanned aerial vehicle,UAV）的载荷约束,即无人机续航能力受载荷重量影响,建立了其规划模型,并通过列生成与启发式算法求解了该问题[4].Evers 等研究了考虑目标时间窗口约束的多无人机侦察路径规划问题[5].Mahmud 等研究了如何避免无人机被敌方预测的侦察路径规划问题[6],提出了一种协作路径规划方法.

随着无人机小型化、智能化的发展趋势,具有体积小、隐蔽性强、运用灵活、成本低等优势的小型无人机在战场近距离侦察中得到越来越广泛的应用.但是小型无人机续航里程短,从基地出发后其可服务的范围半径就受到相应的限制,这大大降低了侦察效率,使其难以完成所有侦察任务.尤其对于区域内分布较为分散的目标点来说,无人机的侦察任务更为艰巨.为解决这方面的问题,国防科技大学罗志浩、刘瑶、刘忠等提出了应用地面车辆搭载小型无人机协同进行战场情报侦察的作战运用模式[7-8].地面车辆作为移动平台,可以携带小型无人机在战场大范围内机动,在运动过程中放飞和回收小型无人机,并为无人机提供充电、更换电池等保障.无人机不断在地面车辆上起飞降落,通过多次续航,完成战场目标的侦察任务.Sundar 研究了单无人机的路径规划,且允许无人机返回基地进行充电[9].Bingxi 提出了同时考虑任务优先分配和充电站选址的大规模搜救任务规划,且规定在充电站的充电时间是一定的[10].Ribeiro 研究了无人机在采矿业中用于带式输送机检测系统的场景[11],但同时规定无人机在充电站只能充满电.在民用领域,各大商业物流公司将小型无人机用于“最后一公里”配送,以提高物流配送效率.如：Coelho 等通过设计双层路径模型,在动态需求的环境下,允许无人机在既定充电点进行充电以完成配送[12].Chiang 等将车辆与无人机协同进行包裹配送,并利用遗传算法求解证明该配送模式可大大降低空气污染和能源消耗[13].刘瑶、刘忠等应用模拟退火算法求解车辆与无人机协同进行快递配送的路径优化问题[14].在这些研究中,通过地面车辆的辅助,有效拓展了无人机的侦察范围,但是受续航能力限制,无人机仍然只能在车辆行驶路线的一定范围内进行侦察活动,并且车辆与无人机路径规划时需要考虑两者在时空方面的密切协同.

为了克服小型无人机续航能力的限制,提出一种新的小型无人机战场侦察应用模式.通过为我方作战装备,如装甲车辆、运输车辆等,加装小型无人机快速无线充电设备,使其成为小型无人机的中继充电平台.在作战过程中,这些装备因各自任务分散部署到战场上时,就形成了一个可为小型无人机进行中继充电的充电站网络.小型无人机在执行侦察任务过程中,当电量不足时,可以到附近具备充电能力的我方作战装备上进行快速充电,然后继续执行任务.这种情况下,在优化无人机侦察路径的过程中,还需要优化选择中继充电点的决策.这种考虑中继充电的无人机路径规划问题与商业领域电动汽车的路径规划比较相似[15].两者的共同之处在于,在执行任务过程中都需要访问充电点进行充电,以增加续航能力,完成后续任务.不同之处在于,充电汽车在等待和服务客户时是不消耗电量的,而小型无人机在目标附近等待和对目标进行侦察时,都会消耗电量,并且侦察目标时由于传感器开始工作,其耗电速度更快.因此,需要针对战场上小型无人机这种新型运用模式的路径规划问题,研究新的模型和求解算法,提高小型无人机战场侦察的指挥控制效率.

1 问题描述与建模

在考虑中继充电的小型无人机侦察规划问题中,多架小型无人机从临时基地出发对战场上的多个目标进行侦察,侦察过程中电量不足时,可以寻求我方在战场上的搭载快速无线充电设备的作战平台进行快速充电,然后继续执行侦察任务,每架无人机通过多次中继充电接力,协同完成战场区域内所有预定目标的侦察任务.图1给出了一个无人机中继充电模式下的侦察飞行路径示意图.

图1 无人机中继充电飞行路径示意图Fig 1 Schematic diagram of UAV routing with recharging

考虑中继充电的无人机路径规划问题中的关键要素与约束如下.

1.1 小型无人机

执行侦察任务的小型无人机为锂电池驱动,电池容量是确定的,无人机飞行时消耗电量与飞行速度和距离相关.无人机搭载的传感器在侦察目标时消耗电量与侦察精度和时间相关,不侦察目标时,侦察传感器关闭,不消耗电量.当无人机悬停在侦察点上方等待合适的目标侦察窗口时,仍需要消耗电量,但电量消耗速度小于飞行或侦察时的消耗速度.无人机从基地出发,完成侦察任务后必须回到基地.

1.2 中继充电平台

我方一些作战平台,如装甲车、运输车辆、导弹发射车等装备,事前安装了快速无线充电设备.这些平台因各自的任务分散部署在战场上,能够为无人机进行快速充电,为无人机的充能量与充电时间相关,且充电函数已知.这些作战平台在战场上的位置和无人机指挥中心是信息共享的.

1.3 侦察目标

需要侦察的目标分布在战场不同位置,并且每个侦察目标只能在给定的时间窗口进行侦察,并且每个目标的侦察时间与精度是任务给定的,目标的位置信息也已知.

在给定上述信息的情况下,考察中继充电的无人机侦察路径规划问题,通过优化每架无人机访问侦察目标和中继充电平台的飞行路径来最小化侦察任务完成的总时间和无人机使用数量.应用混合整数规划建模方法,建立考察中继充电的无人机侦察路径规划的数学模型.

首先,模型中采用的参数变量符号如下：

点集V1 侦察目标集合F 中继充电点及其副本集合{0} 无人机基地{n+1} 同为无人机基地,用来表述无人机返回的节点序号V0 表示侦察目标、中继充电点和出发点的集合,即Vn+1 表示侦察目标、中继充电点和返回点的集合,即V 所有点的集合参数dij 无人机从侦察目标i 飞到j 的耗电量tij 侦察目标i 到j 的飞行时间g 无人机电池的充电率si 目标i 的侦察时间ei 目标i 侦察时间窗口的最早开始时间li 目标i 侦察时间窗口的最晚开始时间Q 无人机的电池容量α 一架无人机的权重系数β 总体侦察时间的权重系统,α+β=1 si 无人机完成目标i 侦察任务的耗电量cw 无人机单位等待时间的耗电率cuav 无人机单位使用成本决策变量ui 目标i 的开始侦察时间,i∈V1 yi 无人机到达目标点i 时的剩余电量,i∈V1 qi 无人机在充电站i 的充电量,i∈F Yi 无人机离开充电站i 时的电量,i∈F δi 无人机在目标i 的等待时间,i∈V1 xij 当无人机从点i 飞往点j 时,为1,否则为0 zj 当选择中继点i（i∈F）进行充电时为1,否则为0

数学规划模型如下：

在模型中,目标函数（1）通过加权最小化无人机使用数量和总体侦察时间.约束（2）确保每个目标被侦察一次.约束（3）处理侦察点与中继充电点之间的连接性.约束（4）确保每个点的飞入次数和飞出次数是相等的.约束（5）限定侦察目标访问时间的可行性.约束（6）限定访问中继充电点的时间可行性.约束（7）限定访问侦察目标的时间窗口.约束（8）和（9）确保无人机离开侦察目标或中继充电点时电量是非负的.约束（10）确定无人机离开中继充电点时的电池状态.约束（11）确保充电量不超过无人机电池容量.约束（12）～（14）为变量限定约束.

对比充电汽车路径规划模型,可以看出,中继充电无人机路径规划不需要考虑货物装备问题,其携带的传感器重量是恒定的,但是无人机在等待过程中以及在侦察目标点进行侦察时都在消耗电量,需要建立相应的约束进行建模,而充电汽车在等待和目标点服务时不消耗电能,相应模型中也没有体现.同时大部分充电汽车采用电池充满策略,而无人机为了尽快完成侦察任务,在中继点进行部分充电,只充后续路径需要的电量,以节省时间.

从模型特点来看,当前充电汽车路径规划的相关算法难以直接解决该问题,需要研究新的算法,设计新的智能搜索策略和算子,为中继充电无人机侦察路径规划提供高效求解算法.

2 算法设计

考虑到小型无人机在侦察过程中需要中继充电的问题复杂性,本文设计了一种改进的蚁群算法.蚁群算法是一种新的仿生类随机型搜索算法,仿照自然界中蚂蚁觅食的自然现象,由意大利学者Dorigo 等提出,具有群体合作、正反馈选择、并行计算等特点.近年来蚁群算法逐渐被用于求解各种车辆路径规划问题[16-20],是一种有效的求解手段.

为适应本文中的小型无人机侦察路径问题特点,本文对蚁群算法进行了两方面的改进.首先考虑到充电站的选择和充电水平的确定,设计了一个最优充电站插入启发式算法；其次,鉴于问题的复杂性,引入局部搜索算法,扩大蚁群算法迭代过程中的搜索空间,增加最优解的搜索概率.改进蚁群算法的主要步骤如算法1.

算法1 改进的蚁群算法1 参数初始化2 构造初始解3 初始化信息素浓度4 While 迭代次数小于Max_iteration 5 对所有的k 个蚂蚁,并行构建其NR 解,直至完成所有蚂蚁的路径构建6 插入充电站启发式算法7 局部搜索8 信息素更新9 End While 10 输出最优可行解

2.1 蚁群初始解构造

其中,dij表示边＜i,j＞的长度,lj表示下一个目标点j的最晚服务时间,该值越小表示其时间窗越紧迫.

2.2 信息素更新

在信息素的更新机制中引入了信息素挥发机制.本文采用精英蚂蚁策略,即不仅采用搜索产生的最优解更新信息素浓度,其余精英蚂蚁产生的较优路径也会被用于信息素浓度的更新.其更新方式如下：

2.3 充电站插入启发式算法

由于小型无人机电池容量有限,其续航里程受到电量水平的限制.蚁群算法求解出的不考虑充电站（no-recharged,NR）的解（φ0）,其路径一般不满足里程约束.因此,需要在这些路径中插入充电站对无人机适当充电才能保证侦察任务的顺利完成.本文设计了一个充电站最优插入启发式算法解决该问题,算法主要步骤如算法2.

充电站插入算法的基本思路如下：首先确定该路径的行驶里程是否超出无人机最大续航里程,然后找出无人机可到达的最远目标点,即无人机可以到达该目标点,但无法访问下一个目标点.寻找距离该目标点后最近的充电站,插入至该目标点后.检查剩余路径是否可行,如不可行,则按该方法继续插入充电站,直至路径可行.

算法2 充电站插入启发式算法Input:初始NR 解Output:最优可行解1 For 不可行解in 2 找到UAV 能到达的最远客户点3 For 前一个充电站/仓库和最远客户点之间的所有节点4 在当前点之后插入距离最近的充电站5 确定充电量6 检查时间窗是否可行7 If 路径时间窗不可行8 将时间窗不可行的客户点移除该路径9 将移除的点加入集合10 Else 11 从中移除可行路径并将其加入12 End if 13 End for 14 End for 15 While中的NR 解采用邻近点搜索17 重复以上1-14 行18 End While 16 对

确定了充电站的插入位置之后,即可通过后续飞行路径所需要的实际电量对无人机进行充电.由于无人机除了飞行时间和侦察时间要耗电之外,若无人机在该侦察点最早侦察开始时间之前到达,无人机需要悬停在侦察点上方进行等待,该等待过程同样需要耗电.因此,无人机在后续侦察点的等待时间内的耗电量会影响前一个充电站的充电水平,进而影响无人机所需要的充电时间.同样地,无人机在充电站的充电时间很大程度上会影响后续侦察点等待时间的长短.因此,这两者因素的交互影响使得如何确定无人机在充电点的充电水平变得更为复杂.为了解决该问题,本文允许无人机在充电站可以多充电,即先不考虑充电时间计算出后续飞行路径所需要的耗电量确定无人机的充电水平.一旦确定了相应的充电时间之后,其后续路径的等待时间有可能会相应缩短,进而使得无人机在到达下一个充电点或者基地时往往会有剩余电量,这就是多充电原则.

当充电水平确定之后,检查该回路上的目标侦察点时间窗约束是否仍然满足.若有目标点的时间窗不满足,则将该目标点从该路径中移除并将其添加到集合.在整个充电站插入的过程中,可行解的接受第一准则首先是尽可能保留较多的目标点,其次则是接受较低成本的可行解.

2.4 局部搜索算法

局部搜索算法可以在一定程度上防止蚁群算法陷入局部最优解,扩展蚁群算法单次迭代过程中的搜索范围,提高搜索的可行解质量.在本文中,局部搜索算法主要由移除算子与插入算子两部分构成,其通过不断破坏与重构当前解,增加解的多样性.考虑到在局部搜索过程中每进行一次解的调整,充电站的最优插入也会不同,因此,本文的局部搜索是在移除充电站的路径上进行的.在完成迭代后,再通过插入充电站生成可行解.

2.4.1 移除算子

本文采用的移除算子可以分为两类：路径移除与目标点移除.路径移除是指将路径上的所有目标点移除,目标点移除是选择一定数量的目标点移除.移除的数量根据总目标点数决定,其首先根据总目标数确定一个特定区间,然后在区间内随机选择.

1）随机路径删除：随机路径删除算子通过随机选择一条路径,将该路径中的所有目标点加入到移除列表中实现移除.随机选择删除算子可以扩大搜索空间.

2）最短路径删除：最短路径删除算子是选择所有路径中最短的,将该路径中的所有目标点加入到移除列表中.其目的是尽量提高车辆利用率.

3）结束最早路径删除：结束最早路径删除算子通过选择路径中返回时间最早的路径,将该路径上所有目标点加入到移除列表中实现移除.其设计主要基于对现实因素的考量,最大化车辆的工作时长.

5）最差目标点删除：最差目标点删除算子对每个目标点计算其距离前后相连目标点的距离之和,并对所有点进行排序,然后移除最大的个目标点.该算子如图2所示.

图2 最差目标点删除算子Fig 2 Worst-distance target removal

6）基于时间窗的目标点删除：基于时间窗的目标点删除算子,首先随机选择一个目标点,然后移除其余目标点中最晚服务开始时间与该目标点最晚服务开始时间最接近的目标点,重复该过程直至删除个目标点.

7）基于距离的目标点删除：基于距离的目标点删除算子先随机选择一个目标点,然后移除距离该目标点最近的目标点,重复该过程直至删除个目标点.该算子如图3所示.

图3 基于距离的目标点删除算子Fig 3 Proximity-based target removal

2.4.2 插入算子

插入算子主要是将移除的目标节点重新插入路径中,在插入算子的设计中只考虑当前路径时间窗以及车辆容量的可行性,而不考虑车辆里程的约束.

1）贪婪插入：在依次插入移除的目标点时,选择所有可插入位置中使得插入成本增加最少的位置.

2）后悔值-2 插入：计算每个移除的节点的前两个最佳插入位置,计算这两种插入方式的成本差.选择差值较大的目标点,将其插入最佳位置.

3）基于模拟退火准则插入：找出所有被移除目标点的最优和次优插入位置,并以一定的概率接受次优解.

4）优先插入准则：首先计算出每一个被移除的目标点可重新插回当前解的位置个数,按该数值进行升序排序,依次选择目标点插入其最优插入位置.该算子的目的是尽可能将所有客户点成功插回,避免重新指派一架无人机.

在局部搜索过程中,移除算子与插入算子具有相同的权重,采用轮盘赌方式随机选择算子的组合.局部搜索算法的主要步骤见算法3.

3 实验分析

由于无人机在整个飞行、侦察以及悬停等待过程中所消耗的电量水平均有所不同,假定耗电率均与所耗时间线性相关.且无人机在充电站会根据实际需求进行适当充电,因此,其充电时间与充电水平、充电速率均相关.本实验中关于无人机的相关参数设定见表1.

表1 无人机相关参数Table 1 Related parameters of UAV

为了验证本文的模型与算法,在实验中分别对4种规模案例（A,B,C,D）进行求解,分别含有5,10,15,100 个目标侦察点以及相对应的充电平台数量（包括基地）分别为4,4,5 和21.算法所有代码由Visual C++ 编程实现,在处理器为Intel（R）Core（TM）i5 -8265U,内存8 G 的笔记本电脑上运行,蚁群算法相关的参数值设定为P=30,α=5,β=5,γ=10,=0.25,Q=100,种群迭代100 次,算法停止.结果如表2所示.

表2 4 个案例的计算结果Table 2 The results of the four cases

算法3 局部搜索Input:不考虑充电站的NR 解Output:最优可行解1 初始化算子权重2 插入充电站生成可行解3 4 While 迭代次数小于最大迭代次数5 随机选择移除算子,并生成移除列表6随机选择插入算子,将列表中的客户点重新插入7 调用插入算法插入充电站，生成当前可行解8 if 总成本低于9 10 End if 11 移除中所有解,得到新的最优解12 End While

在飞行侦察路径中,所有无人机均从基地出发,结束侦察任务后返回基地.路线中序号代表目标侦察点以及充电站,括号内的数值表示无人机在该充电站的实际充电水平,具体飞行路线如图4所示.实验结果显示改进的蚁群算法可以在18 s 内解决15 个目标点以内的小规模,可以在25 min 内解决包含100个目标点的大规模案例.

图4 不同规模案例的飞行路径Fig 4 The routes for cases of different size

为了进一步确定改进蚁群算法的效果,应用传统蚁群算法对4 个案例进行了求解,并将计算结果和改进蚁群的计算结果进行了对比,如表3所示.可以看出,对于5 个侦察点的小规模案例,两者都得到了相同的最优解,而对于另外3 个中等规模和大规模的案例,改进蚁群算法明显优于传统蚁群算法.因此,从计算时间和效果来看,改进蚁群算法具有较高的实际应用价值.

表3 蚁群改进前后求解方案目标值对比Table 3 The results of the four cases

4 结论

针对小型无人机在复杂战场环境下的目标情报侦察任务中的应用,提出了一种中继充电模式下的无人机侦察路径规划问题.当无人机电量不足时,允许无人机在侦察过程中可以飞往特定的充电平台进行快速充电以完成后续侦察任务,且采用部分充电策略来尽可能地减少充电时间,从而更快速地完成战场侦察.通过改进蚁群算法对问题进行求解,实验结果显示改进蚁群算法明显优于传统蚁群算法,并且对于大规模问题的计算时间控制在25 min 以内,在实际任务规划中具有较高的应用价值.

在未来智能化、无人化战争中,越来越多的小型无人机将被用于执行各种作战任务,中继充电模式具有广阔的应用前景.无人机中继充电路径优化作为一类新的路径规划问题,还存在很多扩展研究方向,如无人机侦察过程中充满着很多不确定因素和风险因素,在路径规划中增加敌方威胁、目标动态变化等因素的影响,研究不确定中继充电路径规划方法,为复杂动态战场环境下的小型无人机指挥控制提供理论支撑.