International Journal of Wireless and Microwave Technologies (IJWMT)
IJWMT Vol. 16, No. 5, 8 Oct. 2026
Cover page and Table of Contents: PDF (size: 633KB)
Learning-Augmented Deterministic Task Allocation and Routing for Heterogeneous Multi-UAV Systems
PDF (633KB), PP.37-47
Views: 0 Downloads: 0
Author(s)
Index Terms
Heterogeneous UAVs, multi-UAV routing, task allocation, optimization, learning-augmented optimization, future-regret prediction
Abstract
This paper presents a learning-augmented deterministic method for heterogeneous multi-UAV task allocation and routing in static, fully observed environments. UAV-specific asymmetric path-length matrices represent the output of an offline path planner, allowing online planning to focus on assignment and route construction. The deterministic core evaluates insertions, checks energy feasibility, prioritizes tasks with few feasible UAVs, repairs blocked states, and improves completed routes. A shallow multilayer perceptron ranks feasible candidates by predicting future regret, defined as the difference between the makespan after deterministic completion and the immediate post-insertion makespan. The objective minimizes makespan first and uses aggregate route length only when makespan values are equal within the prescribed numerical tolerance. The model was trained on 12 synthetic instances and evaluated on 20 separate instances, each containing 20 tasks and four heterogeneous UAVs under uniform, clustered, and mixed layouts. It was compared with two greedy insertion heuristics, the corresponding deterministic ablation (CT-D), and a linear-regret variant. The proposed method achieved a mean makespan of 106.24 versus 107.46 for CT-D, a descriptive reduction of approximately 1.1%. Compared with CT-D, aggregate route length increased by approximately 1.5%, while mean runtime increased from 0.059 to 0.233 s. Performance improved on clustered and mixed layouts but declined slightly on uniform layouts.
Cite This Paper
Mykola Nikolaiev, Mykhailo Novotarskyi, "Learning-Augmented Deterministic Task Allocation and Routing for Heterogeneous Multi-UAV Systems", International Journal of Wireless and Microwave Technologies(IJWMT), Vol.16, No.5, pp. 37-47, 2026. DOI:10.5815/ijwmt.2026.05.03
Reference
[1]J. Song, K. Zhao, and Y. Liu, "Survey on Mission Planning of Multiple Unmanned Aerial Vehicles," Aerospace, vol. 10, no. 3, p. 208, 2023. https://doi.org/10.3390/aerospace10030208
[2]G. M. Skaltsis, H.-S. Shin, and A. Tsourdos, "A Review of Task Allocation Methods for UAVs," Journal of Intelligent & Robotic Systems, vol. 109, p. 76, 2023. https://doi.org/10.1007/s10846-023-02011-0
[3]S. A. Ghauri, M. Sarfraz, R. A. Qamar, M. F. Sohail, and S. A. Khan, "A Review of Multi-UAV Task Allocation Algorithms for a Search and Rescue Scenario," Journal of Sensor and Actuator Networks, vol. 13, no. 5, p. 47, 2024. https://doi.org/10.3390/jsan13050047
[4]M. Rinaldi, S. Wang, R. S. Geronel, and S. Primatesta, "Application of Task Allocation Algorithms in Multi-UAV Intelligent Transportation Systems: A Critical Review," Big Data and Cognitive Computing, vol. 8, no. 12, p. 177, 2024. https://doi.org/10.3390/bdcc8120177
[5]M. M. Solomon, "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, vol. 35, no. 2, pp. 254–265, 1987. https://doi.org/10.1287/opre.35.2.254
[6]J.-Y. Potvin and J.-M. Rousseau, "A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows," European Journal of Operational Research, vol. 66, no. 3, pp. 331–340, 1993. https://doi.org/10.1016/0377-2217(93)90221-8
[7]S. Røpke and D. Pisinger, "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, vol. 40, no. 4, pp. 455–472, 2006. https://doi.org/10.1287/trsc.1050.0135
[8]K. Li, "Heuristic Task Scheduling on Heterogeneous UAVs: A Combinatorial Optimization Approach," Journal of Systems Architecture, vol. 140, p. 102895, 2023. https://doi.org/10.1016/j.sysarc.2023.102895
[9]G. Binetti, D. Naso, and B. Turchiano, "Decentralized Task Allocation for Surveillance Systems with Critical Tasks," Robotics and Autonomous Systems, vol. 61, no. 12, pp. 1653–1664, 2013. https://doi.org/10.1016/j.robot.2013.06.007
[10]W. Zhao, Q. Meng, and P. W. H. Chung, "A Heuristic Distributed Task Allocation Method for Multivehicle Multitask Problems and Its Application to Search and Rescue Scenario," IEEE Transactions on Cybernetics, vol. 46, no. 4, pp. 902–915, 2016. https://doi.org/10.1109/TCYB.2015.2418052
[11]H.-L. Choi, L. Brunet, and J. P. How, "Consensus-Based Decentralized Auctions for Robust Task Allocation," IEEE Transactions on Robotics, vol. 25, no. 4, pp. 912–926, 2009. https://doi.org/10.1109/TRO.2009.2022423
[12]F. Ye, J. Chen, Q. Sun, Y. Tian, and T. Jiang, "Decentralized Task Allocation for Heterogeneous Multi-UAV System with Task Coupling Constraints," The Journal of Supercomputing, vol. 77, pp. 111–132, 2021. https://doi.org/10.1007/s11227-020-03264-4
[13]J. Chen, X. Qing, F. Ye, K. Xiao, K. You, and Q. Sun, "Consensus-Based Bundle Algorithm with Local Replanning for Heterogeneous Multi-UAV System in the Time-Sensitive and Dynamic Environment," The Journal of Supercomputing, vol. 78, pp. 1712–1740, 2022. https://doi.org/10.1007/s11227-021-03940-z
[14]W. Cui, R. Li, Y. Feng, and Y. Yang, "Distributed Task Allocation for a Multi-UAV System with Time Window Constraints," Drones, vol. 6, no. 9, p. 226, 2022. https://doi.org/10.3390/drones6090226
[15]E. Edison and T. Shima, "Integrated Task Assignment and Path Optimization for Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms," Computers & Operations Research, vol. 38, no. 1, pp. 340–356, 2011. https://doi.org/10.1016/j.cor.2010.06.001
[16]M. Cao, J. Peng, L. Yang, and Y. Yang, "Multi-UAV Task Allocation and Path Planning in Emergency Rescue Scenarios with Uncertain Requirements," Journal of Industrial and Management Optimization, vol. 21, no. 10, pp. 6107–6133, 2025. https://doi.org/10.3934/jimo.2025124
[17]N. Dong, S. Liu, and X. Mai, "Communication-Efficient Heterogeneous Multi-UAV Task Allocation Based on Clustering," Computer Communications, vol. 229, p. 107986, 2025. https://doi.org/10.1016/j.comcom.2024.107986
[18]W. Wu, L. Zhang, J. Le, and Z. Lu, "Integrated Method for Multi-UAV Task Assignment and Trajectory Planning with Deadlock Based on Three-Dimensional Dubins Path," Scientific Reports, vol. 15, p. 24152, 2025. https://doi.org/10.1038/s41598-025-09753-x
[19]Y. Wang, C. Wang, and S. Ren, "A Two-Level Clustered Consensus-Based Bundle Algorithm for Dynamic Heterogeneous Multi-UAV Multi-Task Allocation," Sensors, vol. 25, no. 21, p. 6738, 2025. https://doi.org/10.3390/s25216738
[20]B. Fan, Y. Bo, and X. Wu, "Learning Improvement Heuristics for Multi-Unmanned Aerial Vehicle Task Allocation," Drones, vol. 8, no. 11, p. 636, 2024. https://doi.org/10.3390/drones8110636
[21]S. Zhang, C. Hu, D. Zhao, K. Yang, Z. Xu, and M. Li, "A Two-Stage Multi-UAV Task Allocation Approach Based on Graph Theory and a Learning-Inspired Immune Algorithm," Drones, vol. 9, no. 9, p. 599, 2025. https://doi.org/10.3390/drones9090599
[22]M. Nikolaiev, M. Novotarskyi, and A. Volokyta, "A Novel Hybrid Differential Evolution and Enhanced Whale Optimization Algorithm for UAV Path Planning," International Journal of Information Technology and Computer Science, vol. 17, no. 6, pp. 109–126, 2025. https://doi.org/10.5815/ijitcs.2025.06.06
[23]B. Zhang, K. Huang, Y. Chen, and D. Yang, "Task Allocation and Trajectory Optimization for Multi-UAV Cargo Systems with Cellular-Connected Constraints," IET Communications, vol. 19, no. 1, 2025. https://doi.org/10.1049/cmu2.70106
[24]Y. Song, Z. Ma, N. Chen, S. Zhou, and S. Srigrarom, "Comparative Analysis of Centralized and Distributed Multi-UAV Task Allocation Algorithms: A Unified Evaluation Framework," Drones, vol. 9, no. 8, p. 530, 2025. https://doi.org/10.3390/drones9080530