基于网络节点聚类的多无人机动态目标分配

doi:10.16182/j.issn1004731x.joss.22-1297

摘要/Abstract

摘要：

为解决分布式的多无人机目标分配算法容易产生通信冗余，导致编队出现通信规模过大的问题，提出一种基于通信网络节点聚类的多无人机动态目标分配算法(clustered consensus-based bundle algorithm, CU-CBBA)。该算法引入了通信网络节点分组聚类策略，依据节点的度中心性、特征向量中心性、中介中心性等属性，建立了网络节点重要性排序模型，选取网络拓扑结构中的一组关键节点，按照最短路径原则完成网络拓扑节点聚类。仿真结果表明：与CBBA、ACBBA(asynchronous consensus-based bundle algorithm)、MCDGA(minimizing communications in decentralized greedy task allocation)算法相比，CU-CBBA算法的通信规模最小，收敛速度最快，迭代稳定性强，编队规模或目标数量的改变不会影响其有效性，与其他CBBA变种算法相比，该算法不需要智能体之间建立相对稳定的通信拓扑结构，通用性和稳定性较好，对复杂战场环境下的多机多目标分配具有部分借鉴意义。

关键词: 战场环境, 通信网络, 节点聚类, 多无人机, 目标分配

Abstract:

In order to solve the problem that the distributed multi-UAV target assignment algorithm is prone to communication redundancy, which leads to the large communication scale of formation, a multi-UAV dynamic target assignment algorithm (CU-CBBA) based on node clustering in communication network is proposed.The algorithm introduces the communication network node grouping clustering strategy. According to the node's degree centrality, feature vector centrality, intermediate centrality and other attributes, the network node importance ranking model is established. A group of key nodes in the network topology structure are selected and the network topology node clustering is completed according to the shortest path principle. The simulation results show that, compared with CBBA, ACBBA and MCDGA algorithms, CU-CBBA algorithm has the smallest communication scale, the fastest convergence speed, and strong iterative stability. The change of formation size or target number does not affect its effectiveness. Compared with the other CBBA variant algorithms, the algorithm does not need the establishment of relatively stable communication topology between agents and has good universality and stability, which has a certain reference significance for the multi-aircraft and multi-target allocation in complex battlefield environment.

Key words: battlefield environment, communication network, node clustering, multiple uavs, target allocation

中图分类号:

TP391.9

赵拓, 邓汉强, 高佳隆, 黄健. 基于网络节点聚类的多无人机动态目标分配[J]. 系统仿真学报, 2023, 35(4): 695-708.

Tuo Zhao, Hanqiang Deng, Jialong Gao, Jian Huang. Dynamic Target Assignment of Multiple Unmanned Aerial Vehicles Based on Clustering of Network Nodes[J]. Journal of System Simulation, 2023, 35(4): 695-708.

图/表 13

图1

图2

图3

表1

图4

图5

图6

图7

表2

图8

图9

图10

图11

参考文献 37

