梁烽杨，杨毅钧，刘功龙，万 兵，高王升

（上海机电工程研究所，上海 201109）

0 引 言

无人机（unmanned aerial vehicle，UAV）是一种具备自主飞行和独立执行任务能力的新型作战平台，能够执行军事侦察、监视、搜索、通信中继等多项任务。复杂多变的战场环境使得单架无人机已无法适应作战需求，研究多无人机的协同任务规划是现代战争发展的必然要求。2018年3月，美空军研究实验室曾展示C-130 运输机空中投放无人机集束柱，释放大量无人机实施蜂群作战的构想。中航工业早在2016年9月就公布了蜂群无人机集群作战系统的宣传视频。通过无人机个体之间的信息交互协作，实现大规模群体的智能协同行为，能完成远超个体能力的复杂任务。

在执行协同侦察任务时，需要决策者根据无人机性能、所处基地、侦察目标等信息规划起飞点、飞行航迹等，使得多无人机协同侦察的整体效能最大，且代价最小。多无人机协同侦察任务问题实质上是一个多目标、多约束、强耦合的复杂多目标优化与决策问题，解决问题的关键是完成多无人机的航迹规划并形成调度策略。

1 协同侦察航迹规划分析

本文结合一个假定的多无人机系统协同侦察任务进行规划分析。

假定某无人机侦察单元现配属有P01～P07 共7个无人机基地，各基地均配备一定数量的侦察无人机（各基地具体坐标、配备的无人机数量见表1）。侦察无人机的巡航飞行速度为200 km/h，最长巡航时间为10 h，巡航飞行高度为1 500 m，最小转弯半径70 m。受燃料限制，无人机在飞行过程中应尽可能减少转弯、爬升、俯冲等机动动作。

表1 无人机基地情况Tab.1 UAV base situation

根据任务要求，需完成侦察的目标有A01～A10共10 个目标群（共68 个目标），每个目标群包含数量不等的地面目标，每个目标群均配属有雷达站，各目标群配属雷达对无人机的有效探测距离为70 km（目标以及各目标群配署雷达的坐标参数见表2）。

表2 目标群相关信息Tab.2 Target group information

研究侦察无人机最优航迹和调度策略，以保证侦察无人机滞留在目标群雷达有效探测范围内的时间总和最小。

2 协同侦察航迹模型建立与策略分析

将基地P01～P07的坐标数据和目标群A01～A10中68个目标及各配属雷达坐标数据输入Matlab，绘制出目标群、基地分布及目标群雷达探测范围示意图，如图1所示，其中圆内各点代表雷达，方框内各点代表无人机基地。

图1 目标群、基地分布及目标群雷达探测范围Fig.1 Target group，base distribution and target group radar detection range

根据任务要求，要降低侦察无人机被目标群雷达探测发现的风险，需确保无人机在雷达区域内滞留飞行时间最短。在进入和离开雷达有效探测范围时，不考虑高度改变等燃油消耗，只考虑拐弯引起的油耗增加。

由此可以提炼出建模的两大原则：

1）雷达不复进原则：无人机离开某区域雷达探测范围，不能以进入另一个区域雷达探测范围为前提条件，即无人机离开某关注雷达，还需同时离开所有不关注雷达。

2）半径方向最优化出入原则：在满足雷达不复进原则的基础上，无人机尽量沿半径方向进入和离开雷达探测范围，以缩短侦察时间。将雷达探测范围看成圆，即连续性的边缘，将目标看成离散性的散点，无人机出入雷达探测范围即在圆的边缘某位置进入和离开，此位置是连续的并且可任意取值。

上述问题属于复杂航迹规划问题，按照规划决策方法分类，航迹规划算法可分为最优式和启发式算法。其中，最优式算法包括数学规划和穷举法等；启发式算法则有神经网络算法、遗传算法和蚁群算法等。因启发式算法有快速而高效的计算能力，本文选用启发式算法。而模型中约束条件多，故以蚁群算法为基础进行建模计算。

蚁群算法是一种仿生物智能算法，用来寻找优化航迹。其模型的基础是：蚂蚁群体寻找食物的过程，它们总能找到一条从食物到巢穴之间的最短路径，并且能够随着环境变化而重新搜索到新的最短路径。该算法鲁棒性较强，且具有分布式特征，从而使其全局搜索能力较强。

