基于时序耦合分析的无人机集群任务分配方法

doi:10.7527/S1000-6893.2025.32075

Abstract

Abstract:

With the increasing scale of UAV swarm and the growing complexity of mission scenarios， designing efficient task allocation algorithms has become a significant challenge for swarm applications. To address the allocation failures and conflicts caused by cross-queue influences in temporal task allocation for UAV swarm， a Temporal Coupling Analysis-based Task Allocation method （TCATA） is proposed. Firstly， a task allocation model considering UAV payloads， task requirements， and task temporal constraints is established. The impact of task temporal coupling constraints under the market mechanism is analyzed from two aspects： performance function design and performance validity. Next， a local adjustment set is constructed for each UAV within the swarm， and a global adjustment set is obtained through communication consensus. Then， based on the performance magnitude and conflict relationships of each adjustment， the global adjustment scheme decision problem is modeled as a maximum weighted clique problem and solved by a greedy algorithm by each UAV. Finally， the executors of the tasks are determined and the global task assignment result is updated. Simulation experiments demonstrate that in solving temporal task assignment problems with hundreds of UAVs and tasks considering communication delays， TCATA significantly outperforms distributed genetic algorithms in both efficiency and performance metrics. Compared with the CBBA-TCC and CNP algorithm， TCATA achieves marginally superior performance while reducing executing time and iteration number by more than 50%， validating its effectiveness in large-scale sequential task allocation.

Key words: unmanned aerial vehicles swarm, temporal task coupling constraint, distributed task allocation, maximum weighted clique, market mechanism

CLC Number:

V249

