一种基于蚁群算法的无人机协同任务规划优化算法

黄伟民+王亚刚

摘 要：随着无人机在军事领域的广泛应用，越来越多的无人机将应用在未来战场，因此无人机协同规划变得越来越重要。建立了多无人机协同任务分配模型，并研究了模型求解的有效算法。在蚁群算法的基础上提出针对密度较大目标区域的多无人机协同任务规划的优化方法，优化蚁群算法的搜索条件，降低了蚁群算法的时间和空间复杂度。

关键词：无人机；协同规划；蚁群算法；目标群密度

DOIDOI：10.11907/rjdk.171261

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2017）007-0131-03

0 引言

多基地多无人机协同侦查模型可以描述为：利用多种不同性能的无人机对多个空间分散的目标进行侦查，这些无人飞机分散在多个地理位置不同的基地上，需要快速制定无人侦查飞机的侦查任务计划以满足侦查要求和实际约束条件。在无人机迅速发展的同时，雷达技术也快速发展，因此一旦有侦察无人机进入防御方某一目标群配属雷达探测范围，防御方目标群的配属雷达均开机对空警戒和搜索目标，并会采取相应对策，包括发射导弹对无人机进行摧毁等，因此侦察无人机滞留防御方雷达探测范围内时间越长，被其摧毁的可能性就越大[1-2]。本文以侦察、监视任务为中心，以协同探测多基地目标为背景，在蚁群算法规划路线的基础上进一步优化线路，以此尽可能缩短无人机任务飞行时间和被雷达探测到的时间。

2 无人机侦察目标群聚类

为了最大程度上利用各无人机基地资源，首先要对目标群进行聚类。常用的聚类方法有K-means聚类算法、层次聚类算法、SOM聚类算法和FCM聚类算法[3]。本文采用层次分析法对目标群进行聚类， 通过聚类，可以规划出各无人机基地派出的无人机的探测目标群，在无人机数量和飞行参数限制条件下，这样做能最大限度地提高效率。

层次分析法的算法流程如图1所示。

3 基于改进蚁群算法的目标群路线规划

对目标群聚类后，要对每个类里的线路进行规划[4，6-7]，首先采用蚁群算法规划路线。在无人机协同任务规划中，蚁群算法能够很好地规划目标群之间的最优路径，但是没有考虑到目标群密度条件，针对密度较小的目标群，蚁群算法给出的是最优解，但是对于密度较大的目标群模型，蚁群算法给出的路径并不是最优解，很多在无人机探测半径之内的目标可以一次飞过，不需要飞到每个点的上空探测，尽可能在两侦查目标之间航行，能够侦查到载荷搜索范围内的目标。鉴于此，提出对蚁群算法的改进算法。首先对三目标距离模型进行建模，设无人机的探测半径为Kr，如图2所示。x为目标1到目标3的距离，y为目标2到目标3的距离，a为1，2目标之间的距离，则可得其模型如图2所示。

Step3：当m只蚁都完成了后续节点选择后，完成一次循环，各路径上信息素根据下式进行局部信息素更新：

其中，Δτkij 表示第k只蚂蚁留在路径（i，j）上的信息素，表示本次循环中路径（i，j）信息素的增量；ρ为信息素轨迹的衰减系数，通常设置ρ<1来避免路径上信息素的无限累计。

Step4：重复Step2和Step3，直到到达目标点。更新全局信息素Q，清空k的禁忌表tabuk。

Step5：计算蚂蚁所有路径的总长度，将新的路径与已知的最优路径相比较。若新路径更优，则替换已知的最优路径，存储当前最优路径的各个节点。

Step6：迭代次数Nstep加1，若Nstep>Maxstep，则停止寻找，输出最优路径，否则转到Step2继续寻找。

蚁群算法的时间和空间复杂度为[5]：

式中，n为所求问题规模，Nc 为算法的迭代次数，m为所求问题中的样本数量[11]。

改进后的蚁群算法时间和空间复杂度为：

4 实验结果分析

为验证算法的可行性和有效性，用Matlab对算法进行程序仿真[8-9]。图3为多无人机基地和目标群落之间的地理位置关系；图4为各目标群落内目标间距离关系图。对此情景下的多无人机协同任务进行规划。

使用MATLAB编写层次聚类算法[3]求出各目标群的聚类图，如图5所示。

实验参数为信息启发式因子α =1；期望启发式因子β=5；信息素残留因子ρ =0.5；蚁群的波数为20；每波蚂蚁的数量为30。

用MATLAB对蚁群算法[5]进行仿真求出侦查路径和航程，如表1所示；使用改进后的蚁群算法计算出侦查路径和航程，具体如表2所示。由表1、表2可得出，优化后的路线减少了飞行的节点数，从而减少了转弯次数，降低了能耗和路径长度，飞行距离减少了36.7%。

5 结语

本文主要研究解决了多无人机协同规划问题，采用层次聚类对目标群进行行分类，把分类目标群分配给各无人机基地。将目标群密度因素引入到蚁群算法中，极大降低了蚁群算法的时间和空间复杂度，加快了算法的收敛速度。用Matlab进行仿真实验，仿真结果表明，改进的蚁群算法能够更好地解决多无人机规划的实际问题，且随着目标群的密度变大和无人机探测半径的增加，其优化效果越明显。

参考文献：

[1] BAUSO D，GIARRE L，PESENTI R.Multiple UAV cooperative path planning via neuro-dynamic programming[C].Proceedings of the IEEE Conference on Decision and Control，2004：1087-1092.

[2] AIAA.Cooperative task assignment and path planning of multiple UAVs[C].2007 Conference and Exhibit，California，2007.

[3] WANG X Z，XIAO J B.Applied research of adshpso algorithm in multi-uav cooperative mission planning[J].Applied Mechanics& Materials，2013（375）：1106-1109.

[4] 鄧启波.多无人机协同任务规划技术研究[D].北京：北京理工大学，2014.

[5] 郭海洋.基于蜂群算法的无人机群协同飞行策略研究[D].哈尔滨：哈尔滨工程大学，2012.

[6] 韩攀.多无人机协同任务规划技术[D].南京：南京航空航天大学，2013.

[7] 程聪.无人机协同作战任务分配与攻击效能评估技术[D].南京：南京航空航天大学，2013.

[8] 王国强，罗贺，胡笑旋.无人机编队协同任务规划仿真系统研究[J].系统仿真学报，2014（8）：1856-1862.

[9] 吴静.多无人机协同航迹规划及效能评估方法研究[D].南昌：南昌航空大学，2012.

[10] 朱艳萍.多无人机协同攻击策略研究[D].南昌：南京航空航天大学，2012.endprint