1	Dai Minghui, Luan Tom H, Zhou Su, et al. Joint Channel Allocation and Data Delivery for UAV-Assisted Cooperative Transportation Communications in Post-Disaster Networks[J]. IEEE Transactions on Intelligent Transportation Systems(S1524-9050), 2022, 23(9): 16676-16689.
2	Hosseini Maryam, Ghazizadeh Reza, Farhadi Hamed. Game Theory-Based Radio Resource Allocation in NOMA Vehicular Communication Networks Supported by UAV[J]. Physical Communication(S1874-4907), 2022, 52: 76-93.
3	Hong Libin, Wang Yue, Du Yichen, et al. UAV Search-and-Rescue Planning Using an Adaptive Memetic Algorithm[J]. Frontiers of Information Technology & Electronic Engineering(S2095-9184), 2021, 22(11): 1477-1491.
4	Xu Shufang, Li Linlin, Zhou Ziyun, et al. A Task Allocation Strategy of the UAV Swarm Based on Multi-Discrete Wolf Pack Algorithm[J]. Applied Sciences(S2076-3417), 2022, 12(1331): 1-21.
5	Wang Yao, Shi Yongkang, Liu Yunhui. Research on Improved Genetic Simulated Annealing Algorithm for Multi-UAV Cooperative Task Allocation[J]. Journal of Physics: Conference Series(S1742-6588), 2022, 2246(1): 1-9.
6	Wu Husheng, Li Hao, Xiao Renbin. A Blockchain Bee Colony Double Inhibition Labor Division Algorithm for Spatio-Temporal Coupling Task with Application to UAV Swarm Task Allocation[J]. Journal of Systems Engineering and Electronics(S1004-4132), 2021, 32(5): 1180-1199.
7	Yuan Xiaoxiang, Zhu Jie, Li Yixuan, et al. An Enhanced Genetic Algorithm for Unmanned Aerial Vehicle Logistics Scheduling[J]. IET Communications (Wiley-Blackwell)(S1751-8628), 2021, 15(10): 1402-1411.
8	Ribeiro Roberto G, Cota Luciano P, A M Euzébioet Thiago, et al. Unmanned-Aerial-Vehicle Routing Problem with Mobile Charging Stations for Assisting Search and Rescue Missions in Post Disaster Scenarios[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems(S2168-2216), 2021, 52(11): 6682-6696.
9	Song Byung Duk, Kyungsu Park, Kim Jonghoe. Persistent UAV Delivery Logistics: MILP Formulation and Efficient Heuristic[J]. Computers & Industrial Engineering(S0360-8352), 2018, 120: 418-428.
10	Albert A, Leira F S, Imsland L. UAV Path Planning Using MILP with Experiments[J]. Modeling, Identification and Control(S0332-7353), 2017, 38(1): 21-32.
11	李相民, 颜骥, 刘波, 等. 多智能体协同任务分配问题研究综述[J]. 计算机与数字工程, 2014, 42(12): 2443-2450.
	Li Xiangmin, Yan Ji, Liu Bo, et al. A Survey of Multi-Agents Cooperative Task Allocation Research[J]. Computer & Digital Engineering, 2014, 42(12): 2443-2450.
12	廖雨翔. 智能移动收球机器人的控制系统及路径规划研究[D]. 安徽: 中国科学技术大学, 2015.
	Liao Yuxiang. Research on Control System and Path Planning of Intelligent Ball Receiving Robot[D]. Anhui: University of Science and Technology China, 2015.
13	Zhu Daqi, Huang Huan, Yang Simon X. Dynamic Task Assignment and Path Planning of Multi-UAV System Based on an Improved Self-Organizing Map and Velocity Synthesis Method in Three-Dimensional Underwater Workspace(Article)[J]. IEEE Transactions on Cybernetics(S2168-2267), 2013, 43(2): 504-514.
14	Xie Tao, Guo Jiansheng, Zhang Xiaofeng, et al. Mathematical Problems in Engineering Improved CNP-Method-Based Local Real-Time Cooperative Task Allocation of Heterogeneous Multi-UAV in Communication-Constrained Environment[J]. Mathematical Problems in Engineering(S1024-123X), 2022, 1(3): 1-14.
15	Ye Fang, Chen Jie, Tian Yuan, et al. Cooperative Task Assignment of a Heterogeneous Multi-UAV System Using an Adaptive Genetic Algorithm[J]. Electronics(S2079-9292), 2020, 9(4): 1-20.
16	Yang Mi, Bi Wenhao, Zhang An, et al. A Distributed Task Reassignment Method in Dynamic Environment for Multi-UAV System[J]. Applied Intelligence(S0924-669X), 2022, 52(2): 1582-1601.
17	Zhan Cheng, Zeng Yong. Energy Minimization for Cellular-Connected UAV: From Optimization to Deep Reinforcement Learning[J]. IEEE Transactions on Wireless Communications(S1536-1276), 2022, 21(7): 5541-5555.
18	Liu Haoting, Ge Jianyue, Wang Yuan, et al. Multi-UAV Optimal Mission Assignment and Path Planning for Disaster Rescue Using Adaptive Genetic Algorithm and Improved Artificial Bee Colony Method[J]. Actuators(S2076-0825), 2022, 11(4): 1-30.
19	Peng Qiang, Wu Husheng, Li Na. Modeling and Solving the Dynamic Task Allocation Problem of Heterogeneous UAV Swarm in Unknown Environment[J]. Complexity(S1076-2787), 2022, 1(1): 1-14.
20	Rezende H B, Silva M. F, Santos M F, et al. Signal Estimation for UAV Control Loop Identification Using Artificial Immune Systems[C]//22nd International Conference on System Theory, Control and Computing (ICSTCC). Sinaia, Romania: IEEE, 2018: 579-584.
21	Zhang Jiandong, Chen Yuyang, Yang Qiming, et al. Dynamic Task Allocation of Multiple UAVs Based on Improved A-QCDPSO[J]. Electronics(S2079-9292), 2022, 11(7): 1028.
22	彭雅兰, 段海滨, 魏晨. 基于交替方向网络进化博弈的无人机集群任务分配[J]. 工程科学学报, 2022, 44(4): 792-800.
	Peng Yalan, Duan Haibin, Wei Chen. UAV Swarm Task Allocation Algorithm Based on the Alternating Direction Method of Multipliers Network Potential Game Theory[J]. Chinese Journal of Engineering, 2022, 44(4): 792-800.
23	王浩淼, 段海滨, 魏晨. 基于合作竞争公共物品博弈的无人机集群动态资源分配[J]. 中国科学(信息科学), 2022, 52(9): 1598-1609.
	Wang Haomiao, Duan Haibin, Wei Chen. Dynamic Resource Allocation of UAV Cluster Based on Cooperative Competition for Public Goods Game[J]. China Science(Information Science), 2022, 52(9): 1598-1609.
24	Bai Xiaoshan, Andres Fielbaum, Kronmü Maximilian, et al. Group-Based Distributed Auction Algorithms for Multi-Robot Task Assignment[J]. IEEE Transactions on Automation Science and Engineering(S1545-5955), 2022, 19(1): 1-12.
25	Choi H L, Brunet L, How J P. Consensus-Based Decentralized Auctions for Robust Task Allocation[J]. IEEE Transactions on Robotics(S1552-3098), 2009, 25(4): 912-926.
26	单永志, 黄得刚. 美军分布式作战概念发展的启示与建议[J]. 飞航导弹, 2020(11): 68-71.
	Shan Yongzhi, Huang Degang. Enlightenment and Suggestions on the Development of the Concept of Distributed Operations in the US Military[J]. Aerodynamic Missile Journal, 2020(11): 68-71.
27	Zhang Na, Zhu Xiaobing, Gou Yahong. The Role of Artificial Intelligence and Autonomous Systems in the Decision-Making Center of the US Mosaic War[C]//2020 International Conference on Intelligent Computing and Human-Computer Interaction(ICHCI). IEEE, 2020: 1-6.
28	Johnson Luke B, Ponda Sameera S, Choi Han Lim, et al. Asynchronous Decentralized Task Allocation for Dynamic Environments[C]//AIAA. 2011.
29	Kim Keum Seong, Kim Ho Yeon, Choi Han Lim. Minimizing Communications in Decentralized Greedy Task Allocation[J]. Journal of Aerospace Information Systems(S1542-9423), 2019, 16(8): 340-345.
30	Kim Keum Seong, Kim Ho Yeon, Choi Han Lim. A Bid-Based Grouping Method for Communication-Efficient Decentralized Multi-UAV Task Allocation[J]. International Journal of Aeronautical and Space Sciences(S2093-274X), 2019, 3(1): 1-13.
31	Darren Smith, Jodie Wetherall, Stephen Woodhead, et al. A Cluster-Based Approach to Consensus Based Distributed Task Allocation[C]//2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. Italy: IEEE, 2014: 428-431.
32	Fei Liguo, Deng Yong. A New Method to Identify Influential Nodes Based on Relative Entropy[J]. Chaos Solitons & Fractals(S0960-0779), 2017, 104(1): 257-267.
33	徐涛, 孟野. 踪迹聚类下组织实体的重要度排序方法[J]. 计算机应用, 2016, 36(5): 1284-1289.
	Xu Tao, Meng Ye. Importance Sorting Method of Organizational Enities Based on Trace Clustering[J]. Journal of Computer Applications, 2016, 36(5): 1284-1289.
34	Zhu Jingcheng, Wang Lunwen, Wu Tao. A Sorting Method of Node Based on Eigenvector and Closeness Centrality[J]. Journal of Physics: Conference Series(S1742-6588), 2021, 2031: 012043.
35	Wang Zhixiao, Chen Zhaotong, Zhao Ya. A Novel Local Maximum Potential Node Search Algorithm for Complex Network Community Detection Based on Topological Potential[J]. Journal of Computational Information Systems(S1553-9105), 2014, 10(5): 2091-2098.
36	Gao Fan, Huang Da. A Node Sorting Method for K2 Algorithm in Bayesian Network Structure Learning[C]//2020 IEEE International Conference on Artificial Intelligence and Computer Applications(ICAICA). Dalian: IEEE, 2020: 106-110.
37	任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13): 1175-1197.
	Ren Xiaolong, Linyuan Lü. Review of Ranking Nodes in Complex Networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.

