Distribution of tasks in a clustered field of goals for homogeneous and heterogeneous UAV groups

Distribution of tasks in a clustered field of goals for homogeneous and heterogeneous UAV groups

Vyacheslav I. Petrenko
PhD in Technical Sciences, Associate Professor, Federal State Autonomous Educational Institution of Higher Education «North Caucasian Federal University» (NCFU), Institute for Digital Development, Head of the Department of Organization and Technology of Information Security 1, Pushkina ul., Stavropol, 355007, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0003-4293-7013

Fariza B. Tebueva
Doctor of Physical and Mathematical Sciences, Associate Professor, NCFU, Head of the    Computer Security Department, 1, Pushkina ul., Stavropol, 355007, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0002-7373-4692

Vladimir O. Antonov
PhD in Technical Sciences, NCFU, Assistant Professor of the Computer Security Department, 1, Pushkina ul., Stavropol, 355007, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0001-8264-9409

Artur V. Sakolchik
Belarusian State University (BGU), student, 4, pr. Nezavisimosty, Minsk, 220030, Republic of Belarus, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0003-4516-3164

Received October 19, 2022

Abstract
This work is devoted to the distribution of tasks in groups of unmanned aerial vehicles (UAVs) under conditions of a significant excess of the number of tasks over the number of agents. The main tasks solved by UAVs: survey and reconnaissance of territories, detection of dangerous objects or places of emergencies, search for victims, etc. The efficiency of solving the problems listed above achieved by the simultaneous use of a group of UAVs, the elements (agents) of which can carry out the tasks of inspecting and scanning various areas of space in parallel. The article proposes an iterative method for distributing tasks in a group of UAVs with a significant excess of the number of tasks over the number of agents (5-20 times). The proposed method for heterogeneous groups of UAVs based on a two-stage procedure for distributing agents of different specializations among task clusters, taking into account the agent's value function. At the first stage, the base part of the agents is distributed, the remaining agents at the second stage distributed in order to average the distance traveled by each agent. Execution of tasks within a cluster implemented by simulating annealing. To evaluate the effectiveness of the method variants, a comparison made with the greedy task distribution algorithm and the collective goal distribution algorithm. The analogs under consideration are widespread, universal and have a high convergence of the solution. Experimental studies carried out by computer simulation, where 2000 experiments carried out with various changes in the number of group agents and generation of a task map. The results showed the high efficiency of the task distribution method in terms of reducing the distance traveled by the agents of the UAV group when performing tasks in comparison with analogues. The efficiency of the path traveled by agents is up to 28% depending on the number of agents and tasks in the cluster, which is a scientific increment of the result of the study.

Key words
Group robotics, swarm robotics, collective decision-making, task distribution, assignment problem.

Acknowledgements
The results were obtained within the framework of the grant of the President of the Russian Federation for young scientists - candidates of science (No. MK-300.2022.4 Development of methods and algorithms for the UAV swarm control system when performing heterogeneous tasks).

DOI
10.31776/RTCJ.11203

Bibliographic description
Petrenko, V.I., Tebueva, F.B., Antonov, V.O. and Sakolchik, A.V. (2023). Distribution of tasks in a clustered field of goals for homogeneous and heterogeneous UAV groups. Robotics and Technical Cybernetics, 11(2), pp. 99-109.

UDC identifier:
623.746-519

