基于改进遗传算法的多无人机搜索航路规划

2024-04-19唐希浪蔡忠义

电光与控制 2024年4期

邓灏, 唐希浪, 蔡忠义, 于冲

(空军工程大学装备管理与无人机工程学院,西安 710000)

0 引言

近年来,无人机在军事领域的地位日益凸显。在任务侦察与敌情搜索方面,无人机具有机动性强、定位精度高等优势,可有效弥补航天侦察过境时间受限和技术侦察难以定位电磁静默目标的不足。相较于单架无人机,采用多架无人机与多种型号无人机对目标进行协同搜索可从不同方位对目标区域进行观测,减小因单架无人机性能有限产生的搜索限制,从而提高无人机在复杂战场环境下的整体作战能力,具有很大应用价值。

无人机对特定区域内的目标搜索本质上属于无人机路径规划问题。对于多无人机搜索而言,搜索过程中不仅要分析区域内目标活动热值分布特点,还需考虑各架无人机的性能约束与彼此间的信息共享,并依据协同搜索概率动态调整航行计划,进而规划出各架无人机的搜索路径。

在无人机路径规划方面,国内外学者从不同角度开展了大量研究。常用的无人机路径规划算法有粒子群算法[1]、A*算法[2]、遗传算法[3-4]等。林阳芷等[5]基于模拟退火算法与改进遗传算法建立了无人机对特定目标检测的航路规划模型,并引入修补算子来修复变化算子所产生的非法路径,但未考虑无人机机动性能与机载雷达探测频率等因素,影响了模型真实性;李楠等[6]对遗传算法的选择算子和变异算子进行改进,提高了算法收敛到最优解的速率和算法稳定性,但在一定程度上会导致种群多样性降低,进而诱发算法过早收敛;王启明等[7]提出一种改进遗传算法,利用贪心算子优化初始种群路线,进而提高算法挖掘能力,但随着种群适应度的提高,贪心算子会增加算法陷入局部最优解的风险,降低全局搜索能力; 文献[8]基于深度强化学习进行机器人网格路径规划,利用深度网络将观测信息应用于动作选择,并在简单的方格迷宫中得到实现和验证,但对于解决目标信息不确定的环境探测问题算法效益有待提高。

根据上述文献中算法策略的优缺点,本文结合贪婪算法思想,对变异操作进行了改进并提出贪婪变异策略与随机变异策略,有效解决了无人机在搜索后期对高热值地区重复搜索问题;同时设置策略选择阈值,做到依据种群适应度变化自适应选择变异策略,保证算法前期的全局搜索能力并提高后期的局部搜索能力;侦察搜索模型实现了无人机机动性能与机载雷达探测属性间的均衡考虑,增强了模型的泛化能力。

1 环境模型

环境模型起着将区域环境信息抽象转化成利于计算机处理的数据信息的作用[9],是无人机实现航路规划的前提和基础。基于无人机机载雷达探测半径与目标活动半径之间的关系,本文对目标区域采取栅格化建模方法以考虑二维情形下的无人机协同搜索任务。

根据目标活动的历史数据与各方情报综合制成了侦察区域目标活动热图,从蓝色到黄色表示目标活动频率递增。将侦察区域内的目标活动热图进行栅格化,如图1所示。考虑到无人机出发区域的大小对航路规划无明显影响,因此忽略出发区域大小。图1中点A(xA,yA)表示无人机出发处。

图1 侦察区域目标活动热图栅格化

栅格的尺寸大小由目标活动半径r0决定,可认为目标在半径为r0的圆内进行机动,所以正方形栅格边长为2r0,并依据先验情报计算出每个栅格所包括的2r0×2r0面积区域内目标活动概率之和作为栅格热度值q。而后对栅格进行编号,(λ,ε)表示第λ行、第ε列的栅格,并求出每个栅格的中心点坐标(xλ,yε),作为该栅格在侦察区域内的地理坐标,即

(1)

式中,L1,L2分别为无人机雷达侦察区域的长度和宽度。

2 协同搜索模型

根据典型无人机区域侦察的场景态势,无人机机动性能、机载雷达探测属性、区域重复探测率等均会对目标的探测概率和无人机航路的生成产生影响,进而影响最终的搜索效能。因此,本文以搜索概率为评价指标,建立无人机运动模型、状态更新模型和搜索效益模型进行分析。

2.1 无人机运动模型

