在美军无人机Unmanned Aerial Vehicle (UAV)路线图2005-2030中指出, 在现代战争中信息收集任务是一项危险而复杂的任务, UAV能够代替人类在该领域发挥重要作用。大量的应用实践已经表明, UAV因其低廉的成本和良好的机动性与隐身性已经成为现代战场上广泛使用的一种侦察手段。UAV在任务侦察阶段能够代替有人机执行“危险、恶劣、枯燥”的任务^[1-2], 已被广泛应用于战场侦察、对地打击、城市反恐、地震救援、以及海上搜救等众多领域。UAV对地侦察是指通过UAV机载成像系统或其他侦察载荷, 及时获取指定区域情报信息的过程^[3]。如何在UAV执行侦察任务之前进行相应的任务规划, 提高UAV的任务执行效率已经成为一个热点问题。文献[4]重点解决了在考虑3D环境和禁飞区限制条件下, 如何获取到目标区域的最大侦察信息, 提出了相应的多UAV路径规划模型并给出了改进的遗传算法求解方案。文献[5]提出了一种基于新的“自适应”进化多目标优化方法的多基地多UAV协同侦察任务规划算法。相关文献都在不同程度上研究了无人机航路规划和侦察搜救问题, 并取得了一定的成果。由于在复杂的战场环境中、地震之后的灾情分析中、大面积海域的侦察搜救中, 都有众多的任务区需要UAV去执行信息收集任务, 如何进行有效的任务规划决策是当前研究的热点问题之一^[6-13]。但UAV的任务工作时间及载荷工作能力都是有限的, 通常难以完成对所有任务区的完全信息侦察任务, 在实际任务中通常我们也不需要对任务区执行完全侦察, 只要侦察到的情报信息满足一定要求即可。因此, 如何快速有效地完成对所有任务区的非完全信息遍历侦察是本文的研究重点。基于以上所述, 本文提出将一种改进的新兴仿生计算算法--布谷鸟搜索算法^[14-15]应用到UAV多任务区侦察决策问题中, 有效解决了对该类问题求解的快速性及有效性, 从而为工业应用提供了决策依据。

1 问题描述

在军事情报侦察、区域反恐、地震救援以及海上搜救等有关任务中, 经常需要单架UAV对有关区域中的多个关注任务点区域进行相关的信息侦察。在UAV自身性能、任务时间及侦察载荷的工作能力约束条件下, 如何最有效地规划各个关注任务点区域的载荷工作时间分配对侦察任务的完成效果有至关重要的影响。假定在任务场景中存在N个待侦察的关注任务区, 已知N个待侦察任务区的位置信息、区域信息和UAV携带的侦察载荷信息并需要满足最大侦察载荷工作时间限制。如图 1所示。

对任务区域的侦察收益主要通过UAV获取的侦察情报来体现, 而侦察情报的获取主要跟UAV在任务区域侦察的时间相关, 时间越长, 侦察所获得情报越多, 反之, 时间越短, 获取到的侦察情报也越少。

因此, 如何在约束条件下使UAV对所有任务区域的综合侦察信息确定性指标最大是我们要重点解决的问题。为了研究的方便做如下假设:UAV从基地出发且返回同一基地; 任务点的空间分布是对称的, 即任务α到任务j的路径距离与任务G(x_i⁰)到任务G(x_i^i-1)的路径距离相等; 侦察任务为预定的关注区域。UAV的任务飞行时间满足侦察载荷工作要求。

2 UAV多任务区侦察决策问题建模

为了分析问题方便, 做如下的变量定义:

n:任务场景中的待侦察任务区数量(含UAV起飞基地);

M:起飞基地与侦察任务区集合M={1, 2, 3…n}, 节点1表示起飞基地, 节点M\{1}表示待侦察任务区集合;

(x_i, y_i):第i个任务区中心的位置坐标, i∈M, (x₁=0, y₁=0);

S_i:第i个任务区域的面积, i∈M, 假定任务区为长方形区域;

c_i:第i个任务区的价值系数, i∈M, 其中c₁=0;

w: UAV携带侦察载荷的扫描宽度;

v: UAV的任务飞行速度, 设为固定值;

T: UAV携带侦察载荷的最大工作时间;

G_imin:对第i个任务区进行侦察必须达到的最小信息收益, i∈M, G_0min=0;

G_i(t):对第i个任务区进行t时间侦察获得的信息收益;

G_max:对所有任务区进行侦察获取的最大信息收益;

t_i:为第i个任务区分配的载荷侦察时间, i∈M, 其中t₁=0。

2.1 UAV侦察信息确定性指标模型

UAV对任务区侦察的目的是为了获得有效信息从而降低对任务区域的不确定性, 一般情况下, UAV对任务区进行侦察时都处于复杂的不确定性环境下, 由于UAV任务飞行时间及侦察载荷工作时间的限制, 通常难以保证对每个任务区域都能做到完全信息侦察。为了有效衡量侦察载荷在特定时间内对任务区侦察的信息收益, 本文提出了采用信息确定性指标来衡量特定时间内对任务区的侦察收益, 信息确定性指标主要跟UAV在任务区域的侦察时间、侦察载荷的工作能力等有关, 如下所示

