A heterogeneous multi-task assignment algorithm based on multi-round distributed auction
-
摘要:
针对多机协同探测、攻击、评估等不同作战任务的分布式决策需要，建立了一种面向异构且具有时序约束任务的多轮次分布式拍卖算法。所提算法较为灵活地解决了不同能力无人机(UAV)之间具有复杂约束的分布式协同任务分配问题。在分布式任务分配框架中，每架无人机可实现分布式异步计算和异步通信，且能确保较好的求解效率和准确性。任务分配原则以就近分配为主，同时兼顾目标价值和时序约束，实现了在有限资源情况下对重要目标的优先分配，且使总的行程最短。仿真结果表明：在给定任意无人机和目标数量及无人机作战能力配置的情况下，所提算法均能得到较好的分配结果。
Abstract:The algorithm solves the distributed cooperative task assignment problem with complex constraints among unmanned aerial vehicles (UAVs) with different capabilities in a more flexible way. Better solution accuracy and efficiency can be ensured by each UAV in the distributed task allocation framework by enabling distributed asynchronous computation and asynchronous communication. In order to prioritize significant targets with limited resources and the quickest total journey time, the task assignment principle is based on proximity assignment while taking the target value and schedule limitations into consideration. Simulation results show that this heterogeneous multi-round distributed auction algorithm can obtain good assignment results for any given number of UAVs and targets and UAV combat capability configuration.
-
图 3 场景1探测任务分配结果示意图
Figure 3. Schematic diagram of the task allocation results of the detection in scenario 1
图 4 场景1攻击任务分配结果示意图
Figure 4. Schematic diagram of the task allocation results of the attack in scenario 1
图 5 场景1毁伤评估任务分配结果示意图
Figure 5. Schematic diagram of the task assignment results of the damage assessment in scenario 1
图 6 场景2探测任务分配结果示意图
Figure 6. Schematic diagram of the task allocation results of the detection in scenario 2
图 7 场景2攻击任务分配结果示意图
Figure 7. Schematic diagram of attack task allocation results in scenario 2
图 8 场景2毁伤评估任务分配结果示意图
Figure 8. Schematic diagram of the task allocation results of the destruction assessment in scenario 2
图 9 无人机1对目标的收益调整过程
Figure 9. The process of adjusting the earnings of UAV1 to the target
图 10 不同鲁棒性条件设置下算法收敛性能测试
Figure 10. Algorithm convergence performance test under different robustness conditions
图 11 各组实验计算结果正确率统计
Figure 11. Statistics on the correct rate of calculation results for each group of experiments
表 1 无人机探测、攻击、毁伤评估能力设置（场景1）
Table 1. UAV detection, attack, and damage assessment capability setting (Scenario 1)
能力 1号
无人机2号
无人机3号
无人机4号
无人机5号
无人机6号
无人机7号
无人机8号
无人机探测 √ × √ √ × √ √ √ 攻击 √ √ × √ √ × √ √ 毁伤评估 × √ × × √ × √ × 注：√表示具备能力，×不具备能力。 
下载: 导出CSV
表 2 各无人机探测、攻击与毁伤评估任务对各目标的分配结果（场景1）
Table 2. Summary table of the allocation results of each UAV detection, attack and evaluation mission to each target (Scenario 1)
无人机
编号目标1 目标2 目标3 目标4 目标5 目标6 目标7 目标8 目标9 目标10 1 D/A 2 V A 3 D 4 D/A 5 A V 6 D 7 V D/A 8 D/A
下载: 导出CSV
表 3 无人机探测、攻击、毁伤评估能力设置（场景2）
Table 3. UAV detection, attack, and damage assessment capability setting (Scenario 2)
能力 UAV 1 UAV 2 UAV 3 UAV 4 UAV 5 UAV 6 UAV 7 UAV 8 探测 √ √ √ √ √ √ × √ 攻击 √ × √ × √ × √ √ 毁伤评估 √ × × × × √ × ×
下载: 导出CSV
表 4 各无人机探测、攻击与评估任务对各目标的分配结果（场景2）
Table 4. Summary table of the allocation results of each UAV detection, attack and evaluation mission to each target (Scenario 2)
无人机编号 目标1 目标2 目标3 目标4 目标5 目标6 UAV1 D/A/V UAV2 D UAV3 D A UAV4 D UAV5 A D UAV6 V UAV7 A UAV8 D A
下载: 导出CSV
-
[1] 陈侠, 魏晓明, 徐光延. 基于分布式邀请拍卖算法的多机协同空战决策[J]. 系统仿真学报, 2014, 26(6): 1257-1261.CHAN X, WEI X M, XU G Y. Cooperative air combat decision making for multiple UCAV based on decentralized invite auction algorithm[J]. Journal of System Simulation, 2014, 26(6): 1257-1261(in Chinese). [2] 贾高伟, 王建峰. 无人机集群任务规划方法研究综述[J]. 系统工程与电子技术, 2021, 43(1): 99-111.JIA G W, WANG J F. Research review of UAV swarm mission planning method[J]. Systems Engineering and Electronics, 2021, 43(1): 99-111(in Chinese). [3] WANG J F, JIA G W, XIN H B, et al. Research on dynamic task allocation method of heterogeneous multi-UAV based on consensus based bundle algorithm[C]//Proceeding of the 2020 Chinese Automation Congress. Piscataway: IEEE Press, 2020: 2214-2219. [4] LIU P F, WANG B, LIU W J, et al. Multi-task allocation of multi-UAV coalition based on improved quantum genetic algorithm[C]// Proceeding of the 2021 40th Chinese Control Conference. Piscataway: IEEE Press, 2021: 1802-1807. [5] Y YU J Y, GUO J S, ZHANG X F, et al. A novel tent-levy fireworks algorithm for the UAV task allocation problem under uncertain environment[J]. IEEE Access, 2022, 10: 102373-102385. doi: 10.1109/ACCESS.2022.3208870 [6] CHEN Y H, CHEN J C, DU C L. Allocation of multi-UAVs timing-dependent tasks based on completion time[C]//Proceeding of the 2022 WRC Symposium on Advanced Robotics and Automation. Piscataway: IEEE Press, 2022: 71-76. [7] TANG Y F, DOU L Q, ZHANG R L. A novel deep learning scheme for cooperative task allocation of large-scale UAVs[C]//Proceeding of the 2022 41st Chinese Control Conference. Piscataway: IEEE Press, 2022: 1866-1871. [8] ZHANG W, LI Z X, WU W H, et al. A bilevel task allocation method for heterogeneous multi-UUV recovery system[J]. Ocean Engineering, 2023, 274: 114057. doi: 10.1016/j.oceaneng.2023.114057 [9] CHEN X Y, ZHANG P, DU G L, et al. A distributed method for dynamic multi-robot task allocation problems with critical time constraints[J]. Robotics and Autonomous Systems, 2019, 118: 31-46. doi: 10.1016/j.robot.2019.04.012 [10] XUE J B, ZHANG H, HU Q C. A low-cost communication security scheme of UAV based on multi-round reverse auction model[J]. Pervasive and Mobile Computing, 2022, 85: 101652. doi: 10.1016/j.pmcj.2022.101652 [11] SHI J Q, TAN L, LIAN X F, et al. A multi-unmanned aerial vehicle dynamic task assignment method based on bionic algorithms[J]. Computers and Electrical Engineering, 2022, 99: 107820. doi: 10.1016/j.compeleceng.2022.107820 [12] KARELS V C G, VEELENTURF L P, VAN WOENSEL T. An auction for collaborative vehicle routing: models and algorithms[J]. EURO Journal on Transportation and Logistics, 2020, 9(2): 100009. doi: 10.1016/j.ejtl.2020.100009 [13] RINALDI M, PRIMATESTA S, GUGLIERI G, et al. Auction-based task allocation for safe and energy efficient UAS parcel transportation[J]. Transportation Research Procedia, 2022, 65: 60-69. doi: 10.1016/j.trpro.2022.11.008 [14] JIN L, LI S, LA H M, et al. Dynamic task allocation in multi-robot coordination for moving target tracking: a distributed approach[J]. Automatica, 2019, 100: 75-81. doi: 10.1016/j.automatica.2018.11.001 [15] ZHANG M, LI W, WANG M M, et al. Helicopter-UAVs search and rescue task allocation considering UAVs operating environment and performance[J]. Computers & Industrial Engineering, 2022, 167: 107994. [16] NEDJAH N, DE MENDONÇA R M, DE MACEDO MOURELLE L. PSO-based distributed algorithm for dynamic task allocation in a robotic swarm[J]. Procedia Computer Science, 2015, 51: 326-335. doi: 10.1016/j.procs.2015.05.250 [17] 冉华明, 周锐, 董卓宁, 等. 空战中协同干扰、探测、攻击任务分配[J]. 北京航空航天大学学报, 2015, 41(5): 911-918.RAN H M, ZHOU R, DONG Z N, et al. Cooperative jamming-detecting-attacking task allocation in air combat[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(5): 911-918(in Chinese). [18] 魏政磊, 赵辉, 黄汉桥, 等. 基于SAGWO算法的UCAVs动态协同任务分配[J]. 北京航空航天大学学报, 2018, 44(8): 1651-1664.WEI Z L, ZHAO H, HUANG H Q, et al. Dynamic UCAVs cooperative task allocation based on SAGWO algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(8): 1651-1664(in Chinese). [19] ZHEN Z Y, WEN L D, WANG B L, et al. Improved contract network protocol algorithm based cooperative target allocation of heterogeneous UAV swarm[J]. Aerospace Science and Technology, 2021, 119: 107054. doi: 10.1016/j.ast.2021.107054 [20] KURDI H, ALDAOOD M F, AL-MEGREN S, et al. Adaptive task allocation for multi-UAV systems based on bacteria foraging behaviour[J]. Applied Soft Computing, 2019, 83: 105643. doi: 10.1016/j.asoc.2019.105643 [21] 陈侠, 刘永泰. 多UAV攻击移动目标的协同任务分配与航迹规划[J]. 火力与指挥控制, 2020, 45(9): 35-40.CHEN X, LIU Y T. Cooperative task assignment and track planning for multi-UAV attack mobile targets[J]. Fire Control & Command Control, 2020, 45(9): 35-40(in Chinese). [22] SHI J K, YANG Z, ZHU J W. An auction-based rescue task allocation approach for heterogeneous multi-robot system[J]. Multimedia Tools and Applications, 2020, 79(21-22): 14529-14538. doi: 10.1007/s11042-018-7080-4 [23] MOORE B J, PASSINO K M. Distributed task assignment for mobile agents[J]. IEEE Transactions on Automatic Control, 2007, 52(4): 749-753. doi: 10.1109/TAC.2007.894545 [24] 邸斌, 周锐, 丁全心. 多无人机分布式协同异构任务分配[J]. 控制与决策, 2013, 28(2): 274-278.DI B, ZHOU R, DING Q X. Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J]. Control and Decision, 2013, 28(2): 274-278(in Chinese). [25] ZAVLANOS M M, SPESIVTSEV L, PAPPAS G J. A distributed auction algorithm for the assignment problem[C]//Proceeding of the 47th IEEE Conference on Decision and Control. Piscataway: IEEE Press, 2008: 1212-1217. [26] 颜骥, 李相民, 刘波. 考虑时序约束的多智能体协同任务分配[J]. 控制与决策, 2015, 30(11): 1999-2003.YAN J, LI X M, LIU B. Multi-agents cooperative task allocation with precedence constrains[J]. Control and Decision, 2015, 30(11): 1999-2003(in Chinese). [27] 廖沫, 陈宗基. 基于多Agent分布协同拍卖的动态目标分配算法[J]. 北京航空航天大学学报, 2007, 33(2): 180-183.LIAO M, CHEN Z J. Dynamic target assignment method based on multi-Agent decentralized cooperative auction[J]. Journal of Beijing University of Aeronautics and Astronautics, 2007, 33(2): 180-183(in Chinese). -
下载:
点击查看大图
计量
- 文章访问数: 387
- HTML全文浏览量: 116
- PDF下载量: 10
- 被引次数: 0
