基于多蚁群系统的多无人机反侦察航迹规划

贾雨薇,邵 忻

(天津外国语大学,天津 300011)

0 引 言

随着无人机技术的发展,无人机侦察已成为当前海上态势感知的重要途径之一。

无人机侦察具备机动性好、定位精度高、准备时间短的优势,能有效克服传统航天侦察过境时间有限、技术侦察无法确定电磁静默目标的缺点。多无人机协同目标搜索是多无人机联合实施的重要任务。在大型搜索区域,当任务繁重和时间紧张时,单架无人机显然无法快速完成搜索任务,而多架无人机可以有效地完成搜索任务。如今,反无人机防空武器的综合运用给战争中的预警探测和拦截打击带来了一些技术挑战[1]。

1 研究背景

无人机航路选择成为发现目标的关键,因为目标在搜索空间中以一定的概率出现。DM Geletko,AT Davari 等人针对多无人机在同一区域内进行搜索的情况,提出了一种分布式协同控制算法。其主要思想是整合简单的规则,使它们相互关联,从而产生复杂的行为。通过半实物仿真演示,多架无人机可完成高度独立、自主飞行。针对多无人机搜索,设计了随机搜索、航空搜索和网格搜索3种搜索策略。

袁广进等人使用多蚁群系统解决多无人机搜索问题。不同的蚁群释放不同的信息素,并且产生相互排斥的效果。每个蚁群中的所有蚂蚁在完成搜索时都会更新信息素,通过最大最小蚁群算法防止信息素过度挥发或积累,并根据搜索概率的模型调整搜索路径。仿真实验结果显示,这种算法很好地完成了多架无人机之间的协作。

同时,如果区域面积较大,少量无人机难以在规定时间内完成既定搜索任务,也可以考虑增加无人机数量。刘永兰等人提出利用狼群算法解决无人机航路规划问题,构建无人机在航路规划中可能遇到的障碍模型。以地形障碍和局部威胁模拟为山峰,抽象出3种捕食行为,即行走、召唤和攻击。游走行为相当于找到解空间,增加解的多样性。呼叫行为相当于逼近最优路线,在单架无人机难以完成任务时呼叫协作伙伴,从而提高任务完成概率。攻击行为相当于集中在最佳路线上,提高了算法的收敛性。仿真结果表明,该航路能够在较短时间内成功避开障碍物并找到搜索目标。

2 问题的提出

2.1 场景规划

假设红方部署2类无人机,分别为低速长续航的U1类无人机与高速短续航的U2类无人机,使用合成孔径雷达对潜伏在某海域内刺探红方情报的蓝方电子侦察船开展搜索,以期在限定时间内发现和驱离蓝方目标,保护红方信息安全。

2.2 航路规划

假定在蓝方电子侦察船进入侦察位置后,红方4架固定型号无人机按指定路线对可疑海域开展搜索,其中红方限制如下:

(1) 搜索时间为3 h;

(2) 每种型号无人机有且仅有2架;

(3) 无人机初始位置为A1、A2机场;

(4) 保证3 h后发现目标概率最大;

(5) 适时考虑返航。

蓝方约束如下:

(1) 按照给定概率在指定海域出现;

(2) 机动半径为10 km。

3 基本假设

假设1:在侦察阵位为1 000 km×1 000 km的区域,将其划分为1 000×1 000个长宽均为1 km的正方形方里格,由于无人机巡航速度较快,较短时间内的飞行轨迹近似为直线。考虑无人机1个步长时间只移动1个单元方里格,且受无人机机动条件的影响,每次移动均存在3种不同的运动。运动方式为按照巡航速度直线匀速运动,且每次步长移动位置均为方里格中心点,如图1所示。

图1 无人机航行方向图

假设2:考虑蓝方侦察船到达侦察阵位后,会进行半径为10 km的机动,假设其圆心点位于方里格中心位置。

假设3:无人机每隔20 s进行一次拍照,因此将移动时间间隔设置为20 s,即无人机侦察照相始终开启,保持每20 s 1次的拍摄状态,且不影响续航时长。

假设4:无人机和船机动时保持匀速运动,即转弯与直行保持同速,均保持最大航行速度。

4 问题的模型建立与求解

4.1 问题分析

