SavedAdd your journal

Journals / Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi / 2024 / Cilt: 13 Sayı: 4

Auction-based distributed task allocation algorithm for drone swarms

Dron sürüleri için müzakere tabanlı dağıtık görev atama algoritması

Mutullah Eşer(ANKARA ÜNİVERSİTESİ, MÜHENDİSLİK FAKÜLTESİ)0009-0009-4847-7522
Asım Egemen Yılmaz(ANKARA ÜNİVERSİTESİ, MÜHENDİSLİK FAKÜLTESİ)0000-0002-4156-4238
Pages
1080–1092
Publication Date
2024-10-15
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Prior research primarily focuses on minimizing overall costs associated with assignments.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Drone swarm research has surged due to their superior task performance.
📊
Key Findings & Data:In addition, the performance of the algorithm was evaluated by comparing it with the CBBA (Consensus-Based Bundle Algorithm) algorithm in cases where all messages are transmitted between agents and some messages are not transmitted due to communication problems.
💡
Conclusion & Impact:Prior research primarily focuses on minimizing overall costs associated with assignments.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Dron sürüsü · Görev atama · Dağıtık hesaplama

Abstract

Drone swarm research has surged due to their superior task performance. This paper introduces Harmony DTA, an auction-based algorithm for task allocation in heterogeneous drone swarms. Prior research primarily focuses on minimizing overall costs associated with assignments. In contrast, Harmony DTA not only minimizes total costs through an enhanced cost calculation function, but also ensures equitable distribution of workload among drones. Additionally, the proposed two-stage auction process reduces the total message size utilized during communication. Simulations and field tests were conducted to assess the effectiveness of the proposed algorithm. In addition, the performance of the algorithm was evaluated by comparing it with the CBBA (Consensus-Based Bundle Algorithm) algorithm in cases where all messages are transmitted between agents and some messages are not transmitted due to communication problems. Based on the simulation findings, the suggested algorithm demonstrates an ability to address the assignment problem with a mean cost reduction of 20% and a mean reduction in message size of 50% compared to CBBA in scenarios without communication issues. However, in situations where communication obstacles lead to some messages being untransmitted between agents, Harmony DTA exhibits inferior performance to CBBA, attributed to conflicting assignments arising from the absence of a consensus phase.

Özet

Dron sürüleri üzerine yapılan araştırmalar, üstün görev performansları nedeniyle ivme kazanmıştır. Bu makale, heterojen drone sürülerinde görev dağılımı için açık artırmaya dayalı bir algoritma olan Harmony DTA'yı tanıtıyor. Literatürde var olan araştırmalar öncelikle görevlerle ilgili toplam maliyeti en aza indirmeye odaklanmaktadır. Harmony DTA ise gelişmiş maliyet hesaplama fonksiyonu aracılığıyla yalnızca toplam maliyeti en aza indirmekle kalmaz, aynı zamanda iş yükünün dronlar arasında adil bir şekilde dağıtılmasını da sağlamaktadır. Ayrıca önerilen iki aşamalı açık artırma süreci, iletişim sırasında kullanılan toplam mesaj boyutunu da azaltmaktadır. Önerilen algoritmanın etkinliğini değerlendirmek için simülasyonlar ve saha testleri yapılmıştır. Ek olarak algoritmanın performansı CBBA (Konsensus Tabanlı Demet Algoritması) algoritmasıyla ajanlar arasında tüm mesajların iletildiği ve haberleşme sorunları nedeniyle bazı mesajların iletilmediği durumlar için de karşılaştırılarak değerlendirilmiştir. Elde edilen simülasyon sonuçlarına göre önerilen algoritma haberleşme sorunsuz ortamlarda CBBA’ya göre ortalama %20 daha düşük maliyet ve ortalama %50 daha az mesaj boyutu ile atama problemini çözebilmektedir. Haberleşme sorunu nedeniyle ajanlar arsında bazı mesajların iletilemediği ortamlarda ise Harmony DTA, fikir birliği aşamasına sahip olmaması nedeniyle çakışan atamalar yaparak CBBA’ya göre daha kötü performans sergilemektedir.

🔖

Cite This Article