(1)

(2)

式中:G₀为侦察开始前UAV对任务区域的信息确定性部分, 0≤G₀ < 1;G₁为侦察开始前UAV对任务区域的信息不确定性部分; β为侦察载荷对任务区域的侦察能力指数, 主要由侦察载荷的固有能力与待侦察任务区的性质决定。

本文中为了便于分析, 将载荷的侦察能力指数β定义如下

(3)

式中，s′为侦察载荷单位时间内的有效侦察面积; s为待侦察任务区的面积大小。

任务载荷在单位时间内的有效侦察面积s′表示为

(4)

式中:w为任务载荷对任务区的有效扫描宽度; v为UAV的任务飞行速度。

综上所述, 可把(3)式表示为下式

(5)

2.2 UAV多任务区侦察收益模型

在多任务区侦察环境下, 每一个任务区i都有相应的侦察价值系数, 根据任务区性质的不同分配不同的价值系数c_i。UAV多任务区总侦察收益表示UAV对所有任务区域进行侦察后的综合收益, 收益大小表示UAV侦察多个任务区域时, 获得的总信息量, 收益值越大, 表示UAV侦察获得的有效信息越多, 对所有侦察区域的综合信息确定性就越大。而每一个任务区i的侦察收益则主要由分配给该任务区的载荷侦察时间t_i确定, 多任务区域的侦察时间规划问题可以表示为如下的最优化问题(假定侦察开始前UAV对任务区域的信息确定性部分为0)

(6)

其中约束条件为

(7)

(8)

(9)

式中, 约束方程(8)为每个任务区需要满足的最小侦察收益约束, 约束方程(9)为UAV对所有任务区的任务侦察时间约束不能大于所携带侦察载荷的有效工作时间。这里规定了UAV对于每个任务区的侦察都应有一个最小侦察收益的限制, 即使得UAV侦察完该任务区后获得的情报信息不至于过少或者没有, 从而导致对该任务区的侦察情报信息失去实用价值。

3 CSA算法的改进策略

在UAV多任务区侦察决策问题中, 针对任务区的侦察时间规划问题属于连续时间约束的非线性规划问题, 由Yang等人提出来的仿生算法--布谷鸟搜索算法(cuckoo search algorithm, CSA)在解决此类问题中具有较高的计算性能, 但是标准的布谷鸟搜索算法完全依赖于随机搜索步长, 难以保证其快速收敛性, 因此, 本文提出一种基于侦察收益的自适应步长搜索策略来改进布谷鸟搜索算法(improved cuckoo search algorithm, ICSA)对所提出的规划问题进行求解。

3.1 布谷鸟搜索算法(CSA)

CSA算法是由Yang Xinshe和Suash Deb于2009年受到自然界中的寄生繁殖行为影响而提出的一种新兴仿生智能优化算法。主要包括最优选择、局部随机扰动、全局Lévy飞行进行随机选择3个过程要素^[15]。

1)  最优选择

通过保留最好的鸟窝或最优解来选择最优, 类似于遗传算法中的精英保留主义, 确保了搜索移动在局部最优解的领域范围内进行, 保证了最优解被保留到下一代而且不会有被逐出种群的危险。

2)  局部随机扰动

局部随机扰动过程可以描述为

(10)

式中, x_j^t和x_k^t是2个不同的随机序列; H(u)是海维赛德函数; ε是取自随机分布中的一个随机数; s是步长; p_a为宿主鸟发现布谷鸟蛋的概率。

3)  基于全局Lévy飞行的随机选择过程

全局随机搜索过程按Lévy飞行过程进行, 即

(11)

式中, x_i^(t+1)和x_i^(t)分表表示第t+1和第t代第i个鸟窝的位置, ⊕表示点对点乘法, α表示与问题规模有关的步长控制量, 通常情况下取为1, L(β)为Lévy分布的随机搜索路径, 它的移动过程服从Lévy分布, 如下所示

(12)

式中，u和v都服从正态分布, 即

, σ_v=1, Γ为标准的Gamma函数, 0 < β ≤2。

3.2 改进的布谷鸟搜索算法(ICSA)

经过大量的标准算例测试, 标准CSA算法都能较快获得问题的全局最优解, 但是标准算法中的部分参数在初始化步骤中被设定为固定值, 在特定问题的求解过程中容易使搜索过程中的局部寻优性能减弱, 从而导致全局收敛速度变慢。本文提出对算法中的α和β参数进行改进, 根据搜索过程的不同阶段来自适应的调整这2个参数的取值, 使得在早期迭代过程中取值足够大以增强解的多样性, 而在迭代过程的后期自适应减小以更好地进行局部搜索。

1)  基于侦察收益的自适应步长搜索因子

在标准CSA算法中α通常取常量1, 容易导致算法的性能和局部收敛速度变慢。因此引入如下的自适应步长搜索因子

(13)