基于已经给定的蓝方侦察船出现概率图等,并且告知了无人机发现目标概率的计算方法,考虑蓝方侦察船会以10 km的半径进行机动,这将影响其在周边范围出现的概率。所以需要考虑侦察船对概率图的更新,同时考虑无人机搜索对概率图的更新。概率图如图2所示,图中的颜色越深,代表目标在该区域出现的概率越大,要找寻最优路径,首先要考虑单个无人机对于发现目标概率的模型,以及确定优化目标。其次考虑多架飞机的协同搜索问题,尽量保证多架无人机的搜索范围覆盖面最大,即4架无人机的搜索路径尽量不交叉[2]。

图2 目标出现概率热图

需要规划合适的搜索路线,计算路径中的每个节点(步)的概率,并保证搜索路线中发现概率之和最大。考虑巡航续航时长U1型8 h,U2型4 h,均具有持续搜索3 h的能力,对于8 h巡航无人机可以不考虑其返航,考虑4 h的无人机在巡航3 h后,若与机场航向较远,即直线距离大于620 km,不能返航。采用离散化的方式将搜索时间离散化为一系列的离散时间点{1,2,…,T}。无人机在每个网格内停留的时间为ΔT,并完成对当前网格的搜索。在相邻的时间点上,飞行器由当前网格移至与之相邻的网格[3]。

无人机的基本参数如表1所示。

表1 红方无人机基本参数表

由于路线计时单位为s,为了便于计算,将巡航速度化为km/s,U1的速度约等于0.889 km/s,U2的速度为1.778 km/s,U2毎横向或者纵向移动1格的时间为5.63 s,毎斜线移动1格的距离所耗费的时间为11.2 s。

4.2 模型构建

4.2.1 侦察船运动对概率图的影响更新

结合概率热图以及题中所给的目标船机动半径,假设其在圆形区域内出现的概率服从均匀分布,并且每个方格出现的概率值相等。对各方里格的目标出现概率进行更新,该点目标出现的概率值为其附近10 km内其余方里格机动距离的叠加,近似为20×20的大方里格,除去顶角的20×4个单位方里格,如图3所示。

图3 目标概率更新示意图

目标出现概率更新为:

(1)

最后将更新的概率进行归一化:

(2)

得到最终目标出现概率模型[4]。

4.2.2 基于Bayes的无人机发现概率更新

无人机当前所在方里格的发现概率为以方里格为中心、探测距离为半径为R的圆形区域。其中目标在m个方里格中被发现的概率满足:

(3)

式中:zk=D,表示k时刻的探测事件,则zk=D为未探测事件且满足:

(4)

无人机在观测事件发生后,可根据 Bayes公式更新无人机的目标概率图,为:

(5)

式中:λ为归一化因子,使得任务海域所有栅格的目标概率之和为1。

4.2.3 优化目标函数

构建目标优化函数为:

(6)

其中航行距离约束为:Du1≤620。

路线约束为:S1∩S2∩S3∩S4=Ø。

4.3 问题的求解

4.3.1 多蚁群系统优化算法简介

自组织行为仿生算法是解决优化问题的可靠方法,具有极强的鲁棒性和收敛性,而蚁群算法是自组织行为仿生算法中最引人注目的算法,它通过模拟蚁群在觅食过程中总能找到从蚁巢到食物源的最短路径构建求解路径。蚁群系统算法是对蚁群算法的改进,可以用于解决伪随机路径规划,也适用于具有先验概率的路径求解问题,适用于本题中具有概率图的路径寻优问题。

多类型蚁群算法是对单蚁群算法的改进,其增加了不同类型蚁群之间的互斥作用,增加了互斥路径的优化搜索实验。多蚁群算法因具有协调性与并行性、正负反馈机制以及强启发性而成功应用于航迹初始化。这一性质非常适用于多个无人机求解最优路径,满足各路径尽量不重叠的要求。

本文将多蚁群系统算法应用于解决多无人机协同目标搜索问题。将单个执行搜索任务的无人机模拟为1个蚁群系统,同一蚂蚁群体内部通过信息素引导个体趋向最优路径,来自不同蚂蚁种群之间的信息素相互排斥实现不同无人机之间的竞争,以避免多架无人机搜索相同区域造成无效搜索[5-7]。

4.3.2 多蚁群协同搜索算法的基本步骤

多蚁群协同搜索算法流程如图4所示。

图4 算法流程图

假设有n架无人机执行协同搜索任务,每架无人机对应1个蚂蚁种群,每个种群由m只蚂蚁组成。

首先对搜索区域的所有网格给出合适的信息素初始值。再将全部蚂蚁放在所在种群的路径初始点,一起同时在搜索区域内移动。每只蚂蚁在行进中根据状态转移规则选择相邻的可行网格,直至全部蚂蚁完成一次路径搜索,即完成一次循环。

