UAV swarm task allocation algorithm based on the alternating direction method of multipliers network potential game theory
-
摘要: 大規模無人機集群相較于單架無人機，可承擔更為復雜的“1+1>2”的任務，其中無人機集群任務分配是一個關鍵性挑戰技術難題。針對無人機集群任務分配問題，本文提出了一種基于交替方向網絡進化博弈算法。首先，考慮無人機集群異類資源約束和執行能力因素，給出了無人機集群任務分配的數學公式描述，并基于網絡進化博弈構建了無人機集群任務分配博弈模型。其次，結合單架無人機的能力特性與任務集特征，利用交替方向策略求解單機局部最優執行效能。將無人機定義為博弈參與者，無人機集群任務分配問題轉化為求解網絡進化博弈納什均衡，每架無人機通過與鄰域內個體的信息交互來調整自身策略，可實現無人機集群任務分配全局任務收益的最大化。最后，通過仿真對比實驗和無人機集群三維態勢綜合驗證平臺實驗，驗證了本文所提出方法的可行性和有效性。Abstract: Compared with a single unmanned aerial vehicle (UAV), a large-scale UAV swarm can accomplish the unavailable, complex, and “1 + 1 > 2” tasks of traditional UAVs. To prevent the UAV swarm from falling into the dilemma of disorganized derailment and mission failure, higher requirements for the robustness and organizational scheduling capability of the UAV swarm were proposed. As one of the important components of the autonomous cooperative control technology of UAV swarms, task allocation refers to certain environmental situation information and UAV swarm status to maximize the overall efficiency of the swarm. To solve the task allocation problem of the UAV swarm, a UAV swarm task allocation algorithm based on the alternating direction method of multipliers (ADMM) network potential game theory was proposed. The ADMM is a typical algorithm that uses the idea of “divide and conquer.” The ADMM adopts the decomposition–coordination process, which coordinates the solutions of each subproblem step by step to determine the global optimum. In terms of problem modeling and algorithm design, the network potential game theory can solve the conflict and cooperation between multiple agents effectively. By combining the advantages of the ADMM and network potential game theory, UAV swarm task allocation can be divided into two parts: local and global benefits optimization. Firstly, considering the different resource constraints and execution capability factors of the UAV swarm, the task allocation problem was formulated as the problem of finding a minimum under inequality constraints, and the game model of the UAV swarm task allocation problem was constructed based on the network potential game theory. Based on the game model of UAV swarm task allocation, the equivalence of the optimum UAV swarm task allocation strategy and the Nash equilibrium solution of the evolutionary network was analyzed. Secondly, according to the UAV capability and task set characteristics, the local optimum execution efficiency of each UAV was determined using the ADMM. Moreover, each UAV was defined as a rational player, the local benefit maximization task combination of each UAV was used as the initial task allocation scheme, and the task allocation problem was transformed and solved by using the Nash equilibrium solution of the network potential game. Each UAV adjusts its strategy based on the information on the interaction between individuals in the neighborhood to maximize the global task benefits. Finally, the simulation experiments verified that the proposed UAV swarm task allocation algorithm can converge to the optimal solution stably within a limited step and assign all task target points without conflict. The feasibility and effectiveness of the method were also verified. The comprehensive verification platform for the 3D simulation process of UAV swarm task allocation and execution was given in the form of real-time deduction.
-
圖 1 基于交替方向法網絡進化博弈的無人機集群任務分配算法流程圖
Figure 1. Flowchart of the unmanned aerial vehicle swarm task allocation algorithm, based on the alternating direction method of multipliers (ADMM) network potential game theory
圖 2 任務分配結果. (a) 初始時刻; (b) 150 s; (c) 200 s; (d) 300 s
Figure 2. Task allocation results: (a) initial moment; (b) 150 s; (c) 200 s; (d) 300 s
圖 6 三維視景場景演示. (a) 任務分配場景1; (b) 任務分配場景2
Figure 6. 3D visual simulation platform snapshots: (a) task allocation scenario 1; (b) task allocation Scenario 2
中文字幕在线观看表 1 本文所提分布式任務分配算法與拍賣算法性能指標
Table 1. Performance metrics of the distributed tasks allocation algorithm and CBBA algorithm
Algorithm Total reward Completion time/s Energy consumption Path length /m Distributed tasks allocation algorithm 121.52 309.19 356.23 995.62 CBBA algorithm 100.44 370.30 409.18 1140.36 
下載: 導出CSV
-
參考文獻
[1] Duan H B, Qiu H X. Unmanned Aerial Vehicle Swarm Autonomous Control Based on Swarm Intelligence. Beijing: Science Press, 2018段海濱, 邱華鑫. 基于群體智能的無人機集群自主控制. 北京: 科學出版社, 2018 [2] Jain R. Efficient Market Mechanisms and Simulation-based Learning for Multi-agent Systems [Dissertation]. Berkeley: University of California, 2004 [3] Wu S T. Cooperative Flight Control System. Beijing: Science Press, 2018吳森堂. 協同飛行控制系統. 北京: 科學出版社, 2018 [4] Yang Q, Duan H B. Verification of unmanned aerial vehicle swarm behavioral mechanism underlying the formation of Anser cygnoides. Chin J Eng, 2019, 41(12): 1599楊慶, 段海濱. 仿鴻雁編隊的無人機集群飛行驗證. 工程科學學報, 2019, 41(12):1599 [5] Yan F, Zhu X P, Zhou Z, et al. Real-time task allocation for a heterogeneous multi-UAV simultaneous attack. Scientia Sinica Informationis, 2019, 49(5): 555 doi: 10.1360/N112018-00338嚴飛, 祝小平, 周洲, 等. 考慮同時攻擊約束的多異構無人機實時任務分配. 中國科學:信息科學, 2019, 49(5):555 doi: 10.1360/N112018-00338 [6] Wang R, Xiao B S. Cooperative search for multi-UAVs via an improved pigeon-inspired optimization and Markov chain approach. Chin J Eng, 2019, 41(10): 1342王瑞, 肖冰松. 基于改進鴿群優化和馬爾可夫鏈的多無人機協同搜索方法. 工程科學學報, 2019, 41(10):1342 [7] Luo Y L, Huang X Y, Yang J, et al. Auction mechanism-based multi-type task planning for heterogeneous UAVs swarm // 2020 IEEE 20th International Conference on Communication Technology. Nanning, 2020: 698 [8] Zhang X L, Tan Y J, Yang Z W. Resource allocation optimization of equipment development task based on MOPSO algorithm. J Syst Eng Electron, 2019, 30(6): 1132 doi: 10.21629/JSEE.2019.06.09 [9] Yavuz H S, G?Ktas H, ?ev?kalp H, et al. Optimal task allocation for multiple UAVs // 2020 28th Signal Processing and Communications Applications Conference (SIU). Gaziantep, 2020: 1 [10] Li T, Shin H S, Tsourdos A. Efficient decentralized task allocation for UAV swarms in multi-target surveillance missions // 2019 International Conference on Unmanned Aircraft Systems (ICUAS). Atlanta, 2019: 61 [11] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl, 1976, 2(1): 17 doi: 10.1016/0898-1221(76)90003-1 [12] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 2011, 3(1): 1 [13] Guo L. Estimation, control, and games of dynamical systems with uncertainty. Scientia Sinica Informationis, 2020, 50(9): 1327 doi: 10.1360/SSI-2020-0277郭雷. 不確定性動態系統的估計、控制與博弈. 中國科學:信息科學, 2020, 50(9):1327 doi: 10.1360/SSI-2020-0277 [14] Zhen Z Y, Xing D J, Gao C. Cooperative search-attack mission planning for multi-UAV based on intelligent self-organized algorithm. Aerosp Sci Technol, 2018, 76: 402 doi: 10.1016/j.ast.2018.01.035 [15] Kim M H, Baik H, Lee S. Response threshold model based UAV search planning and task allocation. J Intell Robotic Syst, 2014, 75(3-4): 625 doi: 10.1007/s10846-013-9887-6 [16] Choi H L, Brunet L, How J P. Consensus-based decentralized auctions for robust task allocation. IEEE Trans Robotics, 2009, 25(4): 912 doi: 10.1109/TRO.2009.2022423 [17] Wu H S, Li H, Xiao R B. A blockchain bee colony double inhibition labor division algorithm for spatio-temporal coupling task with application to UAV swarm task allocation. J Syst Eng Electron, 2021, 32(5): 1180 doi: 10.23919/JSEE.2021.000101 [18] Ma Y H, Zhao Y F, Bai S Y, et al. Collaborative task allocation of heterogeneous multi-UAV based on improved CBGA algorithm // 2020 16th International Conference on Control, Automation, Robotics and Vision (ICARCV). Shenzhen, 2020: 795 [19] Fu X W, Pan J, Gao X G, et al. Task allocation method for multi-UAV teams with limited communication bandwidth // 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV). Singapore, 2018: 1874 [20] Fu X W, Feng P, Gao X G. Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism. IEEE Access, 2019, 7: 41090 doi: 10.1109/ACCESS.2019.2907544 [21] Wu B B, Zhang B N, Zhao B, et al. A potential game approach to multiple UAVs 3D placement in iot communication networks // 2020 International Conference on Wireless Communications and Signal Processing (WCSP). Nanjing, 2020: 660 [22] Marden J R, Arslan G, Shamma J S. Connections between cooperative control and potential games illustrated on the consensus problem // 2007 European Control Conference (ECC). Kos, 2007: 4604 [23] Xie Y, Shanbhag U V. SI-ADMM: A stochastic inexact ADMM framework for stochastic convex programs. IEEE Trans Autom Control, 2020, 65(6): 2355 doi: 10.1109/TAC.2019.2953209 [24] Jia X, Wu S T, Wen Y M, et al. A distributed decision method for missiles autonomous formation based on potential game. J Syst Eng Electron, 2019, 30(4): 738 doi: 10.21629/JSEE.2019.04.11 [25] Zheng X B, Zhang F B, Song T, et al. Heterogeneous multi-UAV distributed task allocation based on CBBA // 2019 IEEE International Conference on Unmanned Systems. Beijing, 2019: 704 -
點擊查看大圖
圖(6) / 表(1)
計量
- 文章訪問數: 671
- HTML全文瀏覽量: 409
- PDF下載量: 99
- 被引次數: 0
