基于联盟形成博弈的异构无人机集群分布式任务分配算法  

Distributed task allocation algorithm for heterogeneousunmanned aerial vehicle swarm based on coalition formationgame

作　　者：薛舒心 马亚杰[1,3] 姜斌 李文博[1,2] 刘成瑞 Shuxin XUE;Yajie MA;Bin JIANG;Wenbo LI;Chengrui LIU(College of Automation Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China;National Key Laboratory of Space Intelligent Control,Beijing Institute of Control Engineering,Beijing 100094,China;Engineering Research Center of Autonomous Control Technology of Aircraft,Ministry of Education,Nanjing 210016,China)

机构地区：[1]南京航空航天大学自动化学院,南京210016 [2]北京控制工程研究所空间智能控制技术全国重点实验室,北京100094 [3]飞行器自主控制技术教育部工程研究中心,南京210016

出　　处：《中国科学：信息科学》2024年第11期2657-2673,共17页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:62273177,62020106003,62233009);江苏省自然科学基金(批准号:BK20211566,BK20222012);高校学科创新引智基地(批准号:B20007);空间智能控制技术全国重点实验室开放基金(批准号:HTKJ2023KL502006);中央高校基本科研业务费(批准号:NI2024001)资助项目。

摘　　要：针对无人机集群携带异构资源以及任务的异构需求下的复杂任务分配优化求解问题,提出一种基于联盟形成博弈的分布式任务分配算法.首先针对任务分配问题规模较大的特点以及资源的异构性,提出一种基于异构资源的改进K-medoids聚类算法,通过对无人机集群和任务进行聚类的预处理,降低了任务分配的规模和难度.考虑任务需求、机载资源以及路径成本等条件建立任务分配模型,将原有任务分配问题转化为联盟划分问题,设计了一种基于联盟形成博弈的分布式任务分配算法进行求解.最后,将30个具有异构需求的任务分配给100架携带3种异构资源的无人机的仿真结果表明,所提算法能够实现较好的任务分配效果,同时极大提高任务分配的实时性,充分发挥集群效能.This paper presents a distributed allocation algorithm based on a coalition formation game to solve the complex task allocation problem when heterogeneous resources are carried by large-scale UAV swarm and tasks have heterogeneous requirements.Firstly,in response to the large scale of the cluster and the heterogeneity of resources,the K-medoids clustering method is improved by incorporating consideration of heterogeneous resources to reasonably reduce the scale of the original problem.Therefore,the allocation difficulty is reduced through preprocessing.Considering task requirements,resources carried by UAV,and path costs,a task allocation model is established and the original problem is transformed into a coalition partitioning problem.Then a distributed task allocation algorithm based on a coalition formation game is used to solve it.Finally,the simulation results of assigning 30 tasks with heterogeneous requirements to 100 unmanned aerial vehicles carrying 3 types of heterogeneous resources show that the proposed algorithm can improve the real-time performance of task allocation,reduce resource redundancy,and fully leverage cluster efficiency.

关 键 词：任务分配 异构无人机集群 异构资源 聚类算法 联盟形成博弈 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] V279[自动化与计算机技术—控制科学与工程]