多无人机多目标协同侦察航迹规划算法

Journal of Chinese Inertial Technology Vol.27 No.3 Jun. 2019 文章编号：1005-6734(2019)03-0340-09 doi: 10.13695/j.cnki.12-1222/o3.2019.03.010

多无人机多目标协同侦察航迹规划算法

庞强伟，胡永江，李文广

（陆军工程大学 无人机工程系，石家庄 050003）

摘要：针对目前无人机集群对多目标进行协同侦察时，易重复侦察目标，进而导致侦察效率低的问题，提出了一种多无人机多目标协同侦察航迹规划算法。首先，优化了K-means聚类算法的评价标准，使目标集合的聚类结果更加稳定，同时也降低了目标被重复侦察的概率。然后，利用改进的离散粒子群算法求解侦察序列，来降低整体任务的时间代价。最后依据侦察序列生成各无人机任务航迹。仿真结果表明，该算法不仅能够有效避免目标被重复侦察，而且相较于基因算法和标准离散粒子群算法，在4架无人机观测30个目标的仿真条件下，将时间代价降低24%，其收敛速度较快，求解精度更高。 关 键 词：多无人机；多目标；协同；聚类；离散粒子群算法 中图分类号：V27

文献标志码：A

Path planning algorithm for multi-UAVs cooperative

reconnaissance on multiple targets

PANG Qiangwei, HU Yongjiang, LI Wenguang

(Department of Unmanned Aerial Vehicle Engineering, Army Engineering University, Shijiazhuang 050003, China)

Abstract: Aiming at the problem of low reconnaissance efficiency caused by repeatedly reconnoitring the target when multiple unmanned aerial vehicles (multi-UAVs) perform cooperative reconnaissance on multiple targets, a path planning algorithm for multi-UAVs cooperative reconnaissance multi-target is proposed. Firstly, the evaluation criteria of K-means clustering algorithm is optimized, which makes the clustering results of the target set more stable and also reduces the probability that the target is repeatedly reconnoitred. Then the improved discrete particle swarm optimization algorithm is used to solve the reconnaissance sequence, which reduces the time cost of the entire mission. Finally, the mission track of each UAV is generated based on the reconnaissance sequence. Simulation results show that the proposed algorithm can not only effectively avoid repeated reconnaissance on a target, but also has faster convergence speed and higher solution accuracy. Compared with the genetic algorithm and the standard discrete particle swarm optimization algorithm, the proposed algorithm reduces the time cost by 24% under the simulation condition that 4 UAVs observe 30 targets. Key words: multiple unmanned aerial vehicles; multi-target; cooperative; clustering; discrete particle swarm optimization

在现代战争中，无人机集群凭借其高效、可靠和适应性强等优点，广泛应用于执行各种复杂的军事任务[1]。航迹规划技术是保证无人机圆满完成任务的关键，决定了任务的合理分配以及各无人机的飞行轨迹[2]。目前对于在给定起点和终点的条件下，如何为无人机规划可规避各种障碍和威胁的飞行航迹[3-6]已有较为成熟的方法。但若要规划可高效侦察大量目标的航迹

收稿日期：2019-03-14；修回日期：2019-06-26

时，相关方法较少。

文献[7]提出了一种基于马尔科夫生成任务流的方法，可较快地规划出各无人机的任务航迹。但是该方法仅适用于目标数大于无人机数的情况，且由于马尔科夫的无后效性，过度简化了无人机彼此之间的联系，导致其最终结果可信度较低。文献[8]提出了将模拟退火算法与K-means聚类算法相结合的航迹规划算法，能够

基金项目：国家自然科学基金（51307183）；军内科研（ZS2015070132A12007）

作者简介：庞强伟（1995—），男，助教，从事多无人机协同任务规划技术研究。E-mail：pqw_AEU@163.com

联 系 人：胡永江（1977—），男，副教授，硕士生导师，从事无人机目标识别研究。E-mail: huyongjiang_jxxy@163.com

第3期 庞强伟等：多无人机多目标协同侦察航迹规划算法 - 341 - 有效解决复杂约束下多无人机侦察多任务的航迹规划问题。但是该聚类方法的初始目标点为随机选取的，不同的初始点会导致不同的聚类结果，其聚类结果不稳定。文献[9]将多无人机多目标协同侦察问题视为多旅行商问题（Multi-Travelling salesman problem, MTSP），然后通过添加虚拟目标的方式，将MTSP转化为单旅行商问题（Travelling salesman problem, TSP），最终可为无人机规划出可飞航迹。但是该方法仅适用于目标规模较小的情况。文献[10]在目标聚类之后，将目标群内部的点目标侦察问题视为TSP

