Integrated Consensus Framework for Task Assignment and Path Planning of a Degraded UAV Fleet

Abstract

Unmanned aerial vehicle (UAV) systems can fail during civil and military operations. This presents a significant challenge for human teleoperators (remote pilots) in determining task reallocation after member loss within the fleet. To alleviate the high cognitive load on teleoperators in critical situations, a decentralized strategy was developed to resolve the combined task assignment and vehicle routing problems. This Integrated Consensus Framework (ICF) not only solves the combined problem but also adds a unique ability to identify the loss of a vehicle and dynamically reroute agents to abandoned tasks to achieve a satisfactory solution. ICF is a two-tiered approach that combines a novel algorithm, the Caravan Auction (CarA) algorithm, with a path-planning strategy to identify when UAVs are lost and reallocate orphaned tasks. The CarA Algorithm consists of three phases: auction, consensus, and validation phases. An experiment using Monte Carlo simulations was conducted to determine the performance of ICF. Teleoperators assigned to complete multiple tasks with UAVs in dangerous environments can allow the proposed system to perform task assignments and reallocation while offering only supervisory control as needed. The results indicate this novel approach provides comparable performance to existing strategies, doing so with the addition of randomized UAV loss.

Keywords

Unmanned aircraft systems / Multi-vehicle intelligent systems / Coordinated control

Author Contributions

Conceptualization, W.T.B.; Methodology, W.T.B., G.M.N.; Software, W.T.B.; Validation, W.T.B., G.M.N., C.D.M. and A.Y.O.; Formal Analysis, W.T.B.; Investigation, W.T.B., G.M.N.; Resources, W.T.B.; Data Curation, W.T.B.; Writing—Original Draft Preparation, W.T.B., G.M.N.; Writing—Review & Editing, W.T.B., G.M.N., C.D.M. and A.Y.O.; Visualization, W.T.B.; Supervision, G.M.N.; Project Administration, W.T.B.; Funding Acquisition, W.T.B.

Ethics Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Research data is available by request to the corresponding author.

Funding

This research was funded in part by the United States Department of Defense, Naval Information Warfare Center Atlantic.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References

[1] Khan MA, Ectors W, Bellemans T, Janssens D, Wets G. UAV-based traffic analysis: A universal guiding framework based on literature survey. Transp. Res. Proc. 2017, 22, 541-550. doi:10.1016/j.trpro.2017.03.043.

[2] Szóstak M, Nowobilski T, Mahamadu A-M, Pérez DC. Unmanned aerial vehicles in the construction industry—Towards a protocol for safe preparation and flight of drones. Int. J. Intell. Unman Syst. 2023, 11, 296-316. doi:10.1108/IJIUS-05-2022-0063.

[3] Lei X, Hu X, Wang G, Luo H. A multi-UAV deployment method for border patrolling based on Stackelberg game. J. Syst. Eng. Electron. 2023, 34, 99-116. doi:10.23919/JSEE.2023.000022.

[4] Mori K, Nishira M, Nishikawa H, Tomiyama H. Exact and heuristic approaches to surveillance routing with a minimum number of drones. Drones Auton. Veh. 2024, 1, 1004. doi:10.35534/dav.2024.10004.

[5] Hu J, Yang J. Application of distributed auction to multi-UAV task assignment in agriculture. Int. J. Precis. Agric. Aviat. 2018, 1, 44-50. doi:10.33440/j.ijpaa.20180101.0008.

[6] Guebsi R, El Wai R. Leveraging drone technology for precision agriculture: A comprehensive case study in Sidi Bouzid, Tunisia. Drones Auton. Veh. 2025, 2, 10006. doi:10.70322/dav.2025.10006.

[7] Saunders J, Saeedi S, Li W. Autonomous aerial robotics for package delivery: A technical review. J. Field Robot. 2024, 41, 3-49. doi:10.1002/rob.22231.

[8] Sorbelli FB. UAV-based delivery systems: A systematic review, current trends, and research challenges. J. Auton. Transp. Syst. 2024, 1, 1-40. doi:10.1145/3649224.

