信息重传与丢包补偿的多无人机分布式任务分配方法

doi:10.12382/bgxb.2022.1180

摘要/Abstract

摘要：

针对通信丢包导致的多机分布式任务分配方法收敛速度慢、通信负载高等问题,提出信息重传与丢包补偿的分布式任务分配方法。设计机间信息重传机制,各机依据通信状态调整任务信息重传次数,有效降低数据丢包概率。给出考虑信息重传下分配算法收敛迭代规律,证明了重传机制对分配算法收敛的增速效果。为进一步降低通信冗余,提出丢包估计分布式任务分配(LE-DTA)算法,利用估计信息补偿丢包数据参与分布式任务分配过程,降低了机间通信传输需求,并证明了LE-DTA算法的收敛性。仿真对比结果表明:信息重传机制改进的一致性束算法(CBBA)能够有效提升算法收敛速度,但机间通信负载较高;LE-DTA算法在高丢包率、低网络拓扑连通度场景下具有明显的性能优势。

关键词: 无人机, 分布式任务分配, 通信丢包, 数据补偿

Abstract:

To address issues such as rapid convergence and communication burden caused by communication package loss, a distributed task allocation algorithm based on information retransmission and package loss compensation is proposed. An inter-UAV information retransmission mechanism is designed. Each UAV adjusts the number of task information retransmissions according to the communication quality, effectively reducing the probability of package loss. The convergence iteration rule of the allocation algorithm with the retransmission mechanism is raised, and the acceleration effect of the retransmission mechanism on the algorithm's convergence is proved. The loss estimation distributed task allocation (LE-DTA) algorithm is proposed to further reduce communication redundancy. The estimation information is used to compensate for lost packages to participate in the distributed task allocation process, which lowers the communication requirements between UAVs. The convergence of the LE-DTA algorithm is then proved. The simulation comparison results show that the improved Consensus-Based Bundle Algorithm (CBBA) with the information retransmission mechanism can effectively accelerate the convergence process, but the disadvantage is the high communication load between UAVs, while the LE-DTA has obvious performance advantages in high package loss rates and low network connectivity scenarios.

Key words: unmanned aerial vehicle, distributed task allocation, package loss, data compensation

中图分类号:

曹严, 龙腾, 孙景亮, 周禹泽. 信息重传与丢包补偿的多无人机分布式任务分配方法[J]. 兵工学报, 2023, 44(9): 2697-2708.

CAO Yan, LONG Teng, SUN Jingliang, ZHOU Yuze. Distributed Task Allocation Algorithm for Multiple Unmanned Aerial Vehicle Based on Information Retransmission and Package Loss Compensation[J]. Acta Armamentarii, 2023, 44(9): 2697-2708.

图/表 7

图1 丢包与对应预估无人机示意图

Fig.1 Package loss and corresponding estimated UAV

图2 丢包估计分布式任务分配算法伪代码

Fig.2 Pseudocode of LE-DTA algorithm

表1 各算法信息交互内容及包长

Table 1 Message content and package length of each algorithm

算法	信息包内容	信息包包长/bit
CBBA、PI	获胜标书列表、获胜无人机列表、时间戳列表	2176
RS-CBBA、LE-DTA、HIPC	获胜标书列表、获胜无人机列表、时间戳列表、各机位置坐标	3072
DGA	当前最优分配方案、各机位置坐标	2048

表2 不同拓扑下无人机位置(想定Ⅰ)

Table 2 UAV positions with different topologies (scenario Ⅰ)

拓扑类型	无人机坐标位置/m
一字型	[300, 1500] [1100, 1500] [1900, 1500] [2700, 1500]	0.59
中心辐射型	[808, 1100] [1500, 1500] [2192, 1100] [1500, 2300]	1
环型	[1100, 1100] [1900, 1100] [1900, 1900] [1100, 1900]	2
全连通型	[1400, 1400] [1600, 1400] [1600, 1600] [1400, 1600]	4

图3 通信传输量对比结果(想定Ⅰ)

Fig.3 Comparison of communication overload (scenario Ⅰ)

图4 收敛耗时对比结果(想定Ⅰ)

Fig.4 Comparison of convergence time (scenario Ⅰ)

图5 算法性能对比结果(想定Ⅱ)

Fig.5 Comparison of algorithm performance (scenario Ⅱ)

参考文献 25

[1]	甄子洋, 江驹, 孙绍山, 等. 无人机集群作战协同控制与决策[M]. 北京: 国防工业出版社, 2022.
	ZHEN Z Y, JIANG J, SUN S S, et al. Cooperative control and decision of UAV swarm operations[M]. Beijing: National Defense Industry Press, 2022. (in Chinese)
[2]	范博洋, 赵高鹏, 薄煜明, 等. 多目标空地异构无人系统协同任务分配方法[J]. 兵工学报, 2023, 44 (6): 1564-1575. doi: 10.12382/bgxb.2022.0095
	FAN B Y, ZHAO G P, BO Y M, et al. Collaborative task allocation method for multi-target aerial-ground heterogeneous unmanned system[J]. Acta Armamentarii, 2023, 44 (6):1564-1575. (in Chinese)