[11-13]

来解决，而目标群之

间视为车辆路径问题来解决。但是该方法较为复杂，运算量较大，算法运行效率低。

上述方法在一定程度上能够解决多无人机多目标协同侦察航迹规划问题，但仍存在以下不足：1）算法仅适应于目标规模较小的情况；2）当目标数量多且距离近时，易重复侦察，导致侦察效率低；3）聚类方法单一，且聚类结果随机性较大，稳定性较弱。

针对以上问题，本文提出了一种将改进K-means聚类方法与改进离散粒子群算法（Discrete Particle Swarm Optimization, DPSO）相结合的多无人机多目标协同侦察航迹规划算法。首先根据任务要求和无人机携带载荷的参数，求解出载荷的侦察半径，并以该侦察半径为阈值，结合提出的改进K-means聚类算法将小于该阈值的多个目标聚类为一个目标，从而简化问题规模。其次对DPSO的粒子编码方式进行了改进，并设计了最佳算子，来求解最佳时间代价下每架无人机对应的目标侦察序列。最后通过仿真实验验证了算法的有效性与收敛性。

1 问题模型

假设某无人机基地O有m架无人机，现需对n个目标进行快速协同侦察。在目标位置、无人机起始位置及其巡航速度已知的条件下，设计一种航迹规划算法，使得每个目标都被侦察，并尽可能的减少重复侦察，且整体时间代价最小。

为了简化问题，可做出以下合理假设： 1）无人机的载荷探测区域为圆形；

2）目标位于无人机探测区域内，即目标被侦察； 3）所有目标优先级一样，目标的侦察序列只与时间代价有关。

记UAV=UAV1,UAV2,,UAVm为待执行侦察

任务的无人机集合，T={T1,T2,,Tn}为待被侦察的目

标集合。UAVji表示UAVi侦察到Tj，1表示侦察，0表示未侦察；xj表示从上一目标飞到Tj的距离；UAVi待侦察的目标集合为TAi，其数目为Ni，无人机速度为

Vi。视每架无人机UAVi(i1,2,,m)为一个旅行商，

将多无人机协同目标侦察问题转化为MTSP，然后再将其转化为TSP进行求解。则多无人机多目标协同侦察航迹规划模型可描述为：

目标函数：

minnmaxxjUAVji,i1,2,,m. (1)

j1Vi约束条件：

nUAVjiNi,i1,2,,m. (2)

j1mNin. (3)

i1T=TA1,TA2,,TAm. (4)

mUAVji≤1,j1,2,,n. (5)

i1式(1)表示以整体任务时间代价最小为目标函数，式(2)表示UAVi侦察的目标数量为Ni，式(3)和式(4)表示所有的目标均被无人机携带的载荷侦察，式(5)表示每个目标至多被侦察一次。

2 算法步骤

多无人机多目标协同侦察航迹规划算法步骤如图1所示。

输入目标、载荷参数、任务高度目标聚类粒子编码计算适应度粒子群更新满足终否止条件？是改进DPSO输出每架无人机对应的目标的侦察序列及时间

图1 算法步骤图

Fig.1 Flowchart of the algorithm

步骤①：目标聚类。根据任务高度以及载荷参数求解无人机载荷的侦察半径。使用改进的K-means聚类算

- 342 - 中国惯性技术学报 第27卷 法将距离小于该侦察半径的所有目标聚类为一个目标。

步骤②：粒子编码。对DPSO的粒子进行二进制编码，保证聚类后的所有目标至多被侦察一次，且所有的目标都被侦察到。

步骤③：计算适应度。基于进化的思想，设计了最佳算子来求解最佳适应度，确定所对应的目标侦察序列。

步骤④：粒子群更新。首先对适应度进行更新，保留最佳适应度及其对应的各无人机的目标侦察序列，然后更新粒子编码与粒子速度。

不断地重复步骤③和④，直到满足终止条件，输出最佳的各无人机侦察目标的序列及其对应的任务时间。

3 改进K-means聚类算法

在无人机进行侦察时，其携带的载荷具有一定的探测范围，如图2所示，任务高度为H，载荷探测角为，则无人机载荷的探测半径为R=Htan。

αHR 图2 载荷探测模型 Fig.2 Detection model of load

当目标数量较大且个别目标距离较近时，会使得个别目标被侦察多次。如图3所示，当侦察目标1时会同时侦察到目标2和目标3，当侦察目标2时会同时侦察到目标1和目标3，依次类推。如果无人机都对5个目标侦察一次，那么每个目标被侦察的次数如表1所示。

