Multi-UAV Cooperative Target Allocation Based on AC-DSDE Evolutionary Algorithm
-
摘要:
多无人机协同目标分配最优问题(Multi-UAV cooperative target allocation optimal problem, MUCTAOP), 旨在求解组合分配问题的最小代价值, 是最具有挑战性的多约束组合优化问题之一. 结合进化算法解决MUCTAOP需要考虑两个关键因素: 1) 在进化过程中保持覆盖问题空间的“探索性”和“开发性”平衡; 2) 建立符合实际战场复杂环境的多约束条件. 为解决这两个关键因素, 本文提出一种新的近似聚类混合双策略差分进化算法(Approximate clustering dual-strategy differential evolution algorithm, AC-DSDE). 首先, 根据父代种群适应度值将个体分成“探索类个体”与“开发类个体”; 然后根据混合双策略变异方案平衡后代多样性与收敛性; 最后, 结合无人机自身性能约束、协同约束和实际三维复杂环境构建约束函数. 实验结果表明, 本文所提出的AC-DSDE算法能够快速地找到合理的分配方案.
-
关键词:
- AC-DSDE /
- 混合双策略 /
- 差分进化算法 /
- 多无人机协同目标分配最优问题
Abstract:Multi-UAV cooperative target assignment optimization problem (MUCTAOP), aimed at solving the minimum cost value portfolio allocation problem is one of the most challenging multi-constrained combinatorial optimization problem. Combining evolutionary algorithms to solve MUCTAOP needs to consider two key factors: first, in the process of evolution, we should keep the balance of “exploratory” and “exploitative” covering the problem space; Second, the establishment of a variety of constraints in line with the actual battlefield complex environment. In order to solve the two key factors, this paper proposes a new approximate clustering dual-strategy differential evolution algorithm (AC-DSDE). Firstly, according to the fitness value of the father, the population is divided into sub-populations of “exploration type individual” and “development type individual”; Then the diversity and convergence of the offspring are balanced according to the mixed double strategy variation scheme; Finally, this paper combines the UAVs' own performance constraints, collaborative constraints and the actual three-dimensional complex environment to build the constraint function. The experimental results show that the AC-DSDE algorithm proposed in this paper can quickly find a reasonable allocation scheme.
-
图 1 MUCTA在三维任务环境中的场景
Fig. 1 Simulation diagram of MUCTA in athree-dimensional environment
图 4 三维环境中实验1的仿真结果
Fig. 4 Simulation results of Experiment 1 in a three-dimensional environment
图 5 三维环境中实验2的仿真结果
Fig. 5 Simulation results of Experiment 2 in a three-dimensional environment
图 7 实验1分配结果的单条和平均收敛曲线对比
Fig. 7 Comparison of the single and average convergence curves of the results of Experiment 1
表 1 实验初始数据
Table 1 Initialization of experimental data
Model Data type 1 2 3 4 5 6 7 8 9 10 N=M Upos [10, 25, 10] [140, 15, 12] [30, 80, 13] [110, 40, 15] [80, 20, 15] [20, 55, 15] [120, 16, 17] [160, 20, 15] [80, 50, 12] [170, 62, 13] Tpos [20, 210, 13] [46, 200, 12] [64, 210, 23] [154, 210, 12] [100, 200, 12] [118, 210, 14] [82, 220, 12] [136, 190, 11] [10, 170, 10] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] $V\ (\rm km/h)$ [0.2, 0.3] [0.2, 0.4] [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] [0.3, 0.5] [0.3, 0.6] Umissile 6.0 8.0 6.0 4.0 6.0 4.0 8.0 8.0 6.0 6.0 $D\ (\rm km)$ 500 700 300 350 700 900 450 610 450 610 W 3.0 2.0 1.0 3.0 2.0 1.0 2.0 3.0 2.0 1.0 Tsort [3, 4] [5, 2] [6, 1] [7, 4] N>M Upos [10, 25, 10] [140, 15, 12] [30, 80, 13] [110, 40, 15] [80, 20, 15] [20, 55, 15] [120, 16, 17] [160, 20, 15] [80, 50, 12] [170, 40, 13] Tpos [28, 210, 13] [64, 210, 23] [154, 210, 14] [118, 210, 14] [136, 190, 11] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] $V\ (\rm km/h)$ [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] [0.2, 0.3] [0.35, 0.45] [0.3, 0.5] [0.3, 0.6] Umissile 6.0 8.0 6.0 4.0 6.0 4.0 8.0 8.0 6.0 6.0 $D\ (\rm km)$ 400 700 650 500 700 900 450 610 400 700 W 1.0 3.0 4.0 2.0 1.0 1.0 Tsort [1, 3] [2, 4] [1, 2] $Twait\ (\rm{m})$ 200 500 600 200 800 600 300 200 700 500 N<M Upos [78, 20, 15] [93, 31, 12] [31, 20, 13] [112, 32, 15] [150, 25, 10] [170, 50, 15] Tpos [28, 211, 13] [46, 220, 12] [64, 210, 23] [154, 212, 12] [100, 200, 12] [118, 213, 14] [82, 225, 12] [136, 190, 11] [10, 180, 10] [172, 170, 12] Rpos [130, 70, 4, 23] [120, 140, 4, 26] [42, 103, 5, 30] [42, 180, 5, 25] [50, 50, 5, 26] Umissile 4.0 8.0 6.0 4.0 6.0 4.0 $V\ (\rm km/h)$ [0.2, 0.3] [0.2, 0.4] [0.4, 0.75] [0.3, 0.6] [0.2, 0.3] [0.2, 0.4] $D\ (\rm km)$ 400 700 650 500 610 400 W 1.0 0.8 0.6 0.7 0.9 0.8 1.0 0.7 1.0 1.0 Tsort [4, 5] [5, 2] [6, 7] [7, 4] $Twait\ (\rm{m})$ 100 600 
下载: 导出CSV
表 2 两组实验进化参数的设定
Table 2 Setting of experimental evolution parameters of two groups
模式 实验 1 实验 2 Un Tn Pn Gen Num Un Tn Pn Gen Num N = M 10 10 50 1 000 20 30 30 50 1 000 10 N > M 10 6 50 1 000 20 30 10 50 1 000 10 N < M 6 10 50 1 000 20 10 30 50 1 000 10
下载: 导出CSV
表 3 实验1的分配结果
Table 3 Assignment results of Experiment 1
模式 分配结果 N = M UAV 1 2 3 4 5 6 7 8 9 10 Target 9 6 1 7 5 2 3 10 8 4 Cost 265.9 685.4 306.1 481.3 609.2 367.6 490.1 216.4 424.6 294.0 N > M UAV 1 2 3 4 5 6 7 8 9 10 Target 1 6 2 5 1 1 4 6 5 3 Cost 429.4 311.7 338.0 437.6 866.6 354.6 530.2 216.4 424.6 294.0 N < M UAV 1 1 1 2 3 3 3 4 5 6 Target 3 5 7 6 1 2 9 8 4 10 Cost 228.7 630.7 75.3 525.9 110.5 83.1 547.1 450.6 452.8 169.6
下载: 导出CSV
表 4 两组实验分配结果的统计数据
Table 4 Statistics of the results of the two groups ofexperimental assignments
实验 模式 平均时间(s) 平均代价 最优代价 约束违背(%) 优解(%) 实验1 N = M 16.1 8 107.9 8 058.8 4.49 95 N > M 22.9 6 808.5 6 690.4 4.07 75 N < M 23.6 5 795.4 5 573.3 2.04 80 实验2 N = M 38.2 18 605.1 18 093.6 6.21 60 N > M 46.6 13 490.5 13 302.1 7.13 70 N < M 50.5 13 537.4 12 528.7 5.24 80
下载: 导出CSV
表 5 AC-DSDE与其他算法之间的比较
Table 5 Comparison between AC-DSDE and other algorithms
模式 方法 UAV与目标点数量 种群数量 迭代次数 实验次数 CR MR IGMR 最优代价 平均代价 平均时间 (s) N = M AC-DSDE N = M = 10 30 1 000 10 0.9 null 0.3 8 058.8 8 107.9 16.1 DMDE N = M = 10 30 1 000 10 CR null 1-CR 8 257.6 8 204.8 19.8 APC-DE N = M = 10 30 1 000 10 0.9 null 0.3 8 145.8 8 168.5 24.6 N > M AC-DSDE N = 10, M = 6 30 1 000 10 0.9 null 0.3 6 690.4 6 808.5 22.9 DMDE N = 10, M = 6 30 1 000 10 CR null 1-CR 6 737.1 6 973.7 29.19 APC-DE N = 10, M = 6 30 1 000 10 0.9 null 0.3 6 770.3 6 835.6 26.5 N < M AC-DSDE N = 6, M = 10 30 1 000 10 0.9 null 0.3 5 573.3 5 795.4 23.6 DMDE N = 6, M = 10 30 1 000 10 CR null 1-CR 5 819.9 5 970.7 26.4 APC-DE N = 6, M = 10 30 1 000 10 0.9 null 0.3 5 712.6 2 838.7 27.5
下载: 导出CSV
-
[1] Zhao Yi-Jing, Zheng Zheng, Liu Yang. Survey on computational-intelligence-based UAV path planning. Knowledge-Based Systems, 2018, 158: 54−64 doi: 10.1016/j.knosys.2018.05.033 [2] Ramirez Atencia C, Del Ser J, Camacho D. Weighted strategies to guide a multi-objective evolutionary algorithm for multi-UAV mission planning. Swarm and Evolutionary Computation, 2019, 44: 480−495 doi: 10.1016/j.swevo.2018.06.005 [3] 韩博文, 姚佩阳, 孙昱. 基于多目标MSQPSO算法的UAVS协同任务分配. 电子学报, 2017, 8: 1856−1863 doi: 10.3969/j.issn.0372-2112.2017.08.008Han Bo-Wen, Tao Pei-Yang, Sun Yu. UAVs collaborative task allocation based on multi-objective MSQPSO algorithm. Acta Electronica Sinica, 2017, 8: 1856−1863 doi: 10.3969/j.issn.0372-2112.2017.08.008 [4] Vetrella A R, Causa F, Renga A. Multi-UAV carrier phase differential GPS and vision-based sensing for high accuracy attitude estimation. Journal of Intelligent & Robotic Systems, 2019, 93(1-2): 245−260 [5] Shah K, Reddy P, Vairamuthu S. Improvement in Hungarian algorithm for assignment problem. Advances in Intelligent Systems and Computing, 2015, 324: 1−8 [6] Luitpold B. Coordinated target assignment and UAV path planning with timing constraints. Journal of Intelligent & Robotic Systems, 2019, 3(4): 857−869 [7] Xin Yi, Zhu An-Min. An improved neuro-dynamics-based approach to online path planning for multi-robots in unknown dynamic environments. In: Processdings of the 2013 IEEE International Conference on Robotics and Biomimetics. Shenyang, China: IEEE, 2013. 1–6. [8] ElGibreen H, Youcef-Toumi K. Dynamic task allocation in an uncertain environment with heterogeneous multi-agents. Autonomous Robots, 2019: 1−26 [9] Hunt S, Meng Q, Hinde C. A consensus-based grouping algorithm for multi-agent cooperative task allocation with complex requirements. Cognitive Computation, 2014, 6(3): 338−350 doi: 10.1007/s12559-014-9265-0 [10] Cui Ying, Wu Xiao, Song Jiao, Ma Hui-Jiao. A dynamic task equilibrium allocation algorithm based on combinatorial auctions. In: Proceedings of the 8th International Conference on Intelligent Human-Machine Systems and Cybernetics. Hangzhou, China. IEEE, 2016. 530–533. [11] Whitbrook A, Meng Q, Chung P W H. Addressing robustness in time-critical, distributed, task allocation algorithms. Applied Intelligence, 2019, 49(1): 1−15 doi: 10.1007/s10489-018-1169-3 [12] Cao Y, Wei W, Bai Y. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm. Cluster Computing, 2017, 20(7): 1417−1420 [13] Roy R, Das M, Dehuri S. A combinatorial multi-objective particle swarm optimization based algorithm for task allocation in distributed computing systems. Communications in Computer and Information Science, 2011, 193: 113−125 [14] Saeedvand S, Aghdasi H S, Baltes J. Robust multi-objective multi-humanoid robots task allocation based on novel hybrid metaheuristic algorithm. Applied Intelligence, 2019, 49: 1−33 doi: 10.1007/s10489-018-1169-3 [15] Jana B, Chakraborty M, Mandal T. A task scheduling technique based on particle swarm optimization algorithm in cloud environment. Advances in Intelligent Systems and Computing, 2019, 742: 525−536 [16] Alencar R C, Santana C J, Bastos-Filho C J A. Optimizing routes for medicine distribution using team ant colony system. Advances in Intelligent Systems and Computing, 2020, 923: 40−49 [17] Kumari S, Gupta G P. Differential evolution-based sensor allocation for target tracking application in sensor-cloud. Advances in Intelligent Systems and Computing, 2018, 695: 347−356 [18] Tang Shu-Yan, Qin Zheng, Xin Jian-Kuan. Collaborative task assignment scheme for multi-UAV based on cluster structure. In: Proceedings of the 2010 International Conference on Intelligent Human-Machine Systems and Cybernetics. Nangjing, China: IEEE, 2010. 285–289. [19] Ramirez-Atencia C, Bello-Orgaz G, R-Moreno M D. Solving complex multi-UAV mission planning problems using multiobjective genetic algorithms. Soft Computing, 2017, 21(17): 4883−4900 doi: 10.1007/s00500-016-2376-7 [20] Wang Yan-Wu, Wei Yao-Wen, Liu Xiao-Kang, Zhou Nan, Cassandras Christos G. Optimal persistent monitoring using second-order agents with physical constraints. IEEE Transactions on Automatic Control, 2018, 64(8): 3239−3252 [21] 魏政磊, 赵辉, 黄汉桥. 基于SAGWO算法的UCAVs动态协同任务分配. 北京航空航天大学学报, 2018, 8: 1651−1664Wei Zheng-Lei, Zhao Hui, Huang Han-Qiao. Dynamic cooperative task assignment of UCAVs based on SAGWO algorithm. Journal of Beijing University of Aeronautics And Astronautics, 2018, 8: 1651−1664 [22] Zhao Ming, Zhao Ling-Ling, Su Xiao-Hong, Ma Pei-Jun, Zhang Yan-Hang. Improved discrete mapping differential evolution for multi-unmanned aerial vehicles cooperative multi-targets assignment under unified model. International Journal of Machine Learning and Cybernetics, 2017, 8(3): 765−780 doi: 10.1007/s13042-015-0364-3 [23] Li Xiao-Dong. Efficient differential evolution using speciation for multimodal function optimization. In: Proceedings of the Genetic and Evolutionary Computation. Washington, USA: GECCO, 2005. 873 [24] Thomsen R. Multimodal optimization using crowding-based differential evolution. In: Proceedings of the 2004 Congress on Evolutionary Computation. Portland, USA: IEEE, 2004. 1382–1389 [25] Stoean C L, Preuss M, Stoean R. Disburdening the species conservation evolutionary algorithm of arguing with radii. In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. London, UK: 2007. 1420–1427 [26] Wang Z J, Zhan Z H, Lin Y. Dual-strategy differential evolution with affinity propagation clustering for multimodal optimization problems. IEEE Transactions on Evolutionary Computation, 2018, 22(6): 894−908 doi: 10.1109/TEVC.2017.2769108 -
计量
- 文章访问数: 1336
- HTML全文浏览量: 228
- PDF下载量: 267
- 被引次数: 0