式中，和分别代表初代和第(t-1)代的总侦察收益, α₀为初始参数。可以看出α随着侦察收益的增加而减小, 控制随机搜索的步长, 使得开始时足够大以增强解变量的多样性, 在后期减小以更好的局部调整解变量。

2)  基于侦察收益的自适应搜索比例因子

β主要决定了解的分布状况, 引入如下的自适应搜索比例因子

(14)

式中，β₀是初始参数, 和分别代表初代和第(t-1)代的总侦察收益, β随占察收益的增加而递减, β≤β₀。

通过对CSA算法中参数的改进, 可以有效地使个体或鸟蛋自适应的逐渐靠近最优解, 在初期执行更多的全局搜索而后期则转向更多的局部搜索。由于CSA算法参数少, 搜索完全依赖随机步长, 改进后的CSA算法相较于标准CSA算法具有更快的收敛速度。

3.3 ICSA的算法流程

采用改进后的CSA算法进行多任务区侦察规划求解的具体流程如下:

Step 1  初始化算法参数(种群数量n、宿主鸟发现外来鸟蛋的概率p_a、最大迭代次数、β₀);

Step 2  随机产生n个鸟窝;

Step 3  计算每个鸟窝的适应度F_i, 并记录鸟窝个体极值及相应最佳鸟窝;

Step 4  如果达到最大迭代次数, 转向Step 8, 否则算法继续;

Step 5  通过公式(12)、(13)得到新的解, 同时保留当前最优解, 记录此时的鸟窝极值;

Step 6  以概率p_a抛弃较差鸟窝, 并通过公式(11)在局部建立全新的鸟窝, 记录此时的鸟窝极值;

Step 7  迭代次数加1, 并转向Step 4;

Step 8  算法停止并输出最优解。

4 仿真实验

1)  仿真场景想定

以高空长航时侦察型无人机对任务场景中多个固定任务区进行不完全信息遍历侦察为例, 对本文所提出的算法进行仿真验证与分析。为便于说明问题, 设侦察前对任务区的信息完全未知, 待侦察任务区的面积已知且不随仿真过程而变化, UAV在二维平面内运动且不考虑地面威胁源的影响。任务场景为300 km×300 km的战场环境, UAV起飞基地的坐标为(0, 0)侦察载荷的最大任务工作时间为25 h, 对侦察区域的有效扫描宽度为0.3 km, UAV飞行速度220 km/h, 战场环境中的待侦察任务区为16个, 任务区有关属性信息设置如表 1所示。

仿真环境为Intel 2.53GHz主频, 2G内存的PC机, Windows 7操作系统, Matlab2010a软件。设定ICSA算法的最大迭代次数为500次, 种群数量为20, 宿主鸟发现鸟蛋的概率为0.25。

2)  仿真算列1

设定所有的待侦察任务区重要程度一样, 要求对每个任务区的侦察收益都不能小于0.25, 通过仿真计算, 完成全部任务区侦察的总信息收益为6.439 9, 对每个待侦察任务区的侦察时间分配及相应的侦察信息收益见表 2、图 2及图 3。

3)  仿真算列2

如果有T₁、T₉、T₁₅3个任务区需要重点侦察, 要求的最小侦察收益不能小于0.55, 其余任务区的侦察收益不能小于0.25。通过仿真计算, 此时完成全部任务区侦察的总信息收益为6.295 4, 对每个待侦察任务区的侦察时间分配及相应的侦察信息收益见表 3、图 7及图 8。

由仿真结果可知, 改进的CSA算法为各个任务区分配的侦察时间满足任务要求, 同时UAV对每个任务区的侦察收益都不小于各个任务区所要求的最小侦察收益。

为了测试ICSA算法的性能, 在上述仿真条件下分别采用了ICSA算法、标准CSA算法, 遗传算法进行了仿真对比分析, 3种算法的进化收敛曲线如图 6所示。

从仿真结果可以看出, ICSA算法为各个待侦察任务区分配的侦察时间满足约束要求, UAV对每个待侦察任务区的侦察收益都不小于预定的最小侦察收益约束, 同时最大限度的使用了侦察载荷的可用工作时间。从ICSA、CSA及GA 3种算法求解目标函数最优值的进化曲线中可以看出, 相对于标准CSA算法和GA算法, 改进的布谷鸟搜索算法具有收敛速度快的优点, 能够在较小的迭代次数下达到收敛。算法能够快速有效地给出最优的多任务区侦察任务决策方案。

5 结论

本文针对UAV多任务区域的侦察决策问题, 提出了任务区侦察信息确定性指标, 建立了多任务区侦察决策的数学模型, 进行了相应的仿真分析, 仿真结果表明, 该方法可以在UAV侦察载荷工作时间约束下获得对任务区域综合侦察收益最大化的决策方案。

由于单架UAV携带载荷侦察能力的局限以及战场环境与任务区域的复杂性, 使得单架UAV常常难以有效的对全部侦察任务区实施满意的侦察信息收集。因此, 在后续工作中, 将对异构型多UAV携带多种载荷对多任务区域的协同侦察问题展开进一步的研究。