Haoyu WANG, Zexu ZHANG, Shan WEN, Jinlong LIU, Beixiao ZHU, Weimin BAO. Task allocation algorithm for UAV swarm based on temporal coupling analysis[J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(2): 332075.

Figures/Tables 14

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Table 1

Algorithm performance variation with α

$α$	计算时间/s	迭代次数	运行时间/s	求解指标/s
1	0.151	22	0.811	371.10
2	0.138	14	0.558	371.70
3	0.172	13	0.562	371.20
4	0.212	14	0.632	370.25
5	0.232	11	0.562	372.00
10	0.519	7	0.729	371.50

Table 1

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

References 28

[1]	王祥科，刘志宏，丛一睿，等. 小型固定翼无人机集群综述和未来发展［J］. 航空学报， 2020， 41（4）： 023732.
	WANG X K， LIU Z H， CONG Y R， et al. Miniature fixed-wing UAV swarms： Review and outlook［J］. Acta Aeronautica et Astronautica Sinica， 2020， 41（4）： 023732 （in Chinese）.
[2]	BINETTI G， NASO D， TURCHIANO B. Decentralized task allocation for surveillance systems with critical tasks［J］. Robotics and Autonomous Systems， 2013， 61（12）： 1653-1664.
[3]	TURNER J， MENG Q G， SCHAEFER G， et al. Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system［J］. IEEE Transactions on Cybernetics， 2018， 48（9）： 2583-2597.
[4]	WANG Z T， ZHENG M F， GUO J S， et al. Uncertain UAV ISR mission planning problem with multiple correlated objectives［J］. Journal of Intelligent & Fuzzy Systems， 2017， 32（1）： 321-335.
[5]	SURESH M， GHOSE D. UAV grouping and coordination tactics for ground attack missions［J］. IEEE Transactions on Aerospace and Electronic Systems， 2012， 48（1）： 673-692.
[6]	BAI X S， FIELBAUM A， KRONMÜLLER M， et al. Group-based distributed auction algorithms for multi-robot task assignment［J］. IEEE Transactions on Automation Science and Engineering， 2023， 20（2）： 1292-1303.
[7]	伍国华，王天宇. 基于自适应模拟退火的大规模星座测控资源调度算法［J］. 航空学报， 2023， 44（12）： 327759.
	WU G H， WANG T Y. Large-scale constellation TT & C resource scheduling algorithm based on adaptive simulated annealing［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（12）： 327759 （in Chinese）.
[8]	GERKEY B P， MATARIĆ M J. A formal analysis and taxonomy of task allocation in multi-robot systems［J］. The International Journal of Robotics Research， 2004， 23（9）： 939-954.
[9]	KORSAH G A， STENTZ A， DIAS M B. A comprehensive taxonomy for multi-robot task allocation［J］. International Journal of Robotics Research， 2013， 32（12）： 1495-1512.
[10]	NUNES E， MANNER M， MITICHE H， et al. A taxonomy for task allocation problems with temporal and ordering constraints［J］. Robotics and Autonomous Systems， 2017， 90： 55-70.
[11]	GAO X H， WANG L， YU X Y， et al. Conditional probability based multi-objective cooperative task assignment for heterogeneous UAVs［J］. Engineering Applications of Artificial Intelligence， 2023， 123： 106404.
[12]	ZHANG R P， FENG Y X， YANG Y K， et al. A deadlock-free hybrid estimation of distribution algorithm for cooperative multi-UAV task assignment with temporally coupled constraints［J］. IEEE Transactions on Aerospace and Electronic Systems， 2023， 59（3）： 3329-3344.
[13]	张安，杨咪，毕文豪，等. 基于多策略GWO算法的不确定环境下异构多无人机任务分配［J］. 航空学报， 2023， 44（8）： 327115.
	ZHANG A， YANG M， BI W H， et al. Task allocation of heterogeneous multi-UAVs in uncertain environment based on multi-strategy integrated GWO［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（8）： 327115 （in Chinese）.
[14]	朱云冲，梁彦刚，黎克波，等. 基于PSO和RRT的智能弹群任务分配算法［J］. 航空学报， 2023， 44（S1）： 727354.
	ZHU Y C， LIANG Y G， LI K B， et al. Task allocation algorithm of intelligent bomb group based on PSO and RRT［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（S1）： 727354 （in Chinese）.
[15]	贾高伟，王建峰. 无人机集群任务规划方法研究综述［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）.
[16]	CHOUDHURY S， GUPTA J K， KOCHENDERFER M J， et al. Dynamic multi-robot task allocation under uncertainty and temporal constraints［J］. Autonomous Robots， 2022， 46（1）： 231-247.
[17]	曹严，龙腾，孙景亮，等. 非死锁合同网协议驱动的多机分布式时序任务分配［J］. 宇航学报， 2022， 43（5）： 675-684.
	CAO Y， LONG T， SUN J L， et al. Multi-UAV distributed task allocation with precedence constraints driven by deadlock-free contract net protocol［J］. Journal of Astronautics， 2022， 43（5）： 675-684 （in Chinese）.
[18]	高程，都延丽，步雨浓，等. 基于顺序扩展一致性包算法的多无人机分布式任务分配［J］. 控制与决策， 2023， 38（11）： 3242-3250.
	GAO C， DU Y L， BU Y N， et al. Distributed task allocation of multiple UAVs based on sequential extended consensus based bundle algorithm［J］. Control and Decision， 2023， 38（11）： 3242-3250 （in Chinese）.
[19]	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.
[20]	YE F， CHEN J， SUN Q， et al. Decentralized task allocation for heterogeneous multi-UAV system with task coupling constraints［J］. The Journal of Supercomputing， 2021， 77（1）： 111-132.
[21]	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）： 902-915.
[22]	翟政，何明，徐鹏，等. 基于市场机制的无人集群任务分配研究综述［J］. 计算机应用研究， 2023， 40（7）： 1921-1928.
	ZHAI Z， HE M， XU P， et al. Research review of task allocation for unmanned swarm based on market mechanism［J］. Application Research of Computers， 2023， 40（7）： 1921-1928 （in Chinese）.
[23]	QUINTON F， GRAND C， LESIRE C. Market approaches to the multi-robot task allocation problem： A survey［J］. Journal of Intelligent & Robotic Systems， 2023， 107（2）： 29.
[24]	WU Q H， HAO J K. A review on algorithms for maximum clique problems［J］. European Journal of Operational Research， 2015， 242（3）： 693-709.
[25]	HUA G， LIAO H， ZHANG H J， et al. Robust ENF estimation based on harmonic enhancement and maximum weight clique［J］. IEEE Transactions on Information Forensics and Security， 2021， 16： 3874-3887.
[26]	ÖSTERGÅRD P R J. A fast algorithm for the maximum clique problem［J］. Discrete Applied Mathematics， 2002， 120（1-3）： 197-207.
[27]	徐杰，吴蔚楠，龚春林. 多无人机任务分配/航迹规划的一体化求解方法［J］. 宇航学报， 2023， 44（12）： 1860-1870.
	XU J， WU W N， GONG C L. Integrated solution method for multi-UAV task assignment and trajectory planning［J］. Journal of Astronautics， 2023， 44（12）： 1860-1870 （in Chinese）.
[28]	TAN X P， ZUO Z， SU S J， et al. Performance analysis of routing protocols for UAV communication networks［J］. IEEE Access， 2020， 8： 92212-92224.

Task allocation algorithm for UAV swarm based on temporal coupling analysis

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 28

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	. Distributed Task Allocation Method for Scalable Heterogeneous Swarm [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[2]	Mian GONG, Yinhui ZHANG, Zifen HE, Guangchen CHEN, Rui ZHANG. Instance segmentation of dual-source geolocation perception for GPS reject environmental aerial vehicle [J]. Acta Aeronautica et Astronautica Sinica, 2026, 47(2): 332120-332120.
[3]	. Distributed Consensus-Based Cooperative Passive Positioning with Multi-Source Information Fusion [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[4]	. An integrated intelligent decision-making algorithm for penetration and strike considering the field of view angle constraint [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[5]	. Aerodynamic and flight control characteristics of flying boom based on wind tunnel tests [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[6]	. An intelligent modeling method for aircraft formation behaviors integrating LLM technology [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[7]	. Enhanced ERG-based Control Framework： Module Design and Experimental Validation [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[8]	. Hierarchical fault-tolerant formation control for unmanned helicopters based on the fully actuated system approach [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[9]	. Distributed Safety Cooperative Control for Multiple UAVs under Multi-Source Risks [J]. Acta Aeronautica et Astronautica Sinica, 0, (): 1-0.
[10]	Zhihao HE, Peng KOU, Bohua LIANG, Deliang LIANG. Powered yaw predictive control of distributed electric propulsion aircraft considering slipstream effects [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(S1): 732305-732305.
[11]	Chuanjin DAI, Peijie QIN, Lin LI, Bo ZANG. A real-time high-precision frequency estimation algorithm for Starlink signals with CPU+GPU parallel acceleration [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(24): 332038-332038.
[12]	Erchao RONG, Yuying ZHANG, Junning LIANG, Ximin LYU. Neural-network aerodynamics-based NMPC trajectory tracking control for a tail-sitter VTOL UAV [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(24): 331995-331995.
[13]	Guocheng YAN, Honglun WANG, Yanxiang WANG, Yuebin LUN, Junfan ZHU. Prescribed performance anti-swing control for wing rotation process of UAV towed aerial recovery [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(24): 331840-331840.
[14]	Jiong HE, Binwu REN, Siliang DU, Yousong XU, Bo WANG. Adaptive attitude control for tilt-quadrotor UAV based on ADRC-RBF [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(S1): 732189-732189.
[15]	Pan ZHOU, Ni LI, Jiangtao HUANG, Qinglin YANG, Yunxiao LIAN. Autonomous decision-making in close-range game under imperfect information for unmanned aerial vehicles [J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(S1): 732215-732215.