[9] Nishira M, Nishikawa H, Kong X, Tomiyama H. An integer programming approach to multi-trip routing of delivery drones at load-dependent flight speed. Drones Auton. Veh. 2024, 1, 10008. doi:10.35534/dav.2024.10008.

[10] Patrinopoulou N, Daramouskas I, Meimetis D, Lappas V, Kostopoulos V. A distributed framework for persistent wildfire monitoring with fixed wing UAVs. Drones Auton. Veh. 2024, 1, 10009. doi:10.35534/dav.2024.10009.

[11] Jan GE, Lei T, Sun CC, You ZY, Luo C. On the problems of drone formation and light shows. IEEE Trans. Consum. Electron. 2024, 70, 5259-5268. doi:10.1109/TCE.2024.3421516.

[12] Wang G, Wang F, Wang J, Li M, Gai L, Xu D. Collaborative target assignment problem for large-scale UAV swarm based on two-stage greedy auction algorithm. Aerosp. Sci. Technol. 2024, 149, 109-146. doi:10.1016/j.ast.2024.109146.

[13] Dantzig GB, Ramser JH. The truck dispatching problem. Manag. Sci. 1959, 6, 80-91. doi:10.1287/mnsc.6.1.80.

[14] Psaraftis HN. Dynamic vehicle routing problems. In Vehicle Routing: Methods and Studies; Golden BL, Assad AA, Eds.; Elsevier: Amsterdam, The Netherlands, 1988; pp. 223-247.

[15] Chiang T-C, Hsu W-H. A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows. Comput. Oper. Res. 2014, 45, 25-37. doi:10.1016/j.cor.2013.11.014.

[16] Archetti C, Corberán Á, Plana I, Sanchis JM, Speranza MG. A branch-and-cut algorithm for the orienteering arc routing problem. Comput. Oper. Res. 2016, 66, 95-104. doi:10.1016/j.cor.2015.08.003.

[17] Montemanni R, Weyland D, Gambardella LM. An enhanced ant colony system for the team orienteering problem with time windows. In Proceedings of the International Symposium on Computer Science and Society, Kota Kinabalu, Malaysia, 16-17 July 2011; pp. 381-384. doi:10.1109/ISCCS.2011.95.

[18] Evers L, Glorie K, van der Ster S, Barros AI, Monsuur H. A two-stage approach to the orienteering problem with stochastic weights. Comput. Oper. Res. 2014, 43, 248-260. doi:10.1016/j.cor.2013.09.011.

[19] Moon S, Oh E, Shim DH. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments. J. Intell. Robot. Syst. 2013, 70, 303-313. doi:10.1007/s10846-012-9740-3.

[20] Góral I, Tchoń K. Lagrangian jacobian motion planning: A parametric approach. J. Intell. Robot. Syst. 2017, 85, 511-522. doi:10.1007/s10846-016-0394-4.

[21] Zengin U, Dogan A. Cooperative target pursuit by multiple UAVs in an adversarial environment. Robot. Auton. Syst. 2011, 59, 1049-1059. doi:10.1016/j.robot.2011.08.006.

[22] Frontera G, Martín DJ, Besada JA, Gu D-W. Approximate 3D euclidean shortest paths for unmanned aircraft in urban environments. J. Intell. Robot. Syst. 2017, 85, 353-368. doi:10.1007/s10846-016-0409-1.

[23] Hota S, Ghose D. Waypoint-based trajectory planning of fixed-wing MAVs in 3D space. J. Intell. Robot. Syst. 2017, 86, 95-113. doi:10.1007/s10846-016-0415-3.

[24] Koubâa A, Cheikhrouhou O, Bennaceur H, Sriti M-F, Javed Y, Ammar A. Move and improve: a market-based mechanism for the multiple depot multiple travelling salesmen problem. J. Intell. Robot. Syst. 2017, 85, 307-330. doi:10.1007/s10846-016-0400-x.

[25] Hino T, Tsuchiya T. Heuristic path planning of unmanned aerial vehicle formations. Int. J. Intell. Unman Syst. 2013, 1, 121-144. doi:10.1108/20496421311330056.

