Distributed Task Allocation for UAV Swarms with Limited Communication

Mutullah Eşer; Asım Egemen Yılmaz

doi:10.35377/saucis...1461626

EN

Distributed Task Allocation for UAV Swarms with Limited Communication

Abstract

Unmanned aerial vehicle (UAV) swarms have become increasingly indispensable in both military and civilian operations. Task allocation, a crucial aspect of UAV swarm autonomy, involves assigning sequential tasks to each aircraft based on environmental constraints and swarm status. While many task allocation algorithms assume reliable communication among agents, real-world environments often present challenges such as limited bandwidth and message interference. This study presents a new distributed task assignment algorithm for heterogeneous UAV swarms, addressing various task constraints. The proposed auction-based method optimizes total cost, ensures fair workload distribution, and minimizes message size through a two-stage auction process. Comparative evaluations with existing algorithms like CBBA and the central Hungarian algorithm, under the Bernoulli communication model, consider factors such as total task cost, message size, unassignable tasks, and conflict assignments. Results indicate the proposed algorithm's effectiveness in smooth communication environments and its potential advantage in low-bandwidth environments. However, it also highlights potential conflicts in scenarios with communication disruptions. To address deviations due to communication quality, Signal-to-Noise Ratio (SNR) values are monitored throughout task execution.

Keywords

References

R. Bouffanais, “Design and control of swarm dynamics,” Springer, Singapore, 2016.
H. Geer, C. Bolkcom, “Unmanned aerial vehicles: Background and issues for Congress,” CRS Report for Congress, CRS Report No. RL31872, 2003.
K. P. Valavanis, G.J. Vachtsevanos, “Handbook of Unmanned Aerial Vehicles-5,” New York, NY, USA: Springer, 2014.
M. R. Brust, G. Danoy, D.H. Stolfi, P. Bouvry, “Swarm-based counter UAV defense system,” Discover Internet of Things, vol.1 no.1, pp.1-19, 2016.
E. Şahin, “Swarm Robotics: From Sources of Inspiration to Domains of Application,” In: Lecture Notes in Computer Science, vol 3342. Springer, Berlin, Heidelberg 2005.
H. David, “Indian Army Shows Off Drone Swarm of Mass Destruction,” Forbes, January 19, 2021.
A. Bürkle, F. Segor, M. Kollmann, “Towards Autonomous Micro UAV Swarms,” Journal of Intelligent & Robotic Systems, vol. 61, pp. 339–353, 2010.
F. Denis, “Russia Develops Molniya Swarming UAV Concept,” Defence Weekly, March, 2021.

