南航姜斌团队 | 基于联盟形成博弈的异构无人机集群任务分配算法
文摘
科技
2024-11-22 12:02
北京
![]()
![]()
文章下载
薛舒心, 马亚杰, 姜斌, 李文博, 刘成瑞. 基于联盟形成博弈的异构无人机集群分布式任务分配算法. 中国科学：信息科学, 2024, 54(11): 2657-2673, doi: 10.1360/SSI-2024-0167
![]()
无人机集群是航空、信息、电子、控制等多领域发展催生的新质作战力量，是各国竞相发展的前沿装备。而任务分配是决定无人机集群发展的关键技术，为集群成功执行任务提供有效支撑和重要保证，是实现高自主化、智能化的关键。因此，针对任务的不同需求和集群内无人机的性能差异进行高效任务分配是目前亟待解决的问题。![]()
图1 无人机集群执行任务示意图
为了解决以上问题，本文提出了基于联盟形成博弈的异构无人机集群任务分配方法，主要包含两个阶段，分别是聚类的预处理和分区内的任务分配。首先，针对资源的异构性，提出一种基于异构资源的改进K-medoids聚类算法，通过对无人机集群和任务进行聚类的预处理，降低原任务分配问题的规模和难度。其次，建立联盟形成博弈模型并提出基于联盟形成博弈的分布式任务分配算法。仿真结果表明所提方法能够实现较好的任务分配效果，并提高了任务分配的实时性。(1) 在K-medoids聚类算法的基础上加入关于异构资源数目均衡度的收敛条件以进行改进。(2) 建立了联盟形成博弈数学模型，将任务分配问题转化为联盟划分问题；通过证明本文联盟形成博弈模型为势博弈，证明了纳什均衡解的存在性并为算法的设计提供了理论基础。(3) 设计了基于联盟形成博弈的分布式任务分配算法，主要包含了最大加权匹配阶段和无人机转移联盟判断阶段，使得算法相比随机寻优更具有导向性，能够获得较好的分配效果并且提高任务分配的实时性。![]()
图2 任务分配示意图
本文提出的基于联盟形成博弈的分布式任务分配算法在100架无人机执行30个任务中的场景中进行验证。仿真包含两个阶段，首先验证提出的基于异构资源的改进K-medoids聚类算法的有效性，在简单场景中与普通K-medoids聚类算法进行对比与分析，可以看出利用改进后的算法类簇内资源数目更加均衡。进一步利用该算法对无人机集群和任务进行聚类分组，无人机集群聚类结果如图3所示。![]()
其次为了验证所提任务分配算法的有效性，设置在不同的无人机数量下(n∈{5,6,7,8,9,10,11}) 以及不同的无人机与任务的数量下 (m∈{1,2,3,4,5,6},n∈{3,6,9,10,12,14}) 与粒子群算法、遗传算法、枚举法比较算法的运行效果与运行时间，从而验证了所提算法的有效性和实时性。![]()
![]()
![]()
