复杂环境下的多无人机协同巡逻航路规划

李友松，乔福超

（1.东海舰队司令部，浙江宁波315122；2.海军航空工程学院研究生管理大队，山东烟台264001）

随着武器装备的革新和战场构成的日益复杂，无人机所担负的任务种类越来越多，其功能也日益综合。如今，集侦查打击能力于一体的无人作战飞机已逐渐投入应用，利用多架UCAV协同执行战场巡逻任务（包括侦查与打击任务）也受到了越来越多的关注。

目前，针对多UCAV 协同巡逻航路规划的研究取得了一些成果[1-4]。文献[1]设计了一种满足UCAV 机动限制和适应数据通讯延迟的协同路径决策算法，使用搜索回报函数引导UCAV对未知环境进行搜索，仿真结果表明该方法能够有效提高协同搜索的效率，但其仅以搜索效率为目标，而未对UCAV的空间分布进行优化。文献[2]提出了兼顾搜索效率和打击效率的多UCAV协同航路原则，使用搜索回报函数和加权平均距离，加强了对高关注度区域的巡逻力度，改善了UCAV 的空间分布。此外，一些穷举覆盖航路规划模型，如Zamboni搜索方法已经得到了发展应用，较好地保证了航路的最优性[3-4]，然而该方法缺乏灵活性，如在设计某地区的森林火情侦查路线时，不能对该区域的湖泊和其他无林带进行规避，在载油有限和时间紧张下，将影响到对其他更有价值区域的侦查活动。

本文在现有研究的基础上，采用文献[2]中的多UCAV 协同巡逻模型，对复杂环境下的多UCAV 协同巡逻进行了研究。

1 复杂环境下的协同巡逻

1.1 复杂环境

复杂环境是指目标空间分布不均，目标分布随时间不断变化，且存在一定的飞行障碍（如禁飞区）的环境。UCAV在复杂环境下的搜索航路应充分考虑目标出现概率、飞行器活动范围限制等因素，加大对目标出现概率高的区域的搜索力度，避开无价值区域，从而提高UCAV的搜索效率。为实现该目的，应对复杂环境进行区域划分。例如，为提高火情侦查飞机的工作效率，其搜索环境应根据植被易燃程度、林木稀疏程度、干燥程度等因素划分为关注程度不等的小区域；又如，UCAV 在争议海域执行巡逻任务时，应根据目标出现的频率和飞行限制将该海域划分为一般关注区、重点关注区、禁飞区等区域。

基于上述分析，考虑根据先验信息，将复杂环境划分为一般关注区域、重点关注区域、已知区域和禁飞区域。UCAV 主要针对未知区域展开搜索，并对重点未知区域给予更高的搜索频率。同时，UCAV 应当尽量避免对已知区域进行搜索，并完全避开禁飞区域。图1为某海区的区域划分示意图。

图1 某海区的区域划分示意图Fig.1 Schematic diagram of a sea area's division

1.2 协同巡逻

UCAV的协同巡逻是一种兼顾搜索和打击的作战形式。例如，在近海作战中，UCAV执行对水面目标的侦查和打击任务：当未发现目标时，UCAV在整个作战区域搜索目标；当发现目标并需对其进行打击时，UCAV 应能及时飞至交战地点并实施打击，作战完成后再转为执行搜索任务。

综上所述，UCAV 在复杂环境下的协同巡逻航路应当同时兼顾搜索效率和打击效率，即应满足以下原则：

1）搜索路径应覆盖尽量多的未知区域，并尽可能避开已知区域，完全避开禁飞区域。

2）根据未知区域的关注度，对关注度高的区域给予更高的搜索频率。

3）UCAV 的空间分布应利于打击尽量多的目标。即在巡逻过程中的多数时间里，UCAV 的空间分布能够使之较快地到达战场区域内的任意一点。此外，当战场环境中的区域具有不同的关注度时，UCAV 应对关注度高的区域具有更短的打击距离。

2 协同巡逻航路规划模型

2.1 环境模型

将作战区域以等距网格划分。每一网格(i,j)被赋予一变量V(i,j)以表示UCAV 对该网格的关注程度。V(i,j) 取值越大，则网格(i,j) 被关注的程度越高，若UCAV 对网格(i,j)内的目标完全不关心，则V(i,j)=0。此外，为使UCAV 能够对禁飞区实行完全的规避，可将禁飞区内网格的关注度设置为绝对值极大的负值。以图1 所示的区域划分为例，空间中各网格的关注度赋值为：

式（1）中：A为已知区域；B为重要未知区域；C为一般未知区域；D为禁飞区域；Negative_Value ＜0 ，High_Value ＞Low_Value ＞0。

2.2 UCAV运动模型

假定UCAV 以匀速运动，UCAV 的运动数学模型如下：