54132 图3 目标之间的位置关系

Fig.3 Positional relationship between targets

为使每个目标都被侦察且尽可能少地被重复侦

察，就必须对目标群进行聚类。

表1 目标被侦察次数

Tab.1 Number of times the target is reconnoitred 目标 1 2 3 4 5 次

3

3

4

3

2

K-means聚类算法以最小化平方误差刻画簇间样本紧密程度，然后设定聚类数K进行聚类，形成聚类簇。该算法操作简单快速，易于理解，是一种常用的聚类算法。但在算法初始时要设定最佳聚类数和初始点，使得聚类的结果不稳定，导致该方法的普适性较弱[14]。

针对以上缺点，若使用目标之间的距离和无人机载荷的探测半径的误差作为刻画目标的紧密程度依据，即将小于无人机载荷探测范围的多个目标聚类为一个目标，则不需要提前设置聚类数目和选取初始目标，聚类结果仅于载荷的探测范围有关，聚类结果唯一且稳定性较强。

具体步骤如下：

步骤①：计算第i(i1,2,,n)个目标到第j(j

1,2,,n)个目标的距离dij，即：

dij(Ti(x)Tj(x))2(Ti(y)Tj(y))2 (6)

(Ti(x),Ti(y))为目标Ti的横坐标与纵坐标。

步骤②：已知无人机载荷探测半径为R，依次判断当无人机位于目标Ti时，在其探测区域内的目标数

量，即：

D1,dijRij0,else,(j1,2,,n) (7)

nDiDij,(i1,2,,n) (8)

j1Dij表示当无人机在目标Ti时，是否能够探测到目标Tj，1表示是，0表示否；Di表示当无人机在目标Ti

时，能够探测到的目标数量。用集合表示为：

TiDi(Tj,)Ti,(i1,2,,n) (9)

即当无人机位于目标Ti时，侦察到的其他目标数

量为Di，(Tj,)Ti表示在Ti侦察范围类的目标为

(Tj,)，最后聚类结果为Ti。当Ti0时，表示无

人机在目标Ti时，侦察到的其他目标数为0，即可单独聚为1类。

那么图3中目标之间的位置关系可表示为：

12(2,3)1,22(1,3)2,33(1,2,4)3, 42(3,5)4,51(4)5第3期 庞强伟等：多无人机多目标协同侦察航迹规划算法 - 343 - 步骤③：选取Di最大的集合聚为一类。对于图3来说，该集合为33(1,2,4)3。

步骤④：在其他的集合中，删掉已经聚类的目标。对于图3来说，剩余的集合则为50。

步骤⑤：重复步骤③、④，直到所有的目标都被聚类，并整理步骤③、④的结果，作为最终的聚类结果。对于图3，最终可聚为两类：目标3和目标5，如图4所示。

目标聚类之后，无人机只需飞过目标3和目标5即可将所有目标侦察完毕，能够有效降低目标被重复侦察的概率，降低路径代价，进而提高侦察效率。

54132 图4 目标聚类结果图

Fig.4 Diagram of target point clustering results

4 改进离散粒子群算法

PSO凭借其算法的简洁性、参数少和易于实现等优点，深受广大学者的喜爱。该算法原理简单，即粒子群中的每个粒子都有一个被优化函数所决定的适应度，以及一个决定它们飞行方向和距离的速度，通过不断地更新自己的位置与速度，然后粒子以追随当前的最优粒子而在整个解的空间中寻优。但该算法仅适用于优化连续性问题，不能直接用于求解离散优化问题

[15-16]

。

为了解决在离散空间中的寻优问题，J.Kennedy和R.C.Eberhart在PSO的基础上提出了DPSO，拓展了PSO的应用范围[17]。在文献[18]中，标准DPSO的粒子编码全部由二进制组成，每个粒子的速度都由式(10)产生：

VtkwVtkc1r1(PtkXtk)c2r2(GtkXtk) (10) 其中，

Vtk、Ptk、Gtk和Xtk分别为粒子t在第k代的速度、个体极值、群体极值和二进制编码；w、c1和c2分别为惯性系数、认知系数和社会学习系数；r1和r2为随机数。

DPSO的粒子位置更新不同于PSO，其位置更新依赖于该粒子的速度，首先将该粒子的速度通过公式(11)函数映射到[0,1]区间，

Vsig(V1tktk)1exp(V (11)

tk)

Vtk表示粒子Xtk位置取1的概率，然后通过公式(12)来更新粒子Xtk位置的取值：

Xtk1,rand≤Vtk0,otherwise (12)

4.1 粒子编码