为了简化分析,假设无人机都在同一高度上以固定的巡航速度飞行,通过调整航向角来改变自身航迹。将无人机运动过程进行离散化处理[9],并规定无人机任意时刻的航向为当前位置相邻8个航向中的一个,即无人机的航向决策集为H={0,1,2,3,4,5,6,7}。由于转弯角度的限制,并考虑到小转弯角度的偏航会节省无人机的能耗,无人机在下一时刻内只有3个可能航向,规定控制参量u∈{-1,0,1},-1,0,1分别表示在原航向基础上向左偏转45°、不偏转、向右偏转45°,航向变换与当前航向关系如图2所示。

图2 无人机航向变换示意图

无人机受控制参量作用,航向状态变化算式为

(2)

式中:hk为第k个状态更新周期的无人机航向状态;uk为第k个状态更新周期的控制参量。

2.2 状态更新周期模型

考虑到无人机实际航向的多样性以及扫描成像原理要求,定义状态更新周期,每经历一个状态更新周期无人机航向会进行一次调整。为使无人机沿任意航向均能在该周期内扫描覆盖整个栅格单位,当飞行距离包络单位栅格最宽处时可满足要求。状态更新周期算式为

(3)

式中:v为无人机巡航速度;t0为无人机机载雷达成像周期。

由几何关系分析可得,栅格中心点与无人机在第k个状态更新周期开始时的投影点(xk,yk)间距离的算式为

(4)

由于栅格热度值代表目标活动概率,因此将栅格中心坐标视为目标在该栅格中的坐标,即目标与无人机投影坐标的距离等价于栅格中心与无人机投影坐标的距离。

2.3 搜索效益模型

多无人机协同搜索的目的是在约束条件下尽可能大地提高搜索概率,搜索概率是无人机利用机载ISAR雷达沿航路对侦察区域成像检测得到的,无人机离目标越近,拍摄次数越多,则发现目标的概率越大。

定义从无人机的ISAR影像中发现目标的概率为

(5)

式中:d为无人机投影坐标与目标的距离;R为无人机的最大探测距离;α为无人机机载雷达的检测指数。

侦察过程中,多架无人机会存在对某一侦察区域多次成像的情况,假设无人机对侦察区域总计成像N次,成像距离分别是d1,d2,…,dN,其中只要有1幅ISAR图像检测出目标,则表示已发现目标。此时无人机基于这N幅影像发现目标的概率为

(6)

在编号为(λ,ε)的栅格中搜索到目标的充要条件是发现目标且目标位于该栅格内,定义在栅格(λ,ε)内搜索到目标的概率为

(7)

进一步可得到侦察区域内多架无人机协同搜索概率为

(8)

最终的搜索效益模型为

arg maxP

(9)

式中,Tlimit为无人机续航时间,约束条件分别表示无人机侦察搜索时间不能超过其续航时间以及无人机不能飞离侦察区域。

3 改进自适应遗传算法

遗传算法(Genetic Algorithm,GA)是根据生物种群优胜劣汰、适者生存的进化特点,模拟出的随机化搜索算法[10],交叉和变异操作是遗传算法中群体进化的主要操作。

自适应遗传算法(Adaptive GA,AGA)能够自发地根据适应度的变化对交叉概率和变异概率做出相应调整。即随着进化的进行,交叉和变异概率会随着种群适应度的增大而减小,以避免破坏当前种群的最优解,从而防止在进化后期出现退化现象。与传统遗传算法相比,其寻优精度大大提高,收敛速度明显加快。

本文提出加入贪婪算子的贪婪变异策略,并引入策略选择阈值sthreshold实现依据搜索概率变化对变异策略(贪婪变异与随机变异)的动态调整,使算法兼具优秀的前期全局搜索能力和后期局部搜索能力。

3.1 编码方式

传统的遗传算法编码方式有二进制编码、实数编码、自然数编码等。本文结合无人机航向与投影坐标之间的关系,采用类0-1编码,将控制参量-1、0、1作为基因,状态更新周期的个数k作为染色体的长度,即一条染色体是由k个控制参量组成的基因链。

3.2 解码方式

定义无人机的初始航行方向h0,初始投影坐标(x0,y0),每经过1个控制参量无人机航向变换1次,在此过程中无人机沿初始方向航行距离为T×v,到达下一个投影坐标(x1,y1),反复进行k次,共计得到k+1个无人机投影坐标。由此完成了控制参量-航行方向-投影坐标之间的转换,即由基因型到表现型的转换,如图3所示。

图3 编码及解码示意图

3.3 适应度计算

将多架无人机协同搜索概率作为种群适应度,搜索概率越大,表示种群优化结果越好,由前文知适应度函数为

(10)

