2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于 AC-DSDE 进化算法多 UAVs协同目标分配

黄刚 李军华

黄刚, 李军华. 基于 AC-DSDE 进化算法多 UAVs协同目标分配. 自动化学报, 2021, 47(1): 173−184 doi: 10.16383/j.aas.c190334
引用本文: 黄刚, 李军华. 基于 AC-DSDE 进化算法多 UAVs协同目标分配. 自动化学报, 2021, 47(1): 173−184 doi: 10.16383/j.aas.c190334
Huang Gang, Li Jun-Hua. Multi-UAV cooperative target allocation based on AC-DSDE evolutionary algorithm. Acta Automatica Sinica, 2021, 47(1): 173−184 doi: 10.16383/j.aas.c190334
Citation: Huang Gang, Li Jun-Hua. Multi-UAV cooperative target allocation based on AC-DSDE evolutionary algorithm. Acta Automatica Sinica, 2021, 47(1): 173−184 doi: 10.16383/j.aas.c190334

基于 AC-DSDE 进化算法多 UAVs协同目标分配

doi: 10.16383/j.aas.c190334
基金项目: 国家自然科学基金(61440049, 61866025, 61866026), 江西省自然科学基金(20181BAB202025), 江西省优势科技创新团队计划(20181BCB24008), 江西省研究生创新基金(YC2018-S369)资助
详细信息
    作者简介:

    黄刚:南昌航空大学硕士研究生. 主要研究方向为导航制导与控制. E-mail: hgnchk@163.com

    李军华:南昌航空大学教授. 主要研究方向为进化计算和智能控制. 本文通信作者. E-mail: jhlee126@126.com

Multi-UAV Cooperative Target Allocation Based on AC-DSDE Evolutionary Algorithm

Funds: Supported by National Natural Science Foundation of China (61440049, 61866025, 61866026), Natural Science Foundation of Jiangxi Province (20181BAB202025), Superiority Science and Technology Innovation Team Program of Jiangxi Province (20181BCB24008), Graduate Innovation Foundation of Jiangxi Province (YC2018-S369)
  • 摘要:

    多无人机协同目标分配最优问题(Multi-UAV cooperative target allocation optimal problem, MUCTAOP), 旨在求解组合分配问题的最小代价值, 是最具有挑战性的多约束组合优化问题之一. 结合进化算法解决MUCTAOP需要考虑两个关键因素: 1) 在进化过程中保持覆盖问题空间的“探索性”和“开发性”平衡; 2) 建立符合实际战场复杂环境的多约束条件. 为解决这两个关键因素, 本文提出一种新的近似聚类混合双策略差分进化算法(Approximate clustering dual-strategy differential evolution algorithm, AC-DSDE). 首先, 根据父代种群适应度值将个体分成“探索类个体”与“开发类个体”; 然后根据混合双策略变异方案平衡后代多样性与收敛性; 最后, 结合无人机自身性能约束、协同约束和实际三维复杂环境构建约束函数. 实验结果表明, 本文所提出的AC-DSDE算法能够快速地找到合理的分配方案.

  • 图  1  MUCTA在三维任务环境中的场景

    Fig.  1  Simulation diagram of MUCTA in athree-dimensional environment

    图  2  个体分组

    Fig.  2  Individual grouping

    图  3  个体分组

    Fig.  3  Individual grouping

    图  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

    图  6  实验1分配结果的单条收敛曲线

    Fig.  6  Single convergence curve of Experiment 1assignment results

    图  7  实验1分配结果的单条和平均收敛曲线对比

    Fig.  7  Comparison of the single and average convergence curves of the results of Experiment 1

    图  8  不同算法的平均收敛曲线

    Fig.  8  Average convergence curve of different algorithms

    表  1  实验初始数据

    Table  1  Initialization of experimental data

    ModelData type12345678910
    N=MUpos[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]
    Umissile6.08.06.04.06.04.08.08.06.06.0
    $D\ (\rm km)$500700300350700900450610450610
    W3.02.01.03.02.01.02.03.02.01.0
    Tsort[3, 4][5, 2][6, 1][7, 4]
    N>MUpos[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]
    Umissile6.08.06.04.06.04.08.08.06.06.0
    $D\ (\rm km)$400700650500700900450610400700
    W1.03.04.02.01.01.0
    Tsort[1, 3][2, 4][1, 2]
    $Twait\ (\rm{m})$200500600200800600300200700500
    N<MUpos[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]
    Umissile4.08.06.04.06.04.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)$400700650500610400
    W1.00.80.60.70.90.81.00.71.01.0
    Tsort[4, 5][5, 2][6, 7][7, 4]
    $Twait\ (\rm{m})$100600
    下载: 导出CSV

    表  2  两组实验进化参数的设定

    Table  2  Setting of experimental evolution parameters of two groups

    模式实验 1实验 2
    UnTnPnGenNumUnTnPnGenNum
    N = M1010501 000203030501 00010
    N > M106501 000203010501 00010
    N < M610501 000201030501 00010
    下载: 导出CSV

    表  3  实验1的分配结果

    Table  3  Assignment results of Experiment 1

    模式分配结果
    N = MUAV12345678910
    Target96175231084
    Cost265.9685.4306.1481.3609.2367.6490.1216.4424.6294.0
    N > MUAV12345678910
    Target1625114653
    Cost429.4311.7338.0437.6866.6354.6530.2216.4424.6294.0
    N < MUAV1112333456
    Target35761298410
    Cost228.7630.775.3525.9110.583.1547.1450.6452.8169.6
    下载: 导出CSV

    表  4  两组实验分配结果的统计数据

    Table  4  Statistics of the results of the two groups ofexperimental assignments

    实验模式平均时间(s)平均代价最优代价约束违背(%)优解(%)
    实验1N = M16.18 107.98 058.84.49 95
    N > M22.96 808.56 690.44.07 75
    N < M23.65 795.45 573.32.04 80
    实验2N = M38.218 605.118 093.66.21 60
    N > M46.613 490.513 302.17.13 70
    N < M50.513 537.412 528.75.24 80
    下载: 导出CSV

    表  5  AC-DSDE与其他算法之间的比较

    Table  5  Comparison between AC-DSDE and other algorithms

    模式方法UAV与目标点数量种群数量迭代次数实验次数CRMRIGMR最优代价平均代价平均时间 (s)
    N = MAC-DSDE N = M = 10301 000100.9null0.38 058.88 107.916.1
    DMDEN = M = 10301 00010CRnull1-CR8 257.68 204.819.8
    APC-DEN = M = 10301 000100.9null0.38 145.88 168.524.6
    N > MAC-DSDEN = 10, M = 6301 000100.9null0.36 690.46 808.522.9
    DMDEN = 10, M = 6301 00010CRnull1-CR6 737.16 973.729.19
    APC-DEN = 10, M = 6301 000100.9null0.36 770.36 835.626.5
    N < MAC-DSDEN = 6, M = 10301 000100.9null0.35 573.35 795.423.6
    DMDEN = 6, M = 10301 00010CRnull1-CR5 819.95 970.726.4
    APC-DEN = 6, M = 10301 000100.9null0.35 712.62 838.727.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.008

    Han 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−1664

    Wei 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
  • 加载中
图(8) / 表(5)
计量
  • 文章访问数:  1338
  • HTML全文浏览量:  230
  • PDF下载量:  267
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-05-06
  • 录用日期:  2019-08-15
  • 网络出版日期:  2021-01-29
  • 刊出日期:  2021-01-29

目录

    /

    返回文章
    返回