式（2）中：xt、yt为无人机在t时刻的坐标；v为无人机的飞行速度；v˙为加速度；ΔT为单位时间；θt为无人机在t时刻的航向角；θ˙t为无人机在t时刻相对t-ΔT时刻的航向角改变量；u为最大转弯角限制参数。

2.3 UCAV航路

将连续的时间离散为时间序列{t|t=k⋅ΔT,k=1,2,…}。以任务开始时刻为零时刻，以固定的时长ΔT为一个时间单位。第n架无人作战飞机Un(n=1,2,…,N)的航路可表示为向量：

式（3）中：xn、yn为UCAV 的起点坐标；θn,t为Un在t时刻所选择的航向，相邻2次转向的时间间隔为ΔT。

θmax为ΔT内UCAV 物理操纵性能所限制的最大转弯角[5]。UCAV的航路如图2所示。

图2 UCAV的航路Fig.2 Route of UCAV

2.4 搜索模型

UCAV 使用雷达对目标进行探测，其在某时刻的探测面积用雷达所覆盖的网格数表示。假设UCAV的雷达探测半径为2 个网格宽度，则一架UCAV 在某时刻能探测到12 个网格。令P(i,j,t)表示UCAV 在t时刻对网格(i,j)的覆盖情况，若在t时刻至少有一架UCAV 的雷达能覆盖到网格(i,j)，则P(i,j,t)=1。若此时所有UCAV 的雷达都无法覆盖到网格(i,j) ，则P(i,j,t)=0。如图3 所示，白色网格是被UCAV 雷达覆盖的区域，灰色网格为未被覆盖的区域。

令K(i,j,t)表示UCAV在t时刻对网格(i,j)内目标分布的不确定度，且满足K(i,j,t)∈[0,1]。K(i,j,t)值越大，表示UCAV 对该区域的不确定度越高，当K(i,j,t)=1时，表示UCAV在t时刻完全不知道网格(i,j)内的目标分布情况。在搜索过程中，若网格(i,j)在t时刻被UCAV 探测到，则其下一时刻的不确定度K(i,j,t+1)变为0；若(i,j)没被探测到，也根据该区域的关注度V(i,j)，其下一时刻的不确定度K(i,j,t+1)应当有适量的增加，即：

式中，Q＞0 为每ΔT时间网格(i,j)的不确定度的增量。

由式（4）可以看出，关注度越高的区域，其在单位时间内的不确定度的增量越高，由此便可以引导UCAV以更高的频率对其进行搜索。

以搜索回报值来描述巡逻航路的搜索效率。多架UCAV 在整个飞行过程中探测到的所有网格的不确定度的加和，即为该航路的搜索回报值为

2.5 加权平均距离

UCAV的空间分布应利于打击尽量多的目标。即在巡逻过程中的多数时间里，UCAV 的空间分布能够使之较快地到达战场区域内的任意一点。此外，当战场环境中的区域具有不同的关注度时，UCAV 应对关注度高的区域具有更短的打击距离。

图4为3架UCAV 在某一时刻的空间分布图。图4 a）中，UCAV在战场区域内分布得较为分散，对于需要UCAV 打击的点a、b、c、d，其与UCAV 之间的最短距离都比较短，尤其对于重点区域内的点d，其与UCAV之间的距离更短；在图4 b）中，UCAV分布得较为集中，当a点需要打击时，UCAV就无法及时赶到。

图4 某时刻无人机的空间分布Fig.4 Distribution of UCAV in a moment

以加权平均距离来描述巡逻航路的打击效率。令d(i,j,t,n)表示网格(i,j)在t时刻与无人作战飞机Un之间的距离，则表示网格(i,j)在t时刻与距其最近的UCAV之间的距离。令：

式（7）、（8）中：d(t)为t时刻所有网格与距其最近的UCAV 之间距离的加权总和，每一距离的权值为相应点的关注度；D值即为加权平均距离，D值越小，UCAV的打击效率越高。

2.6 目标函数

根据协同巡逻航路原则，航路应同时兼顾搜索效率和打击效率，即既具有较大的搜索回报值，又具有较小的加权平均距离。设计目标函数：

式中，α、β(α＜0,β＞0)是权重。因战场环境、任务性质、指挥员性格的差异，其权重还需要做适当的调整。

3 航路规划仿真

3.1 粒子群算法

粒子群优化算法将优化问题的每一个潜在解表示为搜索空间中的一个粒子，通过调整粒子的位置和移动速度实现问题的寻优[6-7]。