以一架侦察无人机侦察一个目标群为模型原型，用基本蚁群算法进行目标群内各目标点间的航迹规划，并确定目标群的进入点和离开点以及出入航迹。用改进型的蚁群算法优化航迹，形成最佳调度策略。

基于蚁群算法的航迹规划基本流程如图2所示。

图2 蚁群算法基本流程Fig.2 The basic flow of ant colony algorithm

2.1 协同侦察航迹模型

从A01 目标群的10 个目标中选取某个目标（用

i

表示），下一个目标用

j

表示，找到一条经过每个目标一次且回到起点的最短路程的封闭航迹。其目标函数为

式中，

d

(

i

，

j

)表示目标

i

和

j

之间的距离。基本蚁群算法求解：假设将

m

架无人机随机地放置在10个目标上，初始时刻目标间每一条航迹上的信息素强度

τ

(0)相等，将无人机禁忌表（Tabu）中的第一个元素设为其初始目标，禁忌表用

T

(

k

=1，2，…，

m

)表示；在搜索过程中，无人机将根据目标间的距离

d

(

i

，

j

)和目标间的航迹上信息素强度决定下一个要侦察的目标；

p

为

t

时刻无人机

k

(

k

=1，2，…，

m

)由目标

i

到目标

j

的转换概率，即

随着时间的推移，以前遗留的信息素逐渐消失，用参数

ρ

表示信息素挥发度。由于目标群中目标数量较多，解得的航迹较多，因此相应的信息素也较多，影响算法的收敛速度。为了提高算法的全局搜索能力，统筹考虑收敛速度，信息素挥发度

ρ

取适当的较大值0.7。经过10 个时刻，无人机完成对10 个目标的1 次侦察，所有无人机的禁忌表都已填满。计算无人机

k

的航迹总长度

L

，找到最短航迹min

L

，记录此航迹并更改信息素，重复这一过程直至达到最大周游值。各目标之间航迹上的信息素量调整为

式中：Δ

τ

表示无人机从目标

i

侦察到目标

j

所形成航迹上的信息素累计之和；Δ

τ

表示在

t

到

t

+10 时刻间第

k

架无人机从目标

i

访问目标

j

所形成航迹上遗留的信息素数量，计算公式为

式中：

Q

为常数；

L

为无人机

k

所形成的航迹总长度。

根据基本蚁群算法原理进行求解，某无人机侦察A01目标群的求解结果如图3所示。

图3 某无人机侦察A01目标群的内部航迹Fig.3 Internal track of a UAV detecting A01 target group

以雷达不复进原则和半径方向最优化出入原则为建模基础，采用非封闭曲线、在圆边缘处自动确定进入点和离开点且存在约束的改进型蚁群算法建立数学模型，计算无人机进入（离开）的航迹。

首先依据基本蚁群算法得出图4（a）所示的某目标群内部航迹，然后断开任一航迹支路进行尝试，如图4（b）所示。找到断开支路的端点，该端点与圆心连线的延长线与圆周的交点和该端点所构成的直线就是最短进入（离开）航迹，如图4（c）所示。受下一个目标群雷达侦测的影响，无人机最短进入（离开）的航迹不能出现在雷达侦测范围圈上，所以需要以下一个目标群雷达侦测范围为约束条件，向最短进入（离开）点两边寻找符合要求的最近进入（离开）点，如图4（d）所示。最后得出断开此航迹支路的方案，找到无人机进入（离开）的相对最优航迹。

再尝试断开其他支路，以相同的方法找到相对最优航迹，最终通过路程距离对比，在所有支路断开方案中找出进入（离开）某一目标群的最优航迹。在图4中，蓝色为无人机航迹；绿色圆弧为可进入（离开）域，其受制于雷达探测重叠区域，算法程序尽量避免无人机进入雷达探测重叠区。

图4 航迹示意图Fig.4 Track diagram

2.2 调度策略