对于不满足航行时间与侦察区域限制的个体,令其适应度为0,以满足搜索效益模型中的约束条件。

3.4 自适应过程

根据适应度和进化代数调节交叉概率和变异概率[11]分别表示为

(11)

(12)

式中:fmax为种群最大的适应度值;favg为当代种群平均适应度值;f为交叉双方中较大的适应度值;f′为发生变异个体的适应度值。k1、k2、k3、k4为常数,且满足k1

3.5 交叉操作

交叉是选中种群内两个个体作为父本,依据交叉概率pc判断是否发生染色体的部分交换从而产生新个体的过程。常见的交叉操作有单点交叉、多点交叉、均匀交叉[12]等。本文采用多点交叉,在交叉的染色体中随机设置多个交叉点,在交叉点处将两个父代基因进行交换并重新组合形成两个新的基因链。

3.6 基于贪婪算法改进的变异操作

变异是选中种群内某一个体作为父本,依据变异概率pm判断是否发生染色体上的某个或某些基因的突变从而产生新个体的过程。常见的变异操作有边界变异、基本位变异、非均匀变异等。其中,基本位变异是指在染色体基因链上随机指定的某一位或某几位基因做变异运算。本文采用基本位变异,并加入贪婪算法进行改进,同时依据类0-1编码特点,制定出贪婪变异策略与随机变异策略,如图4所示。

图4 变异策略示意图

引入变异概率阈值pm,threshold与策略选择阈值sthreshold,改进后的变异操作如图5所示。

图5 基于贪婪算法改进的变异操作

图5中,s1、s2、pm,threshold为常数且s2

由此,实现了以变异概率为桥梁,由协同搜索概率间接控制算法变异策略的效果,使算法能够依据协同搜索概率实时调整自身的全局搜索与局部搜索能力。

4 仿真验证

4.1 参数设置

本文仿真设置侦察区域大小为500 km×500 km,无人机种类为U1、U2型。出发地A配备U1型无人机,出发地B配备U2型无人机,无人机与机载雷达相关性能参数如表1所示。

表1 无人机与机载雷达性能参数

为检验本文所提算法的普适性,以出发地坐标和无人机数量为变量设置3种情形并进行仿真验证。不同情形下参数设置如表2所示。

表2 不同情形下的参数设置

分别采用文献[5]算法、文献[6]算法和本文改进遗传算法对模型进行求解。其中,模拟退火初始温度为100,退火参数为0.99,马尔可夫链长度为100,温度下限为0.001;遗传算法初始种群大小为800,迭代次数为150,本文算法选择策略为轮盘赌。

对于适应度高于种群平均适应度的个体,应赋以较低的交叉概率k1和变异概率k3以确保其能存优,本文中k1、k3分别取0.7、0.15;对于适应度低于种群平均适应度的个体,应以较高的交叉概率k2和变异概率k4诱导其发生交叉和变异,从而尽可能得到较优后代,本文中k2、k4分别取0.8、0.25。

策略选择参量s1、s2分别取0.7、0.5,以满足算法后期当种群自适应变异概率较小时,策略选择阈值sthreshold=s1较大,诱导算法以较大概率选择贪婪变异策略;反之,当种群自适应变异概率较大时,策略选择阈值sthreshold=s2较小,诱导算法以较大概率选择随机变异策略。

4.2 仿真结果

以情形2为例,多无人机搜索航迹如图6所示,其中,4条折线代表4架无人机的搜索路径,节点表示无人机在该点处航向发生变化。

图6 多无人机搜索航迹图

由图6可得,本文算法求解的航迹基本覆盖了热力图全局,同时也对中部高热值区域进行了多轮重复搜索;文献[5]算法虽然具有较优的局部搜索能力,但存在部分高热值区域未探测的情况,全局搜索能力欠佳;文献[6]算法具备较强的全局搜索能力,但对于部分高热值区域的重复搜索能力不及本文算法。

协同搜索概率迭代图见图7。

图7 协同搜索概率迭代图

采用本文算法时,多无人机对目标的协同搜索概率为85.1%,相较文献[5]算法和文献[6]算法的最终协同搜索概率78.7%和79.8%,分别提高了6.4个百分点和5.3个百分点。文献[6]算法虽然加速了算法收敛速率,但由于其改进选择操作中对优秀个体的复制行为以及改进变异操作所具备的特点,种群多样性不如本文算法,后期难以具备较优的局部搜索能力。

为避免一次实验带来的偶然性,针对3种情形采用3种算法分别进行20轮仿真实验,每种情形取协同搜索概率的平均值作为仿真结果,如表3所示。