由于标准DPSO的初始粒子群位置随机产生，为了确保每个目标至多被一架无人机所侦察且所有的目标都被侦察，对标准DPSO的编码方式进行了优化。

粒子群中的每个粒子的尺度由无人机数量和目标数量决定，假定每个粒子为一个矩阵，其行和列的大小即为无人机的数量和目标数量，如图5所示，其中1表示将目标分配给无人机，0表示否。

123…n目标点010…0UAV1101…0UAV2000…0UAV3………………000…1UAVm

图5 粒子编码示意图

Fig.5 Schematic diagram of particle coding

每个粒子的编码步骤如下：

步骤①：生成一个等目标数量的随机0-1行阵，将该行阵视为将目标分配给第一架无人机的初始解；

步骤②：统计未分配目标的数量及位置，再生成一个与未分配目标数量相等的随机0-1行阵，将该行阵视为将目标分配给第二架无人机的初始解；

步骤③：重复步骤②，直到第n1架无人机。 步骤④：将剩下所有未分配目标的全部分给第n架无人机。

通过该编码方式，可将所有目标分配给无人机，同时还可以保证每个目标只被一架无人机侦察。 4.2 适应度求解

适应度函数为每架无人机遍历所有分配到的目标的时间代价，当无人机分配到目标数超过3个时，航迹可能会产生交叉，导致其适应度值不能达到最优，如图6所示。所以必须为无人机编排访问目标的顺序，来求解其最佳适应度值。

为了保证适应度函数能够快速朝着整体时间代价最小的方向进化，基于遗传进化的思想，设计了最佳算子，包括最佳交叉算子和最佳逆转算子，如图7所示。首先对分配到的目标进行整数编码，形成初始可行解的序列。然后对于最佳交叉算子，如图7(a)所示，随机选取两个最佳交叉点，如果在交换两个交叉点的之后的可行解能够使得适应度值减小，则将其保留，并更新无人机访问目标的序列。对于最佳逆转算子，

- 344 - 中国惯性技术学报 第27卷 321UAV 图6 侦察航迹示意图

Fig.6 Diagram of reconnaissance track

如图7(b)所示，随机选取两个最佳逆转点，如果在逆转两个逆转点之间的序列后的可行解能够使得适应度值减小，则将其保留，并更新无人机访问目标的序列。随机选取两个最佳交叉点初始可行解12345随机选取两个最佳交叉点678操作后可行解初始可行解152334425667788操作后可行解1(a) 5最佳交叉算子342

(a) Best crossover operator

(a) Best crossover operator(a) 最佳交叉算子67 8(a) 最佳交叉算子(a) Best crossover operator随机选取两个最佳逆转点初始可行解12345随机选取两个最佳逆转点678操作后可行解初始可行解1152433425667788操作后可行解1(b) 5最佳逆转算子432678(b) Best reversal operator

(b) (b) Best reversal operator(b) 最佳逆转算子最佳逆转算子 (b) Best reversal operator 图7 最佳算子 Fig.7 Best operator

通过上述操作，可以搜索到无人机访问目标的最佳序列，进而求得最佳适应度值。对于图6，其初始访问序列为1-2-3，通过最佳算子操作之后，最佳访问序列为1-3-2.

记其第t代的第k个个体的最佳适应度值为Ftk，则Ftkmax(ti),i1,2,,m. (13)

其中，ti为第i架无人机的最佳适应度值。 4.3 粒子群更新

首先，对粒子群的极值进行更新，其个体极值为Ptk=min(P1k,P2k,,P(t1)k,Ftk) (14)

群体极值为

Gtkmin(Pt1,Pt2,,Ptk) (15)

然后，通过式(10)~(12)，对各个粒子的速度以及其编码进行更新，使其在整个解的空间进行全局寻优。

不断重复4.2节和4.3节，直到满足终止条件，即可完成多无人机多目标协同侦察航迹规划。

4.4 收敛性分析

假设第t代第k个粒子的更新概率为Qtk，由式(12)

可知：

Qtkrand(0,1) (16)

由Qtk决定是否进行粒子位置更新，然后再进行速度的更新。

因此，粒子的每一步更新概率都大于0，更新过程

中构成Markov链，即任意解间依概率可达，且对其它粒子的更新不产生影响（独立同分布）。同时，该种群

序列是单调的。由上述理论分析及依概率收敛定理可知，该算法满足依概率1收敛到全局最优解的充要条件。

5 仿真验证

仿真实验平台为Inter(R) Core(TM) i5-5200U CPU，4GB内存，64位Win7操作系统的戴尔笔记本。编程工具为Matlab R2016a (64位)。 5.1 参数设置

