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

doi:10.7527/S1000-6893.2025.32075

电子电气工程与控制

本期目录 | 过刊浏览 | 高级检索

前一篇 | 后一篇

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

王浩宇¹, 张泽旭¹(), 闻单¹, 刘金龙¹, 朱倍孝², 包为民³

^1.哈尔滨工业大学航天学院，哈尔滨 150001
^2.上海科技大学信息科学与技术学院，上海 201210
^3.中国航天科技集团有限公司科学技术委员会，北京 100048

收稿日期:2025-04-03 修回日期:2025-04-17 接受日期:2025-05-13 出版日期:2025-05-28 发布日期:2025-05-27
通讯作者: 张泽旭 E-mail:zexuzhang@hit.edu.cn
基金资助:
航空科学基金(2024Z023077001)

Task allocation algorithm for UAV swarm based on temporal coupling analysis

Haoyu WANG¹, Zexu ZHANG¹(), Shan WEN¹, Jinlong LIU¹, Beixiao ZHU², Weimin BAO³

^1.School of Astronautics，Harbin Institute of Technology，Harbin 150001，China
^2.School of Information Science and Technology，ShanghaiTech University，Shanghai 201210，China
^3.Corporation Science and Technology Committee，China Aerospace Science and Technology，Beijing 100048，China

Received:2025-04-03 Revised:2025-04-17 Accepted:2025-05-13 Online:2025-05-28 Published:2025-05-27
Contact: Zexu ZHANG E-mail:zexuzhang@hit.edu.cn
Supported by:
Aeronautical Science Foundation of China(2024Z023077001)

摘要/Abstract

摘要：

随着集群规模的增加和任务场景的复杂化，如何设计高效的任务分配算法已是无人机集群应用的巨大挑战。针对无人机集群对时序任务分配中因跨队列影响导致的分配效能失效和冲突问题，提出一种基于时序耦合分析的任务分配方法（TCATA）。首先，建立考虑无人机载荷、任务需求和任务时序约束的任务分配模型，并从效能函数设计和效能有效性2个方面对市场机制下任务时序耦合约束的影响进行分析；其次，构造集群内各无人机局部调整方案集，并通过通讯一致性获取全局调整方案集；随后，各无人机基于各调整方案效能大小和冲突关系，将全局调整方案集的决策问题建模为最大加权团问题，并采用贪婪算法进行求解；最终，确定任务的执行者并更新全局任务分配结果。仿真实验表明，在考虑通信延迟时间的情况下，求解无人机数和任务数均过百的大规模时序任务分配问题时，TCATA在求解效率和指标上显著优于分布式遗传算法，和时序一致性任务包算法和合同网算法相比，求解指标略优，但运行时间和迭代次数低于CBBA-TCC和CNP的50%，验证了TCATA求解大规模时序任务分配问题的有效性。

关键词: 无人机集群, 时序任务耦合约束, 分布式任务分配, 最大加权团, 市场机制

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

中图分类号:

V249

王浩宇, 张泽旭, 闻单, 刘金龙, 朱倍孝, 包为民. 基于时序耦合分析的无人机集群任务分配方法[J]. 航空学报, 2026, 47(2): 332075.

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.

图/表 14

图 1

图 2

图 3

图 4

图 5

图 6

图 7

图 8

表 1

算法性能随α的变化

$α$	计算时间/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

表 1

图 9

图 10

图 11

图 12

图 13

参考文献 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.

E-mail：hkxb@buaa.edu.cn

关于我们

期刊社服务

专业学科

封面文章

友情链接

主管单位：中国科学技术协会主办单位：中国航空学会北京航空航天大学

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

Task allocation algorithm for UAV swarm based on temporal coupling analysis

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 28

相关文章 15

编辑推荐

Metrics

本文评价

[1]	赵良瑾, 仝昊楠, 苑子杨, 李昀镀, 张晓典, 成培瑞. 无人机集群的干扰管理：机理、技术与挑战[J]. 航空学报, 2025, 46(23): 632022-632022.
[2]	李坤, 布树辉, 李佳朋, 王俱博玺, 韩鹏程, 李霄翰, 李浩玮. 基于单目视觉与测距信息的无人机集群定位方法[J]. 航空学报, 2025, 46(11): 531281-531281.
[3]	郭廷宇, 闫溟, 解春雷. 聚合-分体飞行器气动特性[J]. 航空学报, 2024, 45(S1): 730596-730596.
[4]	王传云, 苏阳, 王琳霖, 王田, 王静静, 高骞. 面向反制无人机集群的多目标连续鲁棒跟踪算法[J]. 航空学报, 2024, 45(7): 329017-329017.
[5]	蔡云鹏, 周大鹏, 丁江川. 具有防撞安全约束的无人机集群智能协同控制[J]. 航空学报, 2024, 45(5): 529683-529683.
[6]	於志文, 孙卓, 程岳, 郭斌. 智能无人机集群协同感知计算研究综述[J]. 航空学报, 2024, 45(20): 630912-630912.
[7]	何明, 陈浩天, 韩伟, 邓成, 段海滨. 无人机仿鸟群协同控制发展现状及关键技术[J]. 航空学报, 2024, 45(20): 29946-029946.
[8]	刘伟, 张琳, 王代强, 孟宪良, 张搏. 激光武器反无人机集群作战运用及关键技术[J]. 航空学报, 2024, 45(12): 329457-329457.
[9]	文超, 董文瀚, 解武杰, 蔡鸣, 刘日. 基于回访机制的无人机集群分布式协同区域搜索方法[J]. 航空学报, 2023, 44(11): 327561-327561.
[10]	苏翎菲, 化永朝, 董希旺, 任章. 人与无人机集群多模态智能交互方法[J]. 航空学报, 2022, 43(S1): 727001-727001.
[11]	刘雷, 刘大卫, 王晓光, 陈俊男, 刘东兴. 无人机集群与反无人机集群发展现状及展望[J]. 航空学报, 2022, 43(S1): 726908-726908.
[12]	徐广通, 王祝, 曹严, 孙景亮, 龙腾. 动态优先级解耦的无人机集群轨迹分布式序列凸规划[J]. 航空学报, 2022, 43(2): 325059-325059.
[13]	姜龙亭, 魏瑞轩, 张启瑞, 王栋. 基于群智机理的集群防碰撞控制[J]. 航空学报, 2020, 41(S2): 724294-724294.
[14]	唐帅文, 周志杰, 姜江, 曹友, 陈媛, 叶燕清. 考虑扰动的无人机集群协同态势感知一致性评估[J]. 航空学报, 2020, 41(S2): 724233-724233.
[15]	徐磊, 周藜莎, 李仁俊, 顾村锋. 毫米波波束编码技术在无人机智能集群中的应用[J]. 航空学报, 2020, 41(S1): 723754-723754.