典型通信网络结构	2个节点	3个节点	4个节点	5个节点
全连接	0，1	0，1，6	0，1，6，7	0，1，4，6，7
密集连接	0，1	0，1，6	0，1，6，7	0，1，4，6，7
星型连接	0，8	0，1，8	0，1，2，8	0，1，2，3，8
树型连接	1，9	1，9，8	1，9，8，0	1，9，8，0，2
环型连接	0，1	0，1，3	0，1，3，5	0，1，3，5，7
随机连接	1，4	0，1，4	0，1，4，2	0，1，4，2，3

算法	任务收益	是否存在任务重分配
CBBA	641.7	否
CU-CBBA	641.7	否
ACBBA	636.4	是
MCDGA	638.3	是

[1]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[2]	田广键, 代冀阳, 应进, 王宁. 基于自适应分段势场法的多无人机航迹规划[J]. 系统仿真学报, 2022, 34(11): 2368-2376.
[3]	王宁, 代冀阳, 应进, 李叶鼎, 鲁亮亮. 基于自适应扩展势场的多无人机航迹规划仿真[J]. 系统仿真学报, 2021, 33(9): 2147-2156.
[4]	李向阳, 张志利, 张宁, 桂毅, 李嘉. 局部信息联通的多无人机协同控制过程仿真研究[J]. 系统仿真学报, 2021, 33(7): 1501-1513.
[5]	华翔, 李宝华, 姚红娟, 王昭, 左嘉娴. 一种动态感知的连通恢复方法研究[J]. 系统仿真学报, 2021, 33(7): 1514-1525.
[6]	游雄, 田江鹏. 面向无人自主平台的战场地理环境模型研究[J]. 系统仿真学报, 2020, 32(9): 1645-1653.
[7]	朱杰, 游雄, 夏青. 基于认知的战场地理环境仿真对象数据模型[J]. 系统仿真学报, 2019, 31(6): 1070-1084.
[8]	欧峤, 贺筱媛, 陶九阳. 协同目标分配问题研究综述[J]. 系统仿真学报, 2019, 31(11): 2216-2227.
[9]	陈晖, 马亚平. 基于多级协同MOEA/D的联合火力打击目标分配方法[J]. 系统仿真学报, 2018, 30(8): 2942-2949.
[10]	朱林, 方胜良, 王劲松, 吴付祥. 面向体系作战的空间通信网络级联失效模型[J]. 系统仿真学报, 2018, 30(6): 2144-2152.
[11]	王涛, 王维平, 李小波, 井田. 一种多无人机集群持续侦察分层控制框架及关键算法[J]. 系统仿真学报, 2018, 30(4): 1221-1228.
[12]	曾艳阳, 裴庆庆, 康凤举. 自修正的三维视景组合优化方法[J]. 系统仿真学报, 2017, 29(9): 1873-1879.
[13]	张学毅, 谷聚辉, 周美琴. 一种支持QoS的电力通信组网建模与仿真[J]. 系统仿真学报, 2017, 29(7): 1605-1610.
[14]	王洋, 杨宏, 陈晓光, 丁凯. 深空通信LTP传递时延的理论建模及试验验证[J]. 系统仿真学报, 2017, 29(3): 479-486.
[15]	蒋秉川, 万刚, 范承啸, 夏青. 战场环境体素模型适应性分析及体要素分类方法研究[J]. 系统仿真学报, 2017, 29(2): 241-247.