假设某基地有4架无人机，无人机参数与坐标如表2所示。改进DPSO的参数设置如表3所示。现有30个重要目标需要侦察，其坐标如表4所示。

表2 无人机参数设置 Tab.2 UAV parameter setting

V/(km/h) R/m (x, y)/m UAV1 18 250 (350, 300) UAV2 27 250 (392, 220) UAV3 21.6 250 (450, 275) UAV4

32.4

250

(256, 121)

表3 改进DPSO参数设置

Tab.3 Improve DPSO parameter settings

实验次数 粒子数量 迭代次数 进化次数 进化个体 50

100

300

100

100

表4 目标参数设置

Tab.4 Target point parameter setting Ti (x, y)/m Ti (x, y)/m Ti (x, y)/m 1 (1150,1760) 6 (1030,2070) 11 (840,550) 2 (630,1660) 7 (1650,650) 12 (1170,2300)

3 (40,2090) 8 (1490,1630) 13 (970,1340) 4 (750,1100) 9 (790,2260) 14 (510,700) 5 (750,2030) 10 (710,1310) 15 (750,900) Ti

(x, y)/m Ti (x, y)/m Ti (x, y)/m 16 (1280,1200) 21 (830,1770) 26

(490,2130)

17 (230,590) 22

(490,500)

27 (1460,1420) 18 (460,860) 23 (1840,1240) 28 (1260,1910) 19 (1040,950) 24 (1260,1500) 29 (360,1980) 20

(590,1390)

25

(1280,790)

30

(110,900)

第3期 庞强伟等：多无人机多目标协同侦察航迹规划算法 - 345 - 目标位置和无人机位置如图8所示。 最佳算子。 首先，对目标进行聚类，可简化为20个目标，聚类结果如表6和图9所示。 最终四组实验的每架无人机的任务时间、整体任务时间和每架无人机的侦察序列如表7所示，对应的侦察航迹如图10(a)、图10(b)、图10(c)和图10(d)所示。

将上述实验结果分析如下： 1）由A1+A2与A1+B2（或A2+B1与B1+B2）的航迹规划结果对比可知，改进K-means目标聚类算法可大大减小问题规模，提高多无人机多目标协同侦察 效率。如图10(a)和10(b)所示，使用目标聚类的前后，(b) 目标聚类结果图其整体时间代价从14.5875 min减小到13.4684 min，

Fig.8 Location of four UAVs and the targets (a) Ddiagram of the location of UAV and the target无人机与目标位置示意图图8 (a) 四架无人机与目标位罝示意图

侦察效率提高7.7%。如图10(c)和10(d)所示，在共同使用了最佳算子的基础上，使用目标聚类的前后，其整体时间代价从12.8586 min减小到10.9971 min，侦察效率提高14.5%。 表6 目标聚类结果 Tab.6 Target point clustering result (b) Diagram of target clustering5.2 实验结果及分析 实验一：如表5所示，基于控制变量的准则，对提出的航迹规划算法进行对比实验，来验证提出方法的有效性。 表5 实验技术参数 Tab.5 Experimental technical parameters 1 2 A 未进行目标聚类 未使用最佳算子 B 改进K-means聚类 改进DPSO算法 聚类目标 4、10、15 14、18、22 8、24、27 2、21 5、9 26、29 聚类 结果 4 14 27 2 5 26 聚类 目标 3 6 7

聚类 结果 3 6 7

聚类 目标 16 17 19 23 25 30 聚类 结果 16 17 19 23 25 30 最佳算子，A1+B2表示对目标不进行目标聚类但使用最佳算子，A2+B1表示对目标进行目标聚类但不使用(c) A1+A2下的航迹规划结果图A1+A2表示对目标既不进行目标聚类也不使用

(c) Track planning result chart under A1+A2 (d) A1+B2下的航迹规划结果图1、28 1 20 20 (d) Track planning result chart under A1+B2 11 12 13 11 12 13 最佳算子，B1+B2表示对目标既进行目标聚类也使用表7 多无人机多目标协同侦察航迹时间代价表 Tab.7 Track time cost table of Multi-UAV multi-target coordinated reconnaissance 对应图 无人机 任务时间/min 整体时间/min UAV1 10(a) UAV2 UAV3 UAV4 UAV2 UAV3 UAV4 UAV1

10(c)

UAV2 UAV3 UAV4 UAV1

10(d)

UAV2 UAV3 UAV4

14.5875 13.3525 13.7645 11.1027

