Research Article
BibTex RIS Cite

Year 2024, Volume: 7 Issue: 2, 187 - 202, 31.08.2024

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

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

Abstract

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.

Distributed Task Allocation for UAV Swarms with Limited Communication

Year 2024, Volume: 7 Issue: 2, 187 - 202, 31.08.2024

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

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

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

UAV swarms Distributed computing Auction algorithm Task allocation Constrained communication

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.
There are 58 citations in total.

Details

Primary Language English
Subjects Automation Engineering, Control Engineering, Mechatronics and Robotics (Other)
Journal Section Articles
Authors

Mutullah Eşer 0009-0009-4847-7522

Asım Egemen Yılmaz 0000-0002-4156-4238

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 2024Volume: 7 Issue: 2

Cite

IEEE 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, 2024, doi: 10.35377/saucis...1461626.
 Download Cover Image

29070    The papers in this journal are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License