采用上述模型对侦察各个目标群的航迹规划进行分析可知：目标群A07、A10、A09 的航路相互连通，目标群A02 和A03 的航路相互连通。从多目标群雷达探测的重叠区域考虑，侦察目标群A02、A03、A04、A05、A09 是相对危险的；从侦察任务耗时考虑，侦察目标群A04、A02 是相对危险的。考虑缩短协同侦察任务时间、节省燃料，对某个目标群的侦察任务选择由离其雷达探测区最近的无人机基地承担。

根据上述分析制定侦察无人机调度方案：安排1架侦察无人机完成目标群A07、A10的侦察任务（两者所需总时间相对来说较短）；安排1架侦察无人机完成目标群A02、A03 的侦察任务；在进入（离开）区域内，通过略微改变侦察目标群A08 的进入（离开）点，使目标群A08、A09 的侦察航迹连通，安排1 架侦察无人机完成此侦察任务；对目标群A01、A04、A05、A06 各安排1 架侦察无人机，另备1 架侦察无人机作为应急替补，总共使用7 架侦察无人机一次性完成对所有目标群的侦察任务。

3 模型优化

分析上述模型可知：所规划的航迹路程远远小于侦察无人机的巡航极限，保证有宽裕的空间对此模型进行优化。因此，优化基本蚁群算法，以构建更高效的协同侦察模型。

用蚁群算法研究多维动态组合优化问题，若问题规模较小，一般可快速找到最优解，但随着问题规模的扩展，求解过程将变得越来越复杂。由于侦察目标数较多，且约束条件复杂，可考虑在蚁群算法中引入去交叉禁忌搜索策略，并对每代所计算的解进行局部优化，以加快蚁群算法的收敛速度。

3.1 判定交叉

针对基本蚁群算法的求解，首先应判断交叉航迹的存在性。判定交叉的规则如下：在一般情况下，若两条航迹不交叉，即两条航迹没有公共点，则其中一条航迹的两端点必然处在另一条航迹的同一侧，即可以在两条航迹之间划一条直线，使两条航迹分别位于直线的两边，其中任意一条航迹与直线没有任何交点。

设交叉航迹的 4 个端点的坐标为

A

(

x

，

y

)，

B

(

x

，

y

)，

C

(

x

，

y

)，

D

(

x

，

y

)，则两条航迹的直线方程分别为

3.2 取消交叉

以交叉航迹的4 个端点（

A

、

B

、

C

、

D

）的航迹规划为例，假设在某次迭代过程中蚂蚁从

A

点出发到达

C

点后禁忌列表如图5（a）所示，航迹如图6（a）所示，蚂蚁要选择的下一点是

D

点，航迹用虚线表示。经改进算法判断，此时航迹

CD

与

AB

相交，判定为交叉。下一步，重置禁忌列表来取消交叉，重置后禁忌列表如图5（b）所示，航迹如图6（b）所示。重置的规则是：假设当前航迹和前面禁忌列表中的某条航迹相交，则在禁忌列表中将当前航迹的起始点和相交航迹的结束点位置互换。如上例中当前航迹为

CD

，相交航迹为

AB

，在禁忌列表中将当前航迹起始点

C

和相交航迹的结束点

B

交换位置，如图5（b）所示。

图5 禁忌列表Fig.5 The Tabu list

图6 禁忌列表对应航迹Fig.6 The track of Tabu list

3.3 求解结果

由于目标群雷达探测区重叠的关系，侦察A09、A04、A07、A02 目标群区域应考虑延迟起飞的情况。而有些侦察无人机存在转移侦察目标群的情况，其时间可以相互抵消来避免延迟起飞。由此可知，只需要延迟起飞侦察A04 目标群的侦察无人机即可。避免延迟起飞可以减少侦察无人机执行侦察任务的总时间，从而降低侦察无人机滞空危险。

根据优化算法求解最优侦察航迹，并形成高效调度安排，协同侦察最优调度方案如表3所示，最优侦察航迹如图7所示。

表3 协同侦察最优调度方案Tab.3 Optimal scheduling scheme of cooperative reconnaissance

图7 最优航迹Fig.7 Optimal track

4 结束语

本文对蚁群算法在多无人机系统协同侦察任务中的应用进行了研究，针对蚁群算法迭代计算收敛速度较慢的特点，以去交叉禁忌搜索策略为优化方式，高效解决了多无人机协同侦察多目标群的复杂航迹规划及调度安排问题，具有一定的实用性和可拓展性。