14.5875 侦察序列 1-22-11-18-13-27-7-1 2-17-15-19-25-16-24-6-29-3-20-2 3-30-4-21-1-23-3 (f) B1+B2下的航迹规划结果图1-30-13-27-1 (f) Track planning result chart under B1+B2 (e) A2+B1下的航迹规划结果图UAV1 12.1631 (e) Track planning result chart under A2+B1 4-14-10-2-5-9-26-12-28-8-4 2-17-11-4-2-5-12-23-2

3-19-16-1-6-3 4-14-20-26-3-25-7-4 1-17-15-19-16-23-11-1

10(b)

13.4638 11.3738 11.4973 12.8407 11.9019 12.4486 12.8586 9.3226 10.6241 10.494 10.9971

13.4684

12.8586

2-18-4-10-20-21-1-12-9-26-29-2

3-22-2-5-6-24-27-3 4-14-25-7-13-8-28-3-4 1-17-20-4-19-1 2-30-2-5-6-1-13-16-2 3-14-23-7-11-3 4-25-27-12-26-3-4

10.9971

- 346 - 中国惯性技术学报 第27卷 10.9971 min，侦察效率提高18.3%。 3）由A1+A2与B1+B2的航迹规划结果对比可知，同时使用目标聚类方法和最佳算子，可以大幅提高侦察效率。如图10(a)和10(d)，使用提出的多无人机多目标协同侦察航迹规划算法后，其整体时间代价从14.5875 min减小到10.9971 min，侦察效率提高24.6%。

4）为了进一步研究所提算法的有效性、实用性，在5.1节参数设置的基础上，假设出现了第四架无人机出现故障，不能执行侦察任务时的场景。 (b) 目标聚类结果图 图9 目标聚类结果图 (b) Diagram of target clustering Fig.9 Diagram of target clustering 在不使用本文算法的基础上，继续规划了3架无人机侦察点目标群时的航迹，如图11(a)所示。同时，为了形成对比，使用本文所提算法也进行了相应的航迹规划，如图11(b)所示。该场景下每架无人机的时间代价、整体任务的时间代价以及侦察序列如表8所示。

分析实验结果可知，该算法在该场景下有效地将任务的整体时间代价从15.3311 min降低到12.7376 min，侦察效率提高16.9%，且其平均时间代价也得到了有效的降低。同时可发现，无人机数量从三架增加到四架时，其侦察效率的提高从16.9%增加到24.6%，这也验证了示意图AV and the target2）由A1+A2与A2+B1（或A1+B2与B1+B2）的 航迹规划结果对比可知，使用最佳算子对无人机侦察的目标进行排序后，可以搜寻到最佳的侦察序列，提高侦察效率。如图10(a)和10(c)所示，在使用最佳算子的前后，其整体时间代价从14.5875min减小到 12.8586 min，侦察效率提高11.9%。如图10(b)和10(d)所示，在共同使用目标聚类方法的基础上，在使用最(a) 无人机与目标位置示意图(a) 无人机与目标位置示意图佳算子的前后，其整体时间代价从13.4684 min减小到 结果图under A1+A2 (b) 目标聚类结果图多无人机系统中，无人机数量越多，其侦察效率越高。 (b) 目标聚类结果图(a) Ddiagram of the location of UAV and the target(a) Ddiagram of the location of UAV and the target(b) Diagram of target clustering(b) Diagram of target clustering(d) A1+B2下的航迹规划结果图(a) 无人机与目标位置示意图(a) 无人机与目标位置示意图(b) 目标聚类结果图(b) 目标聚类结果图(d) Track planning result chart under A1+B2 (a) Ddiagram of the location of UAV and the target(a) Ddiagram of the location of UAV and the target(b) Diagram of target clustering(b) Diagram of target clustering (d) A1+B2下的航迹规划结果图(d) A1+B2下的航迹规划结果图 (b) A1+B2下的航迹规划结果图(c) Track planning result chart under A1+A2 (c) Track planning result chart under A1+A2 (d) Track planning result chart under A1+B2 (c) A1+A2下的航迹规划结果图(d) A1+B2下的航迹规划结果图(c) A1+A2下的航迹规划结果图(d) Track planning result chart under A1+B2 (d) A1+B2下的航迹规划结果图(b) Track planning result chart under A1+B2 (f) B1+B2下的航迹规划结果图(a) Track planning result chart under A1+A2 (c) Track planning result chart under A1+A2 (d) Track planning result chart under A1+B2 (c) Track planning result chart under A1+A2 (d) Track planning result chart under A1+B2 (f) Track planning result chart under B1+B2 (c) A1+A2下的航迹规划结果图(c) A1+A2下的航迹规划结果图(a) A1+A2下的航迹规划结果图

结果图under A2+B1 (c) Track planning result chart under A2+B1