循环完成后依据各只蚂蚁经过路径进行全局信息素更新,对没有经过的网格只进行信息素挥发。重复这个过程,直到求出优化路径。

4.3.3 多蚁群系统算法在本题中的具体实现

(1) 信息素的初始化

信息素分布在每个网格内,每个网格内的信息素初始值为τ0。蚂蚁从S点开始搜索,每一步搜索范围是与其当前所在网格邻近的满足机动条件的4个网格。

(2) 路径选择策略

第k个种群的蚂蚁l选择新可行节点的概率是由两节点间边的代价、自身所在种群信息素的强度以及其它种群信息激素的强度决定的,下式给出了从网格i转移到可行网格j的概率:

(7)

(3) 信息素的更新策略

在所有群体中所有的蚂蚁都完成一次搜索后,网格j内第k个种群的信息素强度按下式更新:

τjk(t+1)=(1-ρ)·τjk(t)+ρΔτjk(t+1)

(8)

式中:τjk(t+1) 和τjk(t) 分别为更新前后网格j内第k个种群的信息素含量的强度值;ρ为信息素挥发系数;Δτjk(t+1)为网格j内信息素强度更新值,定义为:

(9)

(10)

(11)

式中:Q为信息素强度;Pkl为第k个种群的第l只蚂蚁在第t次搜索后所经过的网格内目标出现概率之和,代表了该条路径的适应值(搜索概率),搜索概率越大,增强值越大;λkl和πkl分别是第k个种群的第l只蚂蚁在第t次搜索后所经过的网格内第k个种群信息素的总量和其它种群信息素总量的均值,λkl/πkl代表该条路径和其它蚂蚁种群所搜索的路径的交叠程度,λkl/πkl越大,交叠越小,增强值越大。

5 仿真实验

5.1 仿真实验架构

结合本问题需要的模块,构建仿真系统需考虑的整体框架,其中包括无人机类、系统环境类、侦察船类3个重要组成部分,无人机类中集成多蚁群系统算法进行搜索路线的规划和寻优,如图5所示。

图5 仿真系统运行概念图

在仿真建模过程中,基于面向对象技术,设置无人机类、侦察船类以及战场环境类,每个类中包含各个模块的属性和功能,以最大程度地还原问题题意,如图6所示。

图6 系统架构图

其中无人机建模融入多蚁群系统寻路算法,设置2个不同类型的无人机类,分别模拟无人机U1和U2,不同无人机间路径存在互斥,侦察船类考虑其对概率图的影响,设置概率图的更新。环境系统类则对路线进行绘制,对搜索概率进行计算,并进行可视化展示。

5.2 仿真实验结果

由图7可得,U1无人机路径节点为1 080个,U2型无人机路径节点达到2 160个,由路径仿真图可知,符合本文假设的运动限制及下一时刻的运动方向为向前、左转和后退,4架无人机的轨迹满足不交叉的限制条件,且续航较短的无人机U2最终位置与起始位置距离小于620 km,达到要求。最终的搜索成功率达到89.4%。

图7 仿真实验结果

6 结束语

对于路径选择优化问题,首先对无人机与电子侦察船机动策略进行数学建模,根据无人机搜索情况,动态更新概率图,同时采取Markov Mento-Carlo仿真确定侦察船位置变化。而后通过多蚁群系统算法进行无交叉搜索寻优,确定多架无人机侦察路线。

对侦察阵位地图进行了离散化处理,假设侦察船在其活动范围内位置变化服从均匀分布,要求红方在3 h内规划航线,使得发现蓝方侦察船的概率最大,采用“多类型蚁群系统”算法对路径进行了寻优,同时考虑了多个无人机之间的路径堆叠问题,使多个无人机的搜索范围尽量不交叉,以此保证搜索到目标的概率更大。搜索过程中根据无人机的搜索情况,依据贝叶斯公式对概率图进行更新,并最终进行了仿真实验验证。

针对问题,本文首先假设侦察船在侦察阵位出现以后移动呈现均匀分布,借此更新初始概率图,并根据无人机的机动进行概率图的贝叶斯更新。同时提出了“多蚁群系统”算法,该算法引入了不同种群蚁群间的信息素抑制,既解决了路径堆叠的问题,扩大了搜索的范围,又能满足搜索目标的概率最大。最后进行仿真验证,最大搜索概率达到89.4%。