[3]	KORSAH G A, STENTZ A, DIAS M B. A comprehensive taxonomy for multi-robot task allocation[J]. The International Journal of Robotics Research, 2013, 32(12): 1495-1512. doi: 10.1177/0278364913496484 URL
[4]	CHOI H L, BRUNET L, HOW J P. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Transactions on Robotics, 2009, 25(4): 912-926. doi: 10.1109/TRO.2009.2022423 URL
[5]	JOHNSON L, CHOI H L, HOW J P. The hybrid information and plan consensus algorithm with imperfect situational awareness[M]//Distributed Autonomous Robotic Systems. Tokyo,Japan:Springer, 2016: 221-233.
[6]	ZHAO W Q, MENG Q G, CHUNG P W H. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario[J]. IEEE Transactions on Cybernetics, 2016, 46(4).
[7]	CHOPRA S, NOTARSTEFANO G, RICE M, et al. A distributed version of the hungarian method for multirobot assignment[J]. IEEE Transactions on Robotics, 2017, 33(4): 932-947. doi: 10.1109/TRO.2017.2693377 URL
[8]	GAO G Q, MEI Y, JIA Y H, et al. Adaptive coordination ant colony optimization for multipoint dynamic aggregation[J]. IEEE Transactions on Cybernetics, 2022, 52(8): 7362-7376. doi: 10.1109/TCYB.2020.3042511 URL
[9]	PATEL R, RUDNICK-COHEN E, AZARM S, et al. Decentralized task allocation in multi-agent systems using a decentralized genetic algorithm[C]//Proceedings of 2020 IEEE International Conference on Robotics and Automation. Paris, France:IEEE, 2020: 3770-3776.
[10]	ISMAIL S, SUN L. Decentralized hungarian-based approach for fast and scalable task allocation[C]//Proceedings of 2017 International Conference on Unmanned Aircraft Systems. Miami, FL, US:IEEE, 2017:23-28.
[11]	JOHNSON L, PONDA S, CHOI H L, et al. Improving the efficiency of a decentralized tasking algorithm for UAV teams with asynchronous communications[C]//Proceedings of AIAA Guidance, Navigation, and Control Conference. Toronto, Ontario, Canada:ARC, 2010:8421.
[12]	陈璞, 严飞, 刘钊, 等. 通信约束下异构多无人机任务分配方法[J]. 航空学报, 2021, 42(8):306-319.
	CHEN P, YAN F, LIU Z, et al. Communication-constrained task allocation of heterogeneous UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42(8):306-319. (in Chinese)
[13]	王孟阳, 张栋, 唐硕, 等. 基于动态联盟策略的无人机集群在线任务规划方法[J]. 兵工学报, 2022, 44(8):2207-2223.
	WANG M Y, ZHANG D, TANG S, et al. UAV swarm cooperative mission planning method based on dynamic allocation strategy[J]. Acta Armamentarii, 2022, 44(8):2207-2223. (in Chinese)
[14]	王琳蒙, 王玉惠, 陈谋, 等. 基于改进麻雀算法的非完备信息博弈策略研究[J]. 吉林大学学报(信息科学版), 2022, 40(4): 589-599.
	WANG L M, WANG Y H, CHEN M, et al. Strategy research of incomplete information based on improved sparrow algorithm[J]. Journal of Jilin University(Information Science Edition), 2022, 40(4):589-599. (in Chinese)
[15]	OTTE M, KUHLMAN M J, SOFGE D. Auctions for multi-robot task allocation in communication limited environments[J]. Autonomous Robots, 2020, 44(3): 547-584. doi: 10.1007/s10514-019-09828-5
[16]	HAN Z, SWINDLEHURST A L, LIU K J R. Optimization of MANET connectivity via smart deployment/movement of unmanned air vehicles[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7): 3533-3546. doi: 10.1109/TVT.2009.2015953 URL
[17]	NAYAK S, YEOTIKAR S, CARRILLO E, et al. Experimental comparison of decentralized task allocation algorithms under imperfect communication[J]. IEEE Robotics and Automation Letters, 2020, 5(2): 572-579. doi: 10.1109/LSP.2016. URL
[18]	CARRILLO E, YEOTIKAR S, NAYAK S, et al. Communication-aware multi-agent metareasoning for decentralized task allocation[J]. IEEE Access, 2021, 9: 98712-98730. doi: 10.1109/ACCESS.2021.3096229 URL
[19]	MAZDIN P, RINNER B. Distributed and communication-aware coalition formation and task assignment in multi-robot systems[J]. IEEE Access, 2021, 9: 35088-35100. doi: 10.1109/Access.6287639 URL
[20]	符小卫, 冯鹏, 高晓光, 等. 通信延迟约束下多无人机任务指派冲突消解[J]. 系统工程与电子技术, 2018, 40(7): 1491-1497.
	FU X W, FENG P, GAO X G, et al. Conflict resolution in multi-UAV cooperative tasks assignment with communication delay[J]. Systems Engineering and Electronics, 2018, 40(7): 1491-1497. (in Chinese)
[21]	WANG N, LI Z, LIANG X L, et al. Cooperative target search of UAV swarm with communication distance constraint[J]. Mathematical Problems in Engineering, 2021, 2021(5): 1-14.
[22]	RAJA S, HABIBI G, HOW J P. Communication-aware consensus-based decentralized task allocation in communication constrained environments[J]. IEEE Access, 2022, 10: 19753-19767. doi: 10.1109/ACCESS.2021.3138857 URL
[23]	马培蓓, 隋江波, 纪军, 等. 智能无人集群系统协同控制关键问题分析[J]. 战术导弹技术, 2022(4): 124-131.
	MA P B, SUI J B, JI J, et al. Analysis on key problems of cooperative control of intelligent unmanned cluster system[J]. Tactical Missile Technology, 2022(4): 124-131. (in Chinese)
[24]	CHEN Z. On dubins paths to a circle[J]. Automatica, 2020, 117:108996. doi: 10.1016/j.automatica.2020.108996 URL
[25]	KOPEIKIN A, PONDA S S, JOHNSON L B, et al. Multi-UAV network control through dynamic task allocation: ensuring data-rate and bit-error-rate support[C]//Proceedings of 2012 IEEE GLOBECOM Workshops.Anaheim, CA, US:IEEE, 2012:1579-1584.