[26] Huo J, Zenkevich SL, Nazarova AV, Zhai M. Path planning based on map matching in UAV/UGV collaboration system. Int. J. Intell. Unman Syst. 2021, 9, 81-95. doi:10.1108/IJIUS-03-2019-0020.

[27] Cheng H, Page J, Olsen J. Cooperative control of UAV swarm via information measures. Int. J. Intell. Unman Syst. 2013, 1, 256-275. doi:10.1108/IJIUS-01-2013-0001.

[28] Taran B, Homaeinezhad M. Fully- and partially- distributed adaptive consensus of second-order multi-agent systems using only relative position measurements. Drones Auton. Veh. 2024, 1, 10014. doi:10.70322/dav.2024.10014.

[29] Chen J, Du C, Zhang Y, Han P, Wei W. A clustering-based coverage path planning method for autonomous heterogeneous UAVs. IEEE Trans. Intell. Transp. Syst. 2022, 23, 25546-25556. doi:10.1109/TITS.2021.3066240.

[30] Shetty VK, Sudit M, Nagi R. Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Comput. Oper. Res. 2008, 35, 1813-1828. doi:10.1016/j.cor.2006.09.013.

[31] Nanjanath M, Gini M. Repeated auctions for robust task execution by a robot team. Robot. Auton. Syst. 2010, 58, 900-909. doi:10.1016/j.robot.2010.03.011.

[32] Buer T, Kopfer H. A Pareto-metaheuristic for a bi-objective winner determination problem in a combinatorial reverse auction. Comput. Oper. Res. 2014, 41, 208-220. doi:10.1016/j.cor.2013.04.004.

[33] Duan X, Liu H, Tang H, Cai Q, Zhang F, Han X. A novel hybrid auction algorithm for multi-UAVs dynamic task assignment. IEEE Access 2020, 8, 86207-86222. doi:10.1109/ACCESS.2019.2959327.

[34] Izhboldina V, Lebedev I. Group movement of UAVs in environment with dynamic obstacles: A survey. Int. J. Intell. Unman Syst. 2023, 11, 268-284. doi:10.1108/IJIUS-06-2021-0038.

[35] Brunet L. Masters Thesis, Cambridge MA, USA, Consensus-Based Auctions for Decentralized Task Assignment. Masters Thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2008. Available online: http://hdl.handle.net/1721.1/44926 (accessed on 01 September 2025).

[36] Alighanbari M. Robust and Doctoral Dissertation, Cambridge MA, USA, Robust and Decentralized Task Assignment Algorithms for UAVs. Doctoral Dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 2007. Available online: http://dspace.mit.edu/handle/1721.1/7582 (accessed on 01 September 2025).

[37] Choi H-L, Brunet L, How JP. Consensus-based decentralized auctions for robust task allocation. IEEE Trans. Robot. 2009, 25, 912-926. doi:10.1109/TRO.2009.2022423.

[38] Zhang Y, Feng W, Shi G, Jiang F, Chowdhury M, Ling SH. UAV swarm mission planning in dynamic environment using Consensus-Based Bundle Algorithm. Sensors 2020, 20, 2307. doi:10.3390/s20082307.

[39] Chen J, Qing X, Ye F, Xiao K, You K, Sun Q. Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment. J. Supercomput. 2022, 78, 1712-1740. doi:10.1007/s11227-021-03940-z.

[40] Jung S. Real-time UAV Autonomy through Offline Calculations. Masters Thesis, Purdue University, West Lafayette, Indiana, 2010.

[41] Li W, Ren R, Shi M, Lin B, Qin K. Seeking secure adaptive distributed discrete-time observer for networked agent systems under external cyber attacks. IEEE Trans. Consum. Electron. 2025, 71, 918-930. doi:10.1109/TCE.2025.3535083.

[42] Bertsekas DP. Auction algorithms. In Encyclopedia of Optimization; Pardalos PM, Ed.; Springer: Boston, MA, USA, 2001; pp. 73-77.

[43] Rabbath CA. A finite-state machine for collaborative airlift with a formation of unmanned air vehicles. J. Intell. Robot. Syst. 2013, 70, 233-253. doi:10.1007/s10846-012-9692-7.