假设在一个D维的目标搜索空间中，有n个粒子组成一个群落X=(X1,X2,…,Xn)，其中第i个粒子表示为一个D维的向量Xi=(xi1,xi2,…,xiD)，代表第i个粒子在D维的搜索空间中的位置，亦代表问题的一个潜在解。根据目标函数即可计算出每个粒子位置Xi对应的适应度值。第i个粒子的速度为Vi=(vi1,vi2,…,viD)，其个体极值为Pi=(pi1,pi2,…,piD)，粒子群的群体极值为G=(g1,g2,…,gD)。在每次迭代过程中，粒子通过个体极值和群体极值更新自身的速度和位置，即

式（10）中：ω为惯性权重；k为当前迭代次数；Vi为粒子速度；c1和c2是非负常数，称为加速因子；r1和r2是分布于[0,1]区间的随机数。为防止粒子的盲目搜索，一般将粒子的位置和速度限制在一定的区间[-Xmax,Xmax]、[-Vmax,Vmax]。

利用粒子群算法解决一般优化问题的流程图如图5所示。

图5 粒子群算法流程Fig.5 Process of Particle swarm algorithm

3.2 仿真分析

使用粒子群算法对多UCAV 协同巡逻航路规划进行仿真。以单个粒子表示N架UCAV的航路，其粒子结构如图6所示。

图6 多UCAV航路的粒子结构Fig.6 Particle structure of multi UCAV route

其中，xi和yi分别为UCAVi的航路起点的网格坐标，θi,t为UCAVi在为t时刻的偏转角，且θi,t∈[1,M]，M为UCAV 偏转角的离散数量。与固定起点的N架UCAV 的航路相对应，其粒子的搜索空间是(T+1)×N维的空间。

仿真中，将战场环境设置为20×15的网格区域，并设置1 个重点未知区域、1 个已知区域和1 个禁飞区域，其关注度分别设为2、0、0；剩余未划分的区域为一般未知区域，其关注度设为1。3架UCAV从不同基地起飞开始执行巡逻任务，其起点坐标分别为（4,1），（8,1），（12,1），UCAV的最大拐弯角为90°，雷达探测半径为1个网格宽度，每单位时间ΔT前进距离也为1个网格宽度。粒子群算法的各参数取值为：加速因子c1和c2均设为2；r1和r2取[0,1]区间内的随机数；惯性权重ω随迭代次数的增加由0.9 线性变化至0.4，迭代次数设为1 000 次。

图7 的航路是多UCAV 分区域搜索的常规航路，是目前应用较为普遍的非协同搜索航路。在分区域搜索时，各UCAV 之间无协同，每架UCAV 在其搜索区域内按照最大搜索效率进行覆盖式搜索。图8是仿真得到的3 架UCAV 的协同巡逻航路，航路点为25。分别计算图7、图8 中2 种航路的搜索回报值、搜索覆盖率、加权平均距离，计算结果如图9所示。对比图9中协同巡逻航路与非协同航路的参数。虽然协同航路的搜索覆盖率（47%）不及非协同航路（51%），但在空间分布方面，协同航路的加权平均距离（3.01）远小于非协同巡逻航路的加权平均距离（3.78），因而前者具有更高的打击效率。协同航路的搜索回报值（9.67）高于非协同航路的搜索回报值（8.51），这是因为协同航路对关注度高的区域提高了搜索频率。

图7 25航路点的非协同搜索航路Fig.7 Non cooperative search route with 25 points

图8 25航路点的协同巡逻航路Fig.8 Cooperative patrol route with 25 points

图9 航路参数对比Fig.9 Comparison of route parameter

为说明协同巡逻航路规划算法所生成的航路具有更好的打击效率，将UCAV飞行距离设置为15个航路点，起点坐标分别设为（2,1），（2,10），（15,7），得到的航路如图10 所示。可以看出，从t=1 时刻到t=15 时刻，3架UCAV在同一时刻的空间分布都较为分散，与区域内多数网格点之间的距离较短，尤其对于重点区域内的网格点具有更短的距离，因而具有较好的打击效率。图11 是航路点为50 的协同巡逻航路，该航路基本覆盖了区域内所有点，且在重点区域内较为密集，在一般区域内较为稀疏，达到了预期的加强对高关注度区域的巡逻的目的。

图10 15个航路点的协同巡逻航路Fig.10 Cooperative patrol route with 15 points

图11 50个航路点的协同巡逻航路Fig.11 Cooperative patrol route with 50 points

4 结束语

多UCAV 在复杂环境下的协同巡逻航路规划算法通过对未知区域、已知区域、禁飞区域设置不同的关注度，并使用搜索回报函数和加权平均距离对UCAV进行引导，加强了对高关注度区域的巡逻力度，改善了UCAV 的空间分布，与文献[2]的结果相比，本文中UCAV完全避开了禁飞区，并减少了对已知区域的搜索。仿真结果显示，在上述20×15的网格内，1个重点未知区域、1 个已知区域和1 个禁飞区域，3 架UCAV 的条件下，协同航路的搜索回报值比非协同航路提高了13.6%，加权平均距离仅为非协同航路的79.6%。UCAV 的协同航路和空间分布既加强了对高关注度区域的巡逻力度，又利于对目标进行快速打击。因此，在复杂环境下，本文的多UCAV 协同巡逻航比一般非协同航路具有更好的搜索效率和打击效率。

