Auction-based distributed task allocation algorithm for drone swarms

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.

Keywords

• Drone swarm
• Task allocation
• Distributed computing
• Auction algorithm

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

Öz

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.

Anahtar Kelimeler

• Dron sürüsü
• Görev atama
• Dağıtık hesaplama
• açık artırma algoritması

Kaynakça

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.