References 

  1. Kalyaev, I.A., Gaiduk, A.R.  and Kapustyan S.G. (2009), Models and algorithms of collective control in groups of robots, FIZMATLIT, Moscow, Russia, p. 280.
  2. Zakiev, A., Tsoy, T. and Magid, E. (2018), “Swarm Robotics: Remarks on Terminology and Classification”, Third International Conference, ICR 2018, Leipzig, Germany, September 18-22, 2018, DOI: 10.1007/978-3-319-99582-3_30.
  3. Chung, S. et al. (2018), “A Survey on Aerial Swarm Robotics”, In IEEE Transactions on Robotics, vol. 34, no. 4, pp. 837-855, Aug. 2018, DOI: 10.1109/TRO.2018.2857475.
  4. Pshikhopov V.Kh. et al. (2015), Group control of moving objects in uncertain environments, FIZMATLIT, Moscow, Russia, p. 305.
  5. Kowalczyk, W. (2002), “Target Assignment Strategy for Scattered Robots Building Formation”, of the 3rd Intern. Workshop on Robot Motion and Control, Poznan, Poland, pp. 181-185.
  6. Mathew, N., Smith, S.L. and Waslander, S.L. (2015), “Planning Paths for Package Delivery in Heterogeneous Multirobot Teams”, In IEEE Transactions on Automation Science and Engineering, vol. 12, no. 4, pp. 1298-1308, DOI: 10.1109/TASE.2015.2461213.
  7. Zavlanos, M., Spesivtsev, L. and Pappas, G. (2008), “A distributed auction algorithm for the assignment problem”, of the IEEE Conf. on Decision and Control, pp. 1212-1217.
  8. Nam, C. and Shell, D.A. (2015), “Assignment Algorithms for Modeling Resource Contention in Multirobot Task Allocation”, In IEEE Transactions on Automation Science and Engineering, vol. 12, no. 3, pp. 889-900, DOI: 10.1109/TASE.2015.2415514.
  9. Chopra, S. et al. (2017), “A Distributed Version of the Hungarian Method for Multirobot Assignment”, In IEEE Transactions on Robotics, vol. 33, no. 4, pp. 932-947, DOI: 10.1109/TRO.2017.2693377.
  10. Notomista, G. et al. (2019), “An Optimal Task Allocation Strategy for Heterogeneous Multi-Robot Systems”, 18th European Control Conference (ECC), pp. 2071-2076, DOI: 10.23919/ECC.2019.8795895.
  11. Zavlanos, M., Spesivtsev, L. and Pappas, G. (2008), “A distributed auction algorithm for the assignment problem”, of the IEEE Conf. on Decision and Control, pp. 1212-1217.
  12. Bertsekas, D. and Castanon, D. (1991), “Parallel synchronous and asynchronous implementations of the auction algorithm”, J. of Parallel Computing, vol. 17, pp. 707-732.
  13. Luo, L., Chakraborty, N. and Sycara, K. (2015), “Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks”, In IEEE Transactions on Robotics, vol. 31, no. 1, pp. 19-30, DOI: 10.1109/TRO.2014.2370831.
  14. Zavlanos, M. and, Pappas, G. (2008), “Dynamic assignment in distributed motion planning with local coordination”, IEEE Transactions on Robotics, vol. 24, no. 1, pp. 232-242.
  15. Zavlanos, M. and, Pappas, G. (2007), “Sensor-based dynamic assignment in distributed motion planning”, of the IEEE Intern. Conf. on Robotics and Automation, pp. 3333-3338.
  16. Berman, S. et al. (2009), “Optimized Stochastic Policies for Task Allocation in Swarms of Robots”, In IEEE Transactions on Robotics, vol. 25, no. 4, pp. 927-937, DOI: 10.1109/TRO.2009.2024997.
  17. Liu, R. et al. (2020), “Decentralized task allocation for multiple UAVs with task execution uncertainties”, 2020 International Conference on Unmanned Aircraft Systems (ICUAS), 271-278, DOI: 10.1109/ICUAS48674.2020.9213989.
  18. Mouton, H., Roodt, J. and Roux H. (2011), “Applying Reinforcement Learning to the Weapon Assignment Problem in Air Defense”, Scientia Militaria, South African J. of Military Studies, 39, no. 2, pp. 1-15.
  19. Zhao, H., Dorigo, M. and Allwright, M. (2021), “General Dynamic Neural Networks for the Adaptive Tuning of an Omni-Directional Drive System for Reactive Swarm Robotics”, 25th International Conference on Methods and Models in Automation and Robotics (MMAR), pp. 79-84, DOI: 10.1109/MMAR49549.2021.9528468.
  20. Mukhedkar, R. and Naik, S. (2013), “Weapon Target Allocation Problem Using Fuzzy Model”, J. of Application or Innovation in Engineering & Management, vol. 2, no. 6, pp. 279-289.
  21. Wei, T. et al. (2021), “ Multi-UAV Task Allocation Based on Type Mamdani Fuzzy Logic”, 7th International Symposium on Mechatronics and Industrial Informatics (ISMII), pp. 184-187, DOI: 10.1109/ISMII52409.2021.00046.
  22. Yuan, M., Ling, M-X. and Zeng, Q-S. (2008), “An AntColony Algorithm Based on Pheromone Declining for Solving the WTA Problem”, J. on Computer Simulation, vol. 25, no. 2, pp. 23-25.
  23. Payton D. et al. (2001), “Pheromone robotics”, Robot., vol. 11, no. 3, pp. 319-324.
  24. Payton, D., Estkowski, R. and Howard M. (2005), “Pheromone robotics and the logic of virtual pheromones”, In Proc. 1st Int. Workshop Swarm Robotics at SAB 2004, LNCS, Springer-Verlag Berlin, Germany, vol. 3342, pp. 45-57.
  25. Oliveira S. et al. (2017), “Analysis of the population-based ant colony optimization algorithm for the TSP and the QAP”, IEEE Congress on Evolutionary Computation (CEC), pp. 1734-1741, DOI: 10.1109/CEC.2017.7969511.
  26. Liao T. et al. (2014), “Ant Colony Optimization for Mixed-Variable Optimization Problems”, In IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 503-518, DOI: 10.1109/TEVC.2013.2281531.
  27. Brutschy, A. et al. (2012), “Can ants inspire robots?”, Self-organized decision making in robotic swarms, 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4272-4273, DOI: 10.1109/IROS.2012.6386273.
  28. Murphy, R. (1999), “Target-Based Weapon Target Assignment Problems”, Nonlinear Assignment Problems: Algorithms and Applications. Kluwer Academic Publishers, vol. 7., pp. 39-53.
  29. Sikanen, T. (2008), “Solving Weapon Target Assignment Problem with Dynamic Programming”, Independent research projects in applied mathematics, p. 32.
  30. Yu, J. and. LaValle, S.M. (2016), “Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics”, In IEEE Transactions on Robotics, vol. 32, no. 5, pp. 1163-1177, DOI: 10.1109/TRO.2016.2593448.
  31. Shimaa, T. et al. (2006), “Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms”, Computers & Operations Research 33, pp. 3252-3269.
  32. Patel, R. et al. (2020), “Decentralized Task Allocation in Multi-Agent Systems Using a Decentralized Genetic Algorithm”, IEEE International Conference on Robotics and Automation (ICRA), pp. 3770-3776, DOI: 10.1109/ICRA40945.2020.9197314.
  33. Soleimanpour-Moghadam, M. and Nezamabadi-Pour, H. (2020), “Discrete Genetic Algorithm for Solving Task Allocation of Multi-robot Systems”, 4th Conference on Swarm Intelligence and Evolutionary Computation (CSIEC), pp. 006-009, DOI: 10.1109/CSIEC49655.2020.9237316.
  34. Husheng, W., Hao, L. and Renbin, X. (2021), “A blockchain bee colony double inhibition labor division algorithm for spatio-temporal coupling task with application to UAV swarm task allocation”, In Journal of Systems Engineering and Electronics, vol. 32, no. 5, pp. 1180-1199, DOI: 10.23919/JSEE.2021.000101.
  35. Msala, Y., Hamlich, M. and Mouchtachi, A. (2019), “A new Robust Heterogeneous Multi-Robot Approach Based on Cloud for Task Allocation”, 5th International Conference on Optimization and Applications (ICOA), pp. 1-4, DOI: 10.1109/ICOA.2019.8727618.
  36. Zhang, J., Wang, X. and Xu, C. (2012), “ACGA Algorithm of Solving Weapon Target Assignment Problem”, Open J. of Applied Science, [online], vol. 2, no. 4B, pp. 74-77.
  37. Kong, X. et al.] (2019), “Multi-robot Task Allocation Strategy based on Particle Swarm Optimization and Greedy Algorithm”, IEEE 8th Joint International Information Technology and Artificial Intelligence Conference (ITAIC), pp. 1643-1646, DOI: 10.1109/ITAIC.2019.8785472.
  38. Wei, C., Ji, Z. and Cai, B. (2020), “Particle Swarm Optimization for Cooperative Multi-Robot Task Allocation: A Multi-Objective Approach”, IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 2530-2537, DOI: 10.1109/LRA.2020.2972894.
  39. Petrenko V. et al. (2022), “Iterative Method of Labor Division for Multi-Robotic Systems”, Proceedings of International Conference on Artificial Life and Robotics, pp. 699-702.
  40. Petrenko V. et al. (2020), “Consensus achievement method for a robotic swarm about the most frequently feature of an environment”, IOP Conference Series: Materials Science and Engineering, 919(4), 042025.
  41. GitHub, “Task-Allocation”, available at: https://github.com/BenJoice/Task-Allocation (Accessed October 7, 2022).