Autonomous Control of Unmanned Aerial Vehicle Swarms: Task Allocation Based on Coalition Formation Game
-
摘要: 针对复杂多约束条件下异构无人机集群系统的任务分配问题, 提出一种基于联盟形成博弈的分布式任务预分配和重分配方法. 考虑时效性、同时性等耦合约束条件, 引入准确的能耗模型建立任务分配模型, 利用联盟形成博弈将任务分配问题转化为联盟划分问题, 并设计一种无故障条件下的分布式任务预分配方法, 降低任务分配求解的复杂度, 同时提高最终解的平均质量; 进一步, 针对无人机故障问题, 准确分析健康无人机的运动模型, 合理划分重分配范围, 基于任务预分配结果设计重分配算法. 仿真结果表明了所提分布式任务预分配与重分配方法在不同场景下的实时性和有效性.Abstract: This paper presents a distributed task preallocation and reallocation method for heterogeneous UAV swarms system based on coalition formation game to solve the task allocation problem under complex and multi-constraint conditions. Considering multiple coupling constraints such as timeliness and synchronization, a task allocation model is established and an accurate energy consumption model is introduced to it. The task allocation problem is transformed into a coalition partitioning problem based on coalition formation game. Then a distributed task preallocation method under fault-free conditions with low complexity is designed, which can improve the average quality of the final solution. Furthermore, in response to the occurrence of UAV malfunctions, the motion model of healthy drones is accurately analyzed and the reallocation range is reasonably divided. Then a task reallocation algorithm is proposed based on the preallocation results. The simulation results prove the real-time performance and effectiveness of the proposed distributed task preallocation and reallocation method in different scenarios.
-
图 5 任务分配问题基本元素博弈流程图
Fig. 5 Flowchart of game of basic element in task allocation problem
图 7 联盟总收益统计值箱型图
Fig. 7 Box plots of statistical results of total revenue of coalitions
图 8 n = 12, m = 3时的算法典型收敛过程图
Fig. 8 Typical convergence process diagram of algorithm under n = 12, m = 3
图 9 健康情况下的预分配最优结果图
Fig. 9 Graph of optimal preallocation result under healthy conditions
图 10 不同无人机数量下算法收益与最大总收益之比
Fig. 10 The ratio of revenues to maximum total revenues under different numbers of UAVs
图 11 不同无人机数量下算法运行结果标准差
Fig. 11 Standard deviation of running results under different numbers of UAVs
图 12 不同无人机数量下算法平均运行时间及与枚举法运行时间之比
Fig. 12 The average running time and its ratio to the running time of the enumeration method
图 13 不同任务数量下算法收益与最大总收益之比
Fig. 13 The ratio of revenues to maximum total revenues under different numbers of tasks
图 14 $u_{12}$在$t=0\;{\mathrm{s}}$时发生故障后任务重分配示意图
Fig. 14 Graph of task reallocation after $u_{12}$ occurs fault at $t=0\;{\mathrm{s}}$
图 15 $u_{9}$在$t=8\;{\mathrm{s}}$时发生故障后任务重分配示意图
Fig. 15 Graph of task reallocation after $u_{9}$ occurs fault at $t=8\;{\mathrm{s}}$
图 16 $u_{7}$在$t=15\;{\mathrm{s}}$时发生故障后任务重分配示意图
Fig. 16 Graph of task reallocation after $u_{7}$ occurs fault at $t=15\;{\mathrm{s}}$
图 17 不同场景下任务重分配总收益图
Fig. 17 Total revenues of task reallocation in different scenarios
图 18 不同场景下任务重分配算法运行时间示意图
Fig. 18 Diagram of task reallocation running time in different scenarios
表 1 仿真参数符号和数值
Table 1 The notations and values of simulation parameters
符号 数值 符号 数值 $ P_{0} $ 158.76 W W 20 N $ P_{i} $ 88.63 W m 2.04 kg $ U_{tip} $ $ 120 \;{\mathrm{m/s}} $ $ S_{FP} $ $ 0.015\;1\;{\mathrm{m}}^{2} $ $ v_{0} $ 4.03 m/s $ f_{c} $ 2.4 GHz $ d_{0} $ 0.6 c $ 3\times 10^{8}\;{\mathrm{m/s}} $ $ \rho $ $ 1.225\;{\mathrm{kg/m}}^{3} $ $ \sigma^{2} $ −174 dBm/Hz s 0.05 $ \eta _{1} $ 3 dB A $ 0.503\;{\mathrm{m}}^{2} $ $ \eta _{2} $ 23 dB B 1 MHz 
下载: 导出CSV
表 2 任务仿真参数
Table 2 The simulation parameters of tasks
编号 $ T_{1} $ $ T_{2} $ $ T_{3} $ 位置 (798.4,848.3) (442.5,829.7) (585.9,501.6) 消耗型资源需求数量 (22,11,14,22) (19,13,17,27) (26,19,11,18) 数据量(Mbit) (30,90,100) (150,100,40) (60,100,50) 时间窗口 (24,55) (24,55) (24,55) 折扣系数 0.1 0.1 0.1 任务持续时间$ t_{T_{j}}^{con} $ 1.38 s 1.52 s 1.48 s 任务发射功率$ p_{T_{j}} $ 1 W 1 W 1 W
下载: 导出CSV
表 3 $m=3,\;n=12$时的任务预分配方案
Table 3 The optimal task preallocation solution under $m=3,\;n=12$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ $ T_{3} $ $ u_{2} $ $ T_{0} $ $ u_{6} $ $ T_{2} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ $ T_{2} $ $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ $ T_{3} $
下载: 导出CSV
表 4 $u_{12}$在$t=0\;{\mathrm{s}}$时发生故障后任务重分配方案
Table 4 The task reallocation solution after $u_{12}$ occurs fault at $t=0\;{\mathrm{s}}$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ $ T_{3} $ $ u_{2} $ $ T_{3} $ $ u_{6} $ $ T_{2} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ $ T_{2} $ $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ 故障, 退出
下载: 导出CSV
表 5 $u_{9}$在$t=8\;{\mathrm{s}}$时发生故障后任务重分配方案
Table 5 The task reallocation solution after $u_{9}$ occurs fault at $t=8\;{\mathrm{s}}$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ 故障, 退出 $ u_{2} $ $ T_{0} $ $ u_{6} $ $ T_{3} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ $ T_{2} $ $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ $ T_{3} $
下载: 导出CSV
表 6 $u_{7}$在$t=15\;{\mathrm{s}}$时发生故障后任务重分配方案
Table 6 The task reallocation solution after $u_{7}$ occurs fault at $t=15\;{\mathrm{s}}$
无人机 任务 无人机 任务 无人机 任务 $ u_{1} $ $ T_{0} $ $ u_{5} $ $ T_{1} $ $ u_{9} $ $ T_{3} $ $ u_{2} $ $ T_{0} $ $ u_{6} $ $ T_{2} $ $ u_{10} $ $ T_{3} $ $ u_{3} $ $ T_{1} $ $ u_{7} $ 故障, 退出 $ u_{11} $ $ T_{1} $ $ u_{4} $ $ T_{2} $ $ u_{8} $ $ T_{0} $ $ u_{12} $ $ T_{3} $
下载: 导出CSV
-
[1] Hu Z J, Gao X G, Wan K F, Wang Q L, Zhai Y W. Asynchronous curriculum experience replay: A deep reinforcement learning approach for UAV autonomous motion control in unknown dynamic environments. IEEE Transactions on Vehicular Technology, 2023, 72(11): 13985−14001 [2] Liu K, Zheng J. UAV trajectory planning with interference awareness in UAV-enabled time-constrained data collection systems. IEEE Transactions on Vehicular Technology, 2024, 73(2): 2799−2815 doi: 10.1109/TVT.2023.3320676 [3] Zeng Y, Xu X L, Jin S, Zhang R. Simultaneous navigation and radio mapping for cellular-connected UAV with deep reinforcement learning. IEEE Transactions on Wireless Communications, 2021, 20(7): 4205−4220 doi: 10.1109/TWC.2021.3056573 [4] He W J, Yao H P, Mai T L, Wang F, Guizani M. Three-stage stackelberg game enabled clustered federated learning in heterogeneous UAV swarms. IEEE Transactions on Vehicular Technology, 2023, 72(7): 9366−9380 doi: 10.1109/TVT.2023.3246636 [5] 武文亮, 周兴社, 沈博, 赵月. 集群机器人系统特性评价研究综述. 自动化学报, 2022, 48(5): 1153−1172Wu Wen-Liang, Zhou Xing-She, Shen Bo, Zhao Yue. A review of swarm robotic systems property evalu-ation research. Acta Automatica Sinica, 2022, 48(5): 1153−1172 [6] Zhang J, Cui Y N, Ren J. Dynamic mission planning algorithm for UAV formation in battlefield environment. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(4): 3750−3765 doi: 10.1109/TAES.2022.3231244 [7] 鞠锴, 冒泽慧, 姜斌, 马亚杰. 基于势博弈的异构多智能体系统任务分配和重分配. 自动化学报, 2022, 48(10): 2416−2428Ju Kai, Mao Ze-Hui, Jiang Bin, Ma Ya-Jie. Task allocation and reallocation for heterogeneous multiagent systems based on potential game. Acta Automatica Sinica, 2022, 48(10): 2416−2428 [8] 王峰, 黄子路, 韩孟臣, 邢立宁, 王凌. 基于KnCMPSO算法的异构无人机协同多任务分配. 自动化学报, 2023, 49(02): 399−414Wang Feng, Huang Zi-Lu, Han Meng-Chen, Xing Li-Ning, Wang Ling. A knee point based coevolution multi-objective particle swarm optimization algorithm for heterogeneous UAV cooperative multi-task allocation. Acta Automatica Sinica, 2023, 49(02): 399−414 [9] Xiong F, Zheng H, Ruan L, Wang H, Tang L J, Dong X, et al. Energy-saving data aggregation for multi-UAV system. IEEE Transactions on Vehicular Technology, 2020, 69(8): 9002−9016 doi: 10.1109/TVT.2020.2999374 [10] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222−241Du Yong-Hao, Xing Li-Ning, Cai Zhao-Quan. Survey on intelligent scheduling technologies for unmannedflying craft clusters. Acta Automatica Sinica, 2020, 46(2): 222−241 [11] Chen Z, Nian X H, Meng Q. Distributed optimization of multi-integrator agent systems with mixed neighbor interactions. Automatica, 2023, 157(3): 111245 [12] Zhang Z S, Liu H, Wu G H. A dynamic task scheduling method for multiple UAVs based on contract net protocol. Sensors, 2022, 22(12): 4486 doi: 10.3390/s22124486 [13] Garcia A, Hong M Y. Efficient rate allocation in wireless networks under incomplete information. IEEE Transactions on Automatic Control, 2016, 61(5): 1397−1402 doi: 10.1109/TAC.2015.2466836 [14] 吕晔, 周锐, 李兴, 刘志恒, 邸斌. 基于多轮次分布式拍卖的异构多任务分配算法. 北京航空航天大学学报, 2023, DOI: 10.13700/1001-5965.2023.0156Lyu Ye, Zhou Rui, Li Xing, Liu Zhi-Heng, Di Bin. Multi-task assignment algorithm based on multi-round distributed auction. Journal of Beijing University of Aeronautics and Astronautics, 2023, DOI: 10.13700/1001-5965.2023.0156 [15] Liu D, Dou L Q, Zhang R L, Zhang X Y, Zong Q. Multi-agent reinforcement learning-based coordinated dynamic task allocation for heterogenous UAVs. IEEE Transactions on Vehicular Technology, 2023, 72(4): 4372−4383 doi: 10.1109/TVT.2022.3228198 [16] Yuan R P, Dou J T, Li J T, Wang W, Jiang Y F. Multi-robot task allocation in e-commerce RMFS based on deep reinforcement learning. Mathematical Biosciences and Engineering, 2023, 20(2): 1903−1918 [17] Xu Y H, Jiang B, Yang H. Two-level game-based distributed optimal fault-tolerant control for nonlinear interconnected systems. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(11): 4892−4906 doi: 10.1109/TNNLS.2019.2958948 [18] Jie Y M, Guo C, Choo K-K R, Liu C Z, Li M C. Game-Theoretic Resource Allocation for Fog-Based Industrial Internet of Things Environment. IEEE Internet of Things Journal, 2020, 7(4): 3041−3052 doi: 10.1109/JIOT.2020.2964590 [19] Jang I, Shin H S, Tsourdos A. Anonymous hedonic game for task allocation in a large-scale multiple agent system. IEEE Transactions on Robotics, 2018, 34(6): 1534−1548 doi: 10.1109/TRO.2018.2858292 [20] Wang L X, Qiu T H, Pu Z Q, Yi J Q, Zhu J Y, Yuan W M. Hedonic coalition formation for distributed task allocation in heterogeneous multi-agent system. International Journal of Control Automation and Systems, 2024, 22(4): 1212−1224 doi: 10.1007/s12555-022-1182-5 [21] Chen J X, Wu Q H, Xu Y H, Qi N, Guan X, Zhang Y L, et al. Joint task assignment and spectrum allocation in heterogeneous UAV communication networks: a coalition formation game-theoretic approach. IEEE Transactions on Wireless Communications, 2021, 20(1): 440−452 doi: 10.1109/TWC.2020.3025316 [22] Zhang T X, Wang Y H, Ma Z J, Kong L J. Task assignment in UAV-enabled front jammer swarm: a coalition formation game approach. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(6): 9562−9575 doi: 10.1109/TAES.2023.3323441 [23] Qi N, Huang Z Q, Zhou F H, Shi Q J, Wu Q H, Xiao M. A task-driven sequential overlapping coalition formation game for resource allocation in heterogeneous UAV networks. IEEE Transactions on Mobile Computing, 2023, 22(8): 4439−4455 doi: 10.1109/TMC.2022.3165965 [24] Huo X, Zhang H, Huang C, Wang Z P, Yan H C. Task allocation with minimum requirements for multiple mobile robot systems: a game-theoretical approach. IEEE Transactions on Network Science and Engineering, 2024, 11(1): 1202−1213 doi: 10.1109/TNSE.2023.3321605 [25] Tang J, Chen X, Zhu X M, Zhu F. Dynamic reallocation model of multiple unmanned aerial vehicle tasks in emergent adjustment scenarios. IEEE Transactions on Aerospace and Electronic Systems, 2023, 59(2): 1139−1155 [26] 周文惠, 齐瑞云, 姜斌. 面向突发故障的分布式多无人机任务重规划方法. 控制与决策, 2023, 38(05): 1373−1385Zhou Wen-Hui, Qi Rui-Yun, Jiang Bin. Mission replanning method of distributed multiple unmanned aerial vehicles for pop-up faults. Control and Decision, 2023, 38(05): 1373−1385 [27] Wang G, Lv X, Cui L, Yan X. The methods of task pre-allocation and reallocation for multi-UAV cooperative reconnaissance mission. IET Collaborative Intelligent Manufacturing, 2023, 5(4): e12090 doi: 10.1049/cim2.12090 [28] Zeng Y, Xu J, Zhang R. Energy minimization for wireless communication with rotary-wing UAV. IEEE Transactions on Wireless Communications, 2019, 18(4): 2329−2345 doi: 10.1109/TWC.2019.2902559 [29] Yang Z H, Xu W, Shikh-Bahaei M. Energy efficient UAV communication with energy harvesting. IEEE Transactions on Vehicular Technology, 2020, 69(2): 1913−1927 doi: 10.1109/TVT.2019.2961993 [30] Mozaffari M, Saad W, Bennis M, Debbah M. Mobile unmanned aerial vehicles(UAVs) for energy-efficient internet of things communications. IEEE Transactions on Wireless Communications, 2017, 16(11): 7574−7589 doi: 10.1109/TWC.2017.2751045 [31] Zeng Y, Zhang R, Lim T J. Throughput maximization for UAV-enabled mobile relaying systems. IEEE Transactions on Communications, 2016, 64(12): 4983−4996 doi: 10.1109/TCOMM.2016.2611512 [32] Huang S J, Lei J L, Hong Y G. A linearly convergent distributed Nash equilibrium seeking algorithm for aggregative games. IEEE Transactions on Automatic Control, 2023, 68(3): 1753−1759 doi: 10.1109/TAC.2022.3154356 [33] Liu J, Ho D W C, Li L L. A generic algorithm framework for distributed optimization over the time-varying network with communication delays. IEEE Transactions on Automatic Control, 2024, 69(1): 371−378 doi: 10.1109/TAC.2023.3264784 -
计量
- 文章访问数: 90
- HTML全文浏览量: 49
- 被引次数: 0
