ACTA AERONAUTICAET ASTRONAUTICA SINICA >
Task allocation algorithm for UAV swarm based on temporal coupling analysis
Received date: 2025-04-03
Revised date: 2025-04-17
Accepted date: 2025-05-13
Online published: 2025-05-27
Supported by
Aeronautical Science Foundation of China(2024Z023077001)
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.
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 AERONAUTICAET ASTRONAUTICA SINICA, 2026 , 47(2) : 332075 -332075 . DOI: 10.7527/S1000-6893.2025.32075
| [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. |
/
| 〈 |
|
〉 |
CJA