[1] 吴文超，黄长强，宋磊.不确定环境下的多无人机协同搜索航路规划[J].兵工学报，2011，32（11）：1337-1342.

WU WENCHAO，HUANG CHANGQIANG，SONG LEI.Cooperative search and path planning of multi-unmanned air vevehicles in uncertain environment[J]. Acta Armamentarii，2011，32（11）：1337-1342.（in Chinese）

[2] 乔福超，王昌金.按关注度分布的多无人机协同巡逻航路规划[C]//海洋发展与指挥控制会议.烟台，2013：144-147.

QIAO FUCHAO，WANG CHANGJIN. Cooperative patrol and path planning of multi-UCAVs according to degree of concern[C]//Ocean Development and Command Control Cconference. Yantai，2013：144-147.（in Chinese）

[3] CHANDLER P，PACHTER M，RASMUSSEN S. Hierarchical control for autonomous teams[C]//Proceedings of AIAA Guidance，Navigation，and Control Conference and Exhibit. Montreal：American Institute of Aeronautics and Astronautics，2001：632-642.

[4] SVENNEBRING J，KOENIG S. Building terrain-covering ant robots：a feasibility study[J].Autonomous Robots，2004：16（3）：313-332.

[5] 黄长强，翁兴伟，王勇.多无人机协同作战技术[M].北京：国防工业出版社，2012：41-53.

HUANG CHANGQIANG，WENG XINGWEI，WANG YONG. Cooperative combat technology for multi-UAVS[M]. Beijing：National Defense Industry Press，2012：41-53.（in Chinese）

[6] 汲万峰，姜礼平，朱建冲.基于机动目标威胁和粒子群算法的航路规划[J].电光与控制，2010，17（11）：5-8.

JI WANFENG，JIANG LIPING，ZHU JIANCHONG.Route planning based on mobile threat and particle swarm optim ization[J]. Electronics Optics and Control，2010，17（11）：5-8.（in Chinese）

[7] 王磊，施荣华.基于粒子群算法的无人机航路规划与建模仿真[J].计算机仿真，2011，28（4）：74-77.

WANG LEI，SHI RONGHUA. Application of particle swan optimization algorithm to path planning of unmanned aerial vehicle[J]. Computer Simulation，2011，28（4）：74-77.（in Chinese）

[8] 丁伟锋，严建钢，叶文.不同作战任务条件下的UCAV航路规划问题建模[J].海军航空工程学院学报，2012，27（1）：115-119.

DING WEIFENG，YAN JIANGANG，YE WEN. Research on the UCAV path planning model in different combat mission condition[J]. Journal of Naval Aeronautical and Astronautical University，2012，27（1）：115-119.（in Chinese）

[9] CHOSET H.Coverage for robotics：a survey of recent results[J]. Annals of Mathematics and Artificial Intelligence，2001，31：113-126.

[10]刘钢，老松杨，侯绿林，等.知识引导的智能优化算法在航路规划中的应用[J].湖南大学学报，2013，40（1）：103-108.

LIU GANG，LAO SONGYANG，HOU LVLIN，et al.Application of knowledge-conducting intelligent optimization algorithms to path planning[J].Journal of Hunan University，2013，40（1）：103-108.（in Chinese）

[11]刘科，周继强，郭小和.基于改进粒子群算法的无人机路径规划研究[J].中北大学学报，2013，34（4）：441-447.

LIU KE，ZHOU JIQIANG，GUO XIAOHE. Path planning research for unmanned air vehicle based on improved particle swarm algorithm[J].Journal of North University of China，2013，34（4）：441-447.（in Chinese）

[12]杜继永，张凤鸣，毛红保，等.多UAV协同搜索的博弈论模型及快速求解方法[J].上海交通大学学报，2013，47（4）：667-673.

DU JIYONG，ZHANG FENGMING，MAO HONGBAO，et al. Game theory based Multi-UAV cooperative searching model and fast solution approach[J]. Journal of Shanghai Jiaotong University，2013，47（4）：667-673.（in Chinese）

[13]李帆，郝博，万聪梅，等.基于混合粒子群优化算法的多弹协同航迹规划[J].飞行力学，2013，31（1）：93-96.

LI FAN，HAO BO，WAN CONGMEI，et al.Multi-missile cooperative route planning based on hybrid particle swarm optimization[J]. Flight Dynamics，2013，31（1）：93-96.（in Chinese）