[44] Li W, Yue J, Shi M, Lin B, Qin K. Neural network-based dynamic target enclosing control for uncertain nonlinear multi-agent systems over signed networks. Neural Netw. 2025, 184, 107057. doi:10.1016/j.neunet.2024.107057.

[45] Campion M, Ranganathan P, Faruque S. UAV swarm communication and control architectures: A review. Unmanned Veh. Syst. 2018, 7, 93-106. doi:10.1139/juvs-2018-0009.

[46] Tahir A, Böling J, Haghbayan MH, Toivonen HT, Plosila J. Swarms of unmanned aerial vehicles—A survey. J. Ind. Inf. Integr. 2019, 16, 100106. doi:10.1016/j.jii.2019.100106.

[47] Kada B, Khalid M, Shaikh MS. Distributed cooperative control of autonomous multi-agent UAV systems using smooth control. J. Syst. Eng. Electron. 2020, 31, 1297-1307. doi:10.23919/JSEE.2020.000100.

[48] Adoni WYH, Lorenz S, Fareedh JS, Gloaguen R, Bussmann M. Investigation of autonomous multi-UAV systems for target detection in distributed environment: Current developments and open challenges. Drones 2023, 7, 263. doi:10.3390/drones7040263.

[49] Javed S, Hassan A, Ahmad R, Ahmed W, Ahmed R, Saadat A, et al. State-of-the-art and future research challenges in UAV swarms. IEEE Internet Things J. 2024, 11, 19023-19045. doi:10.1109/JIOT.2024.3364230.

[50] Alqudsi Y, Makaraci M. UAV swarms: research, challenges, and future directions. J. Eng. Appl. Sci. 2025, 72, 12. doi:10.1186/s44147-025-00582-3.

[51] Kourtis MA, Xilouris G, Oikonomakis A, Batistatos MC, Chochliouros I. Integration of Drone Connectivity in 5G: An Examination of the OASEES Framework. In Proceedings of the 2023 IEEE Future Networks World Forum (FNWF), Baltimore, MD, USA, 13-15 November 2023; pp. 1-6; doi:10.1109/FNWF58287.2023.10520379.

[52] Amponis G, Lagkas T, Zevgara M, Katsikas G, Xirofotos T, Moscholios I, et al. Drones in B5G/6G networks as flying base stations. Drones 2022, 6, 39. doi:10.3390/drones6020039.

[53] Jagatheesaperumal SK, Rahouti M, Chehri A, Xiong K, Bieniek J. Blockchain-based security architecture for unmanned aerial vehicles in B5G/6G services and beyond: A comprehensive approach. IEEE Open J. Commun. Soc. 2025. doi:10.1109/OJCOMS.2025.3528220.

[54] Hartmann K, Steup C. The vulnerability of UAVs to cyber attacks—An approach to the risk assessment. In Proceedings of the 5th International Conference on Cyber Conflict, Tallinn, Estonia, 4-7 June 2013; pp. 1-23. Available online: https://ieeexplore.ieee.org/abstract/document/6568373 (accessed on 01 September 2025).

[55] Barnawi WT. Targeting Assignment. Doctoral Dissertation, Huntsville AL, USA, Integrated Consensus-Based Frameworks for Unmanned Vehicle Routing and Targeting Assignment. Doctoral Dissertation, The University of Alabama in Huntsville, Huntsville, AL, USA, 2015. Available online: https://www.proquest.com/openview/52c5bf8a45854a246f9471cfca26bb53/1?cbl=18750&pq-origsite=gscholar (accessed on 01 September 2025).

[56] Beard R, Stepanyan V. Synchronization of information in distributed multiple vehicle coordinated control. In Proceedings of the IEEE Conference on Decision and Control, Maui, HI, USA, 9-12 December 2003; pp. 2029-2034. doi:10.1109/CDC.2003.1272913.

[57] Office of the Secretary of Defense. Unmanned Aerial Vehicle Reliability Study. 2003, Unpublished manuscript.

[58] Alighanbari M, How JP. Decentralized task assignment for unmanned aerial vehicles. In Proceedings of the 44th IEEE Conference on Decision and Control, Seville, Spain, 15 December 2005; pp. 5668-5673. doi:10.1109/CDC.2005.1583066.