P. Akshara, “Expanding Focus: Rotary-Wing Swarming UAVs from China’s Ziyan,” International Defence Review, September 23, 2021.
R. M. Zlot, “An auction-based approach to complextask allocation for multirobot teams,” PhD Dissertation, Carnegie Mellon University, 2006.
C. Tovey, M. Lagoudakis, S. Jain, “The generation of bidding rules for auction-based robot coordination,” Multi-Robot Systems, vol.3, no.1, pp.3-14, 2005.
M. Dias, A. Stentz, “A free market architecture for distributed control of a multirobot system,” in: Conference on Intelligent Autonomous, 2000.
Z. Kallenborn, “Infoswarms:drone swarms and information warfare,” The US Army War College Quarterly: Parameters, vol.52, no.2, pp.87–102, 2022.
B. T. Clough, “UAV swarming? So what are those swarms, what are the implications, and how do we handle them?” in AUVSI Unmanned System Conf., Orlando, FL, 2002.
R. C. Arkin, M. Egerstedt, “Temporal heterogeneity and the value of slowness in robotic systems,” in 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1000–1005, 2015.
D. Frelinger, J. Kvitky, W. Stanley, “Proliferated autonomous weapons,” Rand Corp., Santa Monica, CA, Tech. Rep., 1997.
N. H. Motlagh, T. Taleb, O. Arouk, “Low-altitude unmanned aerial vehicles-based internet of things services: Comprehensive survey and future perspectives,” IEEE Internet of Things Journal, vol. 3, no. 6, pp. 899–922, 2016.
Drone incidents all over the world. [Online]. Available: https://www.dedrone.com/resources/incidents/all
S. Edwards, “Swarming on the Battlefield: Past, Present, and Future”. Santa Monica, Rand Corp., 2000.
B. P. Gerkey, M. J. Mataric, “A formal analysis and taxonomy of task allocation in multirobot systems,” International Journal of Robotics Research, vol.23, no.9, pp.939–954, 2004.
X. Chen, T. Tang, “Dynamic task allocation method for multiple UAVs in uncertain environment,” Firepower and Command Control, vol. 38, no. 1, pp. 45–49, 2013.
X.L. Zhao, K.W. Zhang, Z.Z. Li, “Research on dynamic reconnaissance resource allocation of multiple UAVs,” Electronics Optics and Control, vol. 27, no. 6, pp. 11–15, 2020.
T. Shima, S. J. Rasmussen, A. G. Sparks, K. M. Passino, “Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms,” Computers & Operations Research, vol. 33, no. 11, pp. 3252–3269, 2006.
F. Su, Y. Chen, L. C. Shen, “UAV cooperative multi task assignment based on ant colony algorithm,” Acta Aeronautica Sinica, vol. 29, no. 1, pp. 184–191, 2008.
Z. Liu, W. Li, J.C. Ren, “Modeling and solving method of multi base and multi UCAV task allocation,” Journal of Southeast University, vol. 49, no. 1, pp. 91–96, 2019.
D.M. Gordon, “The organization of work in social insect colonies,” Nature, vol. 380 no.6570, pp.121–124, 1996.
I. Karsai, T. Schmickl, “Regulation of task partitioning by a “common stomach”: a model of nest construction in social wasps,” Behavioral Ecology, vol.22, no.4, pp.819–830, 2011.
H. W. Kuhn, “The hungarian method for the assignment problem,” Naval Research Logistics, vol.2, no.1, pp.83–97, 1955.
T. Lemaire, R. Alami, S. Lacroix, “A distributed tasks allocation scheme in multi-uav context,”in IEEE International Conference on Robotics and Automation, 2004.
M. Hussain, B. Kimiaghalam, A. Homaifar, “An evolutionary approach to capacitated resource distribution by a multiple-agent team,” in Genetic and Evolutionary Computation Conference. 2003.
D.P. Bertsekas, “A distributed algorithm for the assignment problem,” Annals of Operations Research, vol.14, no.1, pp.105–123, 1979.
M. G. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. J. Kleywegt, S. Koenig, C. A. Tovey, A. Meyerson, “Auction-based multi-robot routing,” in Robotics: Science and Systems, 2005.
R. Simmons, D. Apfelbaum, W. Burgard, D. Fox, M. Moors, S. Thrun, H. Younes, “Coordination for multi-robot exploration and mapping,” American Association for Artificial Intelligence, pp. 852–858, 2000.
I. Rekleitis, A. P. New, E. S. Rankin, H. Choset, “Efficient boustrophedon multi-robot coverage: An algorithmic approach,” Annals of Mathematics and Artificial Intelligence, vol.52, no.2, pp.109–142, 2008.
D. Vail, M. Veloso, “Dynamic multi-robot coordination,” Multi-Robot Systems: From Swarms to Intelligent Automata, vol. 2, pp. 87–98, 2003.
R. C. Cavalcante, T. Noronha, L. Chaimowicz, “Improving combinatorial auctions for multi-robot exploration,” in 16th international conference on advanced robotics, 2013.
E. Schneider, O. Balas, A. T. Ozgelen, E. I. Sklar, S. Parsons, “Evaluating auction-based task allocation in multi-robot teams” in AAMAS workshop on autonomous robots and multirobot systems, 2014.
M. G. Lagoudakis, M. Berhault, S. Koenig, P. Keskinocak, A. J. Kleywegt, “Simple auctions with performance guarantees for multirobot task allocation,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst. (IROS), Sendai, Japan, pp. 698–705, 2004.
S. Yan, F. Pan, D. Zhang, “Research on task reassignment method of heterogeneous uav in dynamic environment,” in 6th International Conference on Robotics and Automation Sciences, 2022.
B. Lopez, B. Innocenti, D. Busquets, “A Multiagent System for Coordinating Ambulances for Emergency Medical Services,” IEEE Intelligent Systems, vol.23, no.5, pp.50-57, 2008.
M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby, P. Grin, A. Kleywegt, “Robot exploration with combinatorial auctions,” in International Conference on Intelligent Robots and Systems, 2003.
A. Prasad, S. Sundaram, H. L. Choi, “Min–max tours for task allocation to heterogeneous agents,” in Proc. IEEE Conf. Decis. Control (CDC), Miami, FL, USA, 2018.
E. P. Freitas, M. Basso, A. A. S. Silva, “A distributed task allocation protocol for cooperative multi uav search and rescue systems,” in International Conference on Unmanned Aircraft Systems (ICUAS), 2021.
S. Trigui, A. Kouba, O. Cheikhrouhou, “A distributed market based algorithm for the multi robot assignment problem,” Procedia Computer Science, vol.32, no.1, pp.1108–1114, 2014.
S. Raja, G. Habibi, J. P. How, “Communication-Aware Consensus-Based Decentralized Task Allocation in Communication Constrained Environments”, IEEE Access, vol.10, pp. 19753 – 19767, 2021.
S. A. S. Baron, “Dynamic Task Allocation and Coordination in Cooperative Multi-Agent Environments,” Doctoral Dissertation, University of Girona, Spain, 2010.
J. Bellingham, M. Tillerson, A. Richards, J.P. How, “Multi-task allocation and path planning for cooperative UAVs,” Cooperative Systems, vol 1., pp. 23–41, 2003.
G. A. Korsah, A. Stentz, M.B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” Int. J. Robot. Res., vol. 32, no. 12, pp. 1495–1512, 2013.
J. Jackson, M. Faied, P. Kabamba, A. Girard, “Communication-Constrained Distributed Task Assignment,” in IEEE Conference on Decision and Control and European Control Conference, 2011.
D.Castanon, C. Wu, “Distributed algorithms for dynamic reassignment,” in Proc. IEEE Conf. Decis. Control, pp. 13–18, 2003.
M. Otte, M. J Kuhlman, D. Sofge, “Auctions for multi-robot task allocation in communication limited environments,” Autonomous Robots, vol.44, pp. 547–584, 2020.
H. L. Choi, L. Brunet L, “Consensus based decentralized auctions for robust task allocation,” IEEE Transactions on Robotics, vol.25, no.4, pp. 912–926, 2009.
X. Fu, J. Pan, X. Gao, B. Li, J. Chen, K. Zhang, “Task Allocation Method for Multi-UAV Teams with Limited Communication Bandwidth,” in 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), 2018.
B. Zhu, L. Xie, D. Han, X. Meng, R. Teo, “A survey on recent progress in control of swarm systems,” Science China Information Sciences, vol.60, no.7, 2017.
S. J. Chung, A.vA. Paranjape, P. Dames, S. Shen, V. Kumar, “A survey on aerial swarm robotics,” IEEE Transactions on Robotics, vol.34, no.4, pp.837–855, 2018.
B. Balazs, G. Vasarhelyi, “Coordinated dense aerial traffic with self-driving drones,” in IEEE International Conference on Robotics and Automation (ICRA), pp. 6365–6372, 2018.
J. A. Fax, R. M. Murray, “Information flow and cooperative control of vehicle formations,” IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1465–1476, 2004.
J. Supramongkonset, S. Duangsuwan, S. Promwong, “A Study of A2A Channel Modeling for Small UAV-Enabled Wireless Communication,” in IEEE International Conference on Engineering, Applied Sciences and Technology (ICEAST), 2021.

Details

Primary Language

English

Subjects

Automation Engineering , Control Engineering, Mechatronics and Robotics (Other)

Journal Section

Research Article

Authors

Mutullah Eşer ^*
0009-0009-4847-7522
Türkiye

Asım Egemen Yılmaz
0000-0002-4156-4238
Türkiye

Early Pub Date

August 23, 2024

Publication Date

August 31, 2024

Submission Date

March 30, 2024

Acceptance Date

July 26, 2024

Published in Issue

Year 2024 Volume: 7 Number: 2

DOI

https://doi.org/10.35377/saucis...1461626

IZ

https://izlik.org/JA59XW66FU

Cite

RIS / Bibtex

APA

Eşer, M., & Yılmaz, A. E. (2024). Distributed Task Allocation for UAV Swarms with Limited Communication. Sakarya University Journal of Computer and Information Sciences, 7(2), 187-202. https://doi.org/10.35377/saucis...1461626

AMA

1.Eşer M, Yılmaz AE. Distributed Task Allocation for UAV Swarms with Limited Communication. SAUCIS. 2024;7(2):187-202. doi:10.35377/saucis.1461626

Chicago

Eşer, Mutullah, and Asım Egemen Yılmaz. 2024. “Distributed Task Allocation for UAV Swarms With Limited Communication”. Sakarya University Journal of Computer and Information Sciences 7 (2): 187-202. https://doi.org/10.35377/saucis. 1461626.

EndNote

Eşer M, Yılmaz AE (August 1, 2024) Distributed Task Allocation for UAV Swarms with Limited Communication. Sakarya University Journal of Computer and Information Sciences 7 2 187–202.

IEEE

[1]M. Eşer and A. E. Yılmaz, “Distributed Task Allocation for UAV Swarms with Limited Communication”, SAUCIS, vol. 7, no. 2, pp. 187–202, Aug. 2024, doi: 10.35377/saucis...1461626.

ISNAD

Eşer, Mutullah - Yılmaz, Asım Egemen. “Distributed Task Allocation for UAV Swarms With Limited Communication”. Sakarya University Journal of Computer and Information Sciences 7/2 (August 1, 2024): 187-202. https://doi.org/10.35377/saucis. 1461626.

JAMA

1.Eşer M, Yılmaz AE. Distributed Task Allocation for UAV Swarms with Limited Communication. SAUCIS. 2024;7:187–202.

MLA

Eşer, Mutullah, and Asım Egemen Yılmaz. “Distributed Task Allocation for UAV Swarms With Limited Communication”. Sakarya University Journal of Computer and Information Sciences, vol. 7, no. 2, Aug. 2024, pp. 187-02, doi:10.35377/saucis. 1461626.

Vancouver

1.Mutullah Eşer, Asım Egemen Yılmaz. Distributed Task Allocation for UAV Swarms with Limited Communication. SAUCIS. 2024 Aug. 1;7(2):187-202. doi:10.35377/saucis. 1461626