Eşer, M., Yılmaz, A. E. (2024). Auction-based distributed task allocation algorithm for drone swarms. Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, Cilt: 13 Sayı: 4, 1080–1092. https://doi.org/10.28948/ngumuh.1456928

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (52)

  1. J. Laarni, A. Vaatanen, H. Karvonen, Development of a concept of operations for a counter-swarm scenario. International Conference on Human-Computer Interaction, pp. 49-63, June 2022. https://doi.org/10.1007/978-3-031-06086-1_4
  2. T. Zielinski, Factors determining a drone swarm employment in military operations, Centrum Rzeczoznawstwa Budowlanego Sp. z o.o., 1, pp. 59-71, 2021.
  3. R. B. Yeşilay, A. Macit, Dünyada ve Türkiye’de drone ekonomisi: geleceğe yönelik beklentiler. Beykoz Akademi Dergisi, 8, 239-251, 2020. https://doi.org/10.14514/byk.m.26515393.2020.8/1.239-251
  4. Z. Kallenborn, InfoSwarms: drone swarms and information warfare. The US Army War College Quarterly: Parameters, 52, 87-102, 2022.
  5. R. M. Zlot, An auction-based approach to complex task allocation for multirobot teams. Ph.D. Thesis, Carnegie Mellon University, Pennsylvania, 2006.
  6. G. M. Skaltsis, H. S. Shin, A. Tsourdos. A survey of task allocation techniques in MAS, International Conference on Unmanned Aircraft Systems, pp. 488-497, 2022.
  7. H. W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics, 2(1), 83-97, March 1955.
  8. T. Shima, S. J. Rasmussen, UAV cooperative multiple task assignments using genetic algorithms, American Control Conference, June 2005.
  9. E. P. de Freitas, M. Basso, A. A. S. da Silva, M. R. Vizzotto, M. S. C. Correa, A distributed task allocation protocol for cooperative multi UAV search and rescue systems. International Conference on Unmanned Aircraft Systems (ICUAS), June 2021.
  10. X. Tao, Y. Zheng, Multi agent task allocation method based on auction. Advances in Wireless Networks and Information Systems, 72, 217-225, 2010. https://doi.org/10.1007/978-3-642-14350-2_27
  11. M. B. Dias and A. Stentz, A free market architecture for distributed control of a multirobot system. Conf. on Intelligent Autonomous Systems, pp. 115–122, Venice, Italy, July 2000.
  12. R. M. Zlot, A. T. Stentz, M. B. Dias, S. Thayer, Multi-robot exploration controlled by a market economy. Proc. Int’l Conf. on Robotics and Automation, May 2002.
  13. C. Tovey, M. Lagoudakis, S. Jain, S. Koenig, The generation of bidding rules for auction-based robot coordination, Multi-Robot Systems Workshop, Mar. 2005.
  14. M. G. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, C. Tovey, A. Meyerson, S. Jain, Auction-based multi-robot routing. Robotics: Science and Systems, Cambridge, USA, June 2005. https://doi.org/10.15607/RSS.2005.I.045
  15. M. Rinaldi, S. Primatesta, Auction based task allocation for safe and energy efficient UAS parcel transportation. 11th International Conference on Air Transport, pp. 60-69, 2022. https://doi.org/10.1016/j.trpro.2022.11.008
  16. S. Trigui, A. Kouba, A distributed market based algorithm for the multi robot assignment problem. 3rd International Workshop on Cooperative Robots and Sensor Networks, pp. 1108-1114, 2014. https://doi.org/10.1016/j.procs.2014.05.540
  17. K. Erten, T. Saraç, Simulated annealing algorithm for the multi resource generalized assignment problem with eligibility constraint. Gazi University Journal of Science, 9(3), 385-401, 2021. https://doi.org/10.29109/gujsc.919665
  18. H. L. Choi, L. Brunet, Consensus based decentralized auctions for robust task allocation. IEEE Transactions On Robotics, 25(4), 912-926, 2009. https://doi.org/10.1109/TRO.2009.2022423
  19. Z. Yan, N. Jouandeau, A. A. Cherif, A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems, 10(12), 399, 2013. https://doi.org/10.5772/57313
  20. M. Otte, N. Correll, Any-com multi-robot path-planning: Maximizing collaboration for variable bandwidth. Distributed Autonomous Robotic Systems, 83, 161–173, 2013. https://doi.org/10.1007/978-3-642-32723-0_12
  21. A. Kassir, R. Fitch, A. Sukkarieh, Communication-efficient motion coordination and data fusion in information gathering teams. 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5258–5265, 2016. https://doi.org/10.1109/IROS.2016.7759773
  22. M. Guo, M. M. Zavlanos, Multirobot data gathering under buffer constraints and intermittent communication. IEEE Transactions on Robotics, 34(4), 1082 –1097, 2018. https://doi.org/10.1109/TRO.2018. 2830370
  23. Y. Kantaros, M. Thanou, A. Tzes, Distributed coverage control for concave areas by a heterogeneous robot-swarm with visibility sensing constraints. Automatica, 53, 195–207, 2015. https://doi.org/10.1016/ j.automatica.2014.12.034
  24. G. Best, M. Forrai, R. R. Mettu, R. Fitch, Planning-aware communication for decentralised multi-robot coordination. 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia,, pp.1050-1057, 2018. https://doi.org/10.1109/ ICRA.2018.8460617
  25. R. K. Williams, A. Gasparri, G. S. Sukhatme, G. Ulivi, Global connectivity control for spatially interacting multi-robot systems with unicycle kinematics. IEEE International Conference on Robotics and Automation (ICRA), pp. 1255– 1261, 2015. https://doi.org/ 10.1109/ICRA.2015.7139352
  26. L. Zhou, P. Tokekar, Active target tracking with self-triggered communications in multi-robot teams. IEEE Transactions on Automation Science and Engineering, 16(3), 1085-1096, 2019. https://doi.org/ 10.1109/TASE.2018.2867189
  27. J. V. Hook, P. Tokekar, V. Isler, Algorithms for cooperative active localization of static targets with mobile bearing sensors under communication constraints. IEEE Transactions on Robotics, 31(4), 864–876, 2015. https://doi.org/10.1109/TRO.2015.2432612
  28. H. Li, G. Chen, T. Huang, Z. Dong, High-performance consensus control in networked systems with limited bandwidth communication and time-varying directed topologies. IEEE Transactions on Neural Networks and Learning Systems, 28(5), 1043– 1054, 2017. https://doi.org/10.1109/TNNLS.2016.2519894
  29. S. Yan, F. Pan, D. Zhang, X. Jihua Research on task reassignment method of heterogeneous UAV in dynamic environment. 6th International Conference on Robotics and Automation Sciences, 2022. https://doi.org/10.1109/ICRAS55217.2022.9841995
  30. X.L. Zhao, K.W. Zhang, Z.Z. Li, Research on dynamic reconnaissance resource allocation of multiple UAVs. Electronics Optics and Control, 27(6), 11–15, 2020.
  31. F. Afghah, A. Razi, J. Chakareski, and J. Ashdown, Wildfire monitoring in remote areas using autonomous unmanned aerial vehicles. IEEE Conf. Comput. Commun. Workshops, pp. 835–840, 2019. https://doi.org/10.1109/INFCOMW.2019.8845309
  32. P. Oberlin, S. Rathinam, and S. Darbha, A transformation for a heterogeneous, multiple depot, multiple traveling salesman problem. IEEE Amer. Control Conf., pp. 1292–1297, 2009. http://dx.doi.org/10.1109/ACC.2009.5160666
  33. D. Kim, L. Xue, D. Li, Y. Zhu, W. Wang, and A. O. Tokuta, On theoretical trajectory planning of multiple drones to minimize latency in search-and-reconnaissance operations. IEEE Trans. Mobile Comput., 16 (11), pp. 3156–3166, 2017.
  34. P.B. Sujit, A. Sinha, and D. Ghose, Multi-UAV task allocation using team theory. IEEE Conference on Decision and Control, 2005. https://doi.org/10.1109/CDC.2005.1582370
  35. L. Huo, J. Zhu, G. Wu, and Z. Li, A novel simulated annealing based strategy for balanced uav task assignment and path planning. Sensors, 20(17), 4769, 2020. https://doi.org/10.3390/s20174769
  36. S. Gao, J. Wu, and J. Ai, Multi-uav reconnaissance task allocation for heterogeneous targets using grouping ant colony optimization algorithm. Soft Computing, 25(10), pp.7155–7167, 2021. https://doi.org/10.1007/s00500-021-05675-8
  37. C. Yu, W. Du, F. Ren, and N. Zhao, Deep reinforcement learning for task allocation in uav-enabled mobile edge computing. International Conference on Intelligent Networking and Collaborative Systems, pp 225–232, 2021. https://doi.org/10.1007/978-3-030-84910-8_24
  38. S. Ma, W. Guo, R. Song, and Y. Liu, Unsupervised learning based coordinated multi-task allocation for unmanned surface vehicles. Neurocomputing, 420, pp. 227–245, 2021.
  39. Z. Wang, L. Liu, T. Long, and Y. Wen, Multi-uav reconnaissance task allocation for heterogeneous targets using an oppositionbased genetic algorithm with double-chromosome encoding. Chinese Journal of Aeronautics, 31(2),pp.339–350, 2018. https://doi.org/10.1016/j.cja.2017.09.005
  40. F. Wu, T. Zhang, C. Qiao, and G. Chen, A strategy-proof auction mechanism for adaptive-width channel allocation in wireless networks, IEEE Journal on Selected Areas in Communications, 34(10), pp. 2678-2689, 2016. https://doi.org/10.1109/JSAC.2016.2605939
  41. J. Chen, X. Qing, F. Ye, K. Xiao, K. You, Q. Sun, Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment. Journal of Supercomput, 78, pp. 1712–1740, 2022. https://doi.org/10.1007/s11227-021-03940-z
  42. L. F. Bertuccelli, H. Choi, P. Cho, J. P. How, Real-time multi-uav task assignment in dynamic and uncertain environments. AIAA Guidance, Navigation, and Control Conference, 2009.
  43. A. Samiei, S. Ismail, L. Sun, Cluster-based hungarian approach to task allocation for unmanned aerial vehicles. NAECON 2019 - IEEE National Aerospace and Electronics Conference, 2019.
  44. T. Long, H. Y. Zhu, L. C. Shen, Negotiation-based distributed task allocation for cooperative multiple unmanned combat aerial vehicles. Journal of Astronautics, 27(3), pp. 457–462, 2006.
  45. M. Yao, X. Z. Wang, M. Zhao, Cooperative combat task assignment optimization design for unmanned aerial vehicles cluster. Journal of University of Electronic Science and Technology of China, 2013.
  46. L. B. Johnson, S. S. Ponda, H. L. Choi, J. P. How, Improving the effciency of a decentralized tasking algorithm for UAV teams with asynchronous communications. Aiaa Guidance, Navigation, Control Conference, 2010.
  47. X. Fu, J. Pan, X. Gao, B. Li, K. Zhang, Task allocation method for multi-uav teams with limited communication bandwidth. 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), 2018.
  48. C. Bothorel, J. D. Cruz, M. Magnani, B. Micenkov, Clustering attributed graphs: models, measures and methods. Network Science, 3(3), pp. 408–444, 2015. https://doi.org/10.48550/arXiv.1501.01676
  49. X. Fu, P. Feng, B. Li, X. Gao, A two-layer task assignment algorithm for uav swarm based on feature weight clustering. International Journal of Aerospace Engineering, 2019(5), pp. 1–12, 2019. http://dx.doi.org/10.1155/2019/3504248
  50. S. Yan, J. Xu, L. Song, F. Pan, Heterogeneous UAV collaborative task assignment based on extended CBBA algorithm. 7th International Conference on Computer and Communication, 2022.
  51. G. Best, M. Forrai, R. R. Mettu, R. Fitch, Planning-aware communication for decentralised multi-robot coordination. 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia,, pp.1050-1057, 2018. https://doi.org/10.1109/ ICRA.2018.8460617
  52. Z. Wang, L. Liu, T. Long, and Y. Wen, Multi-uav reconnaissance task allocation for heterogeneous targets using an oppositionbased genetic algorithm with double-chromosome encoding. Chinese Journal of Aeronautics, 31(2),pp.339–350, 2018. https://doi.org/10.1016/j.cja.2017.09.005