(e) A2+B1下的航迹规划结果图(f) B1+B2下的航迹规划结果图(e) A2+B1下的航迹规划结果图(f) B1+B2下的航迹规划结果图(e) A2+B1下的航迹规划结果图(f) B1+B2下的航迹规划结果图 (e) A2+B1下的航迹规划结果图(f) B1+B2下的航迹规划结果图(d) B1+B2下的航迹规划结果图(c) A2+B1下的航迹规划结果图 (e) Track planning result chart under A2+B1 (f) Track planning result chart under B1+B2 (e) Track planning result chart under A2+B1 (f) Track planning result chart under B1+B2 (e) Track planning result chart under A2+B1 (f) Track planning result chart under B1+B2 (e) Track planning result chart under A2+B1 (f) Track planning result chart under B1+B2 (d) Track planning result chart under B1+B2

图10 四架无人机的仿真结果图

Fig.10 Diagram of simulation results of four UAVs

第3期 庞强伟等：多无人机多目标协同侦察航迹规划算法 表8 三架无人机航迹时间代价表 Tab.8 Track time cost table for three UAVs

对应图

无人机 UAV1 UAV2 UAV3 UAV1 UAV2 UAV3

任务时间/min 整体时间/min 14.0479 15.0911 15.3311 11.9221 12.7376 12.1955

12.7376

15.3311

侦察序列 1-22-4-13-19-2-21-1

2-17-14-11-25-7-23-8-28-12-9-5-26-20-10-2

3-18-15-16-27-24-1-6-29-3-30-3

1-1-17-15-10-1 2-14-4-13-9-6-7-8-5-2-2 3-12-19-18-3-11-20-16-3

- 347 -

11(a)

11(b)

综上所述，本文提出的多无人机多目标协同侦察航迹规划算法能够有效解决多无人机协同侦察多目标航迹规划问题，且规划出的航迹侦察效率较高，可行性较强。

机进行航迹规划。为了更好地进行对比，使用GA进行航迹规划时的参数设置，如表9所示。并同时记录了3种算法在求解迭代过程中每一代的最优解，形成了对比图，如图12所示。

表9 GA参数设置 Tab.9 GA parameter setting 实验次数 种群规模 进化次数 变异概率 交叉概率 50 100 300 0.1 0.8 (a) Track planning result under A1+A2

(a) Track planning result chart under A1+A2 (a) A1+A2下的航迹规划结果图 (a) A1+A2下的航迹规划结果图

(b) B1+B2下的航迹规划结果图 (b) Track planning result chart under B1+B2

图12 算法对比图

Fig.12 Diagram of algorithm comparison

分析图12可得以下结论：

1）改进的DPSO与GA相比，最佳任务时间具有较快的收敛性，且最终收敛于11min左右，要优于GA的最佳任务时间。

2）就平均任务时间来说，虽然GA在起初其收敛

(b) B1+B2下的航迹规划结果图 (b) B1+B2下的航迹规划结果图

(b) Track planning result chart under B1+B2 (b) Track planning result under B1+B2

规划结果图 rt under A1+A2 速度要大于改进DPSO，但是最终的收敛结果，改进DPSO要优于GA，这表明了改进的DPSO与GA相比，具有较好的寻优能力。

3）改进的DPSO与标准的DPSO相比，标准的DPSO在第77代时最佳任务时间和平均任务时间都变为0，这是因为标准的DPSO其编码方式随机，导致最终最佳任务时间和平均任务时间收敛于0，这表明了标准DPSO算法的不稳定性，同时也说了改进的DPSO算法的有效性。

图11 三架无人机仿真结果图 Fig.11 Simulation results of three UAVs

实验二：改进DPSO与标准DPSO和基因算法（Genetic Algorithm, GA）的收敛性对比。

为了验证改进DPSO的收敛性，在5.1节仿真参数的基础上，继续使用标准DPSO和GA为四架无人

- 348 - 中国惯性技术学报 第27卷 综上所述，改进的DPSO与标准DPSO和GA相比，收敛性较强，其收敛速度快，求解精度高。

6 结 论

针对侦察目标数量多且相距较近时，侦察效率低的问题，提出了相应的航迹规划算法，并通过仿真实验验证了算法的有效性，主要得到以下结论：1）对相距较近的目标，利用改进K-means聚类算法能够有效的将目标进行聚类，且结果稳定，有效减少了重复侦察的几率，提高了侦察效率；2）利用改进DPSO算法可快速搜索出最优的侦察序列，保证其整体时间代价最小，更有利于侦察任务的快速完成；3）改进DPSO相比于标准DPSO和GA，具有更好的寻优能力，且收敛速度更快，求解精度更高。 参考文献（References）：

[1] Erdelj M, Uk B, Konam D, et al. From the eye of the

storm: an IoT ecosystem made of sensors, smartphones and UAVs[J]. Sensors, 2018, 18(11): 3814-3841. [2] 赵明, 李涛, 苏小红, 等. 三维多无人机系统协同航迹

规划关键问题综述[J]. 智能计算与应用, 2016, 6(1): 31-35.

Zhao M, Li T, Su X, et al. A survey on key issues of cooperative task planning for 3D multi-UAVs system[J]. Intelligent Computer and Applications, 2016, 6(1): 31-35. [3] Yao P, Wang H, Su Z. Cooperative path planning with

applications to target tracking and obstacle avoidance for multi-UAVs[J]. Aerospace Science and Technology, 2016, 54, 10-22.

[4] Wang C, Mu D, Zhao F, et al. A parallel simulated

annealing method for the vehicle routing problem with simultaneous pickup-delivery and time window[J]. Com- puters & Industrial Engineering, 2015, 83(5): 111-122. [5] Cekmez U, Ozsiginan M, Sahingoz O K. Multi colony

ant optimization for UAV path planning with obstacle avoidance[C]//International Conference on Unmanned Air- craft Systems. 2016: 47-52.

[6] 李文广, 胡永江, 孙世宇, 等. 面向任务的无人机照相

侦察航迹规划算法[J]. 中国惯性技术学报, 2018, 26(4): 440-445.

Li W, Hu Y, Sun S, et al. Mission-oriented UAV camera reconnaissance path planning algorithm[J]. Journal of Chinese Inertial Technology, 2018, 26(4): 440-445. [7] Jeong B, Ha J, Choi H. MDP-based mission planning for

multi-UAV persistent surveillance[C]//14th International Conference on Control, Automation and Systems. Korea,

2014: 831-834.

[8] Yue X, Zhang W. UAV path planning based on K-means

algorithm and simulated annealing algorithm[C]//IEEE International Conference on 37th Chinese Control Confe- rence. 2017: 2290-2295.

[9] Sathyan A, Boone N. Comparison of approximate appro-

aches to solving the travelling salesman problem and its application to UAV swarming[J]. International Journal of Unmanned System Engineering, 2015, 3(1): 1-16. [10] Li J, Zhang S, Zheng Z, et al. Research on multi-UAV

loading multi-type sensors cooperative reconnaissance task planning based on genetic algorithm[C]//International Conference on Intelligent Computing Theories and Application. 2017: 485-500.

[11] Agatz N, Bouman P, Schmidt M. Optimization appro-

aches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52(4): 1-17.

[12] Saji Y, Riffi M E. A novel discrete bat algorithm for

solving the travelling salesman problem[J]. Neural Computing and Applications, 2016, 27(7): 1853-1866. [13] Tawhid M A, Savsani P. Discrete sine-cosine algorithm

(DSCA) with local search for solving traveling salesman problem[J]. Arabian Journal for Science and Engineering, 2019, 44(4): 3669-3679.

[14] 刘叶, 吴晟, 周海河, 等. 基于K-means聚类算法优化

方法的研究[J]. 信息技术, 2019, 1(16): 66-70.

Liu Y, Wu S, Zhou H, et al. Research on optimization method based on K-means clustering algorithm[J]. Infor- mation technology, 2019, 1(16): 66-70.

[15] 方群, 徐青. 基于改进粒子群算法的无人机三维航迹

规划[J]. 西北工业大学学报, 2017, 35(1): 66-73. Fang Q, Xu Q. 3D route planning for UAV based on improved PSO algorithm[J]. Journal of Northwestern Polytechnical University, 2017, 35(1): 66-73.

[16] 乔楠, 王立辉, 孙德胜, 等. 粒子群算法在惯性/地磁

组合导航航迹规划中的应用[J]. 中国惯性技术学报, 2018, 26(6): 787-791.

Qiao N, Wang L, Sun D, et al. Application of particle swarm optimization in track planning of inertial/ geo- magnetic integrated navigation[J]. Journal of Chinese Inertial Technology, 2018, 26(6): 787-791.

[17] Kennedy J, Eberhart R C. A discrete binary version of the

particle swarm algorithm[C]//IEEE International Confe- rence on Systems, Man, and Cybernetics. 1997.

[18] Strasser S, Goodman R, Sheppard J, et al. A new discrete

particle swarm optimization algorithm[C]//Proceedings of the 2016 on Genetic and Evolutionary Computation Con- ference. 2016: 53-60.