Распределение задач в кластеризированном поле целей для гомогенных и гетерогенных групп БПЛА

Распределение задач в кластеризированном поле целей для гомогенных и гетерогенных групп БПЛА

Петренко Вячеслав Иванович
к.т.н., доцент, ФГАОУ ВО «Северо-Кавказский федеральный университет» (СКФУ), Институт цифрового развития, заведующий кафедрой организации и технологии защиты информации, 355007, г. Ставрополь, ул. Пушкина, д. 1., Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра., ORCID: 0000-0003-4293-7013

Тебуева Фариза Биляловна
д.ф.-м.н., доцент, СКФУ, заведующий кафедрой компьютерной безопасности, 355007, г. Ставрополь, ул. Пушкина, д. 1., Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра., ORCID: 0000-0002-7373-4692

Антонов Владимир Олегович
к.т.н., СКФУ, доцент кафедры компьютерной безопасности, 355007, г. Ставрополь, ул. Пушкина, д. 1., тел.: +7(988)098-05-11, Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра., ORCID: 0000-0001-8264-9409

Сакольчик Артур Витальевич
Белорусский государственный университет (БГУ), студент, 220030, Республика Беларусь, г. Минск, пр. Независимости, д. 4, Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра., ORCID: 0000-0003-4516-3164

Материал поступил в редакцию 19 октября 2022 года.

Аннотация
Данная работа посвящена вопросам распределения задач в группах беспилотных летательных аппаратов (БПЛА) при условиях значительного превышения количества задач над количеством агентов. Основными задачами, решаемыми БПЛА, являются: обзор и разведка территорий, обнаружение опасных объектов или мест возникновения чрезвычайных ситуаций, поиск пострадавших и т.п. Эффективность решения перечисленных выше задач достигается путем одновременного использования группы БПЛА, элементы (агенты) которой могут осуществлять параллельное выполнение задач по осмотру и сканированию различных областей пространства. В статье предложен итеративный метод распределения задач в группе БПЛА при значительном превышении количества задач над количеством агентов (5-20 раз). Предлагаемый метод для гетерогенных групп БПЛА базируется на двухэтапной процедуре распределения агентов разных специализаций по кластерам задач с учетом функции ценности агента. На первом этапе производится распределение базовой части агентов, оставшиеся агенты на втором этапе распределяются с целью усреднения пройденного пути каждым агентом. Выполнение задач внутри кластера реализуется методом имитации отжига. Для оценки эффективности вариантов метода произведено сравнение с жадным алгоритмом распределения задач и алгоритмом коллективного распределения целей. Рассматриваемые аналоги являются широко распространенным, универсальными и имеют высокую сходимость решения. Экспериментальные исследования проведены путем компьютерного моделирования, где проведено 2000 экспериментов при различном изменении количества агентов группы и генерации карты задач. Результаты показали высокую эффективность метода распределения задач в части снижения пройденного пути агентами группы БПЛА при выполнении задач в сравнении с аналогами. Эффективность пройденного пути агентами составляет до 28% в зависимости от количества агентов и задач в кластере, что является научным приращением полученного результата исследования.

Ключевые слова
Групповая робототехника, роевая робототехника, коллективное принятие решений, распределение задач, задача о назначениях.

Благодарности
Результаты были получены в рамках выполнения гранта Президента Российской Федерации для молодых ученых - кандидатов наук (№ МК-300.2022.4 Разработка методов и алгоритмов для системы управления роем БПЛА при выполнении гетерогенных задач).

DOI
10.31776/RTCJ.11203

Индекс УДК 
623.746-519

Библиографическое описание
Распределение задач в кластеризированном поле целей для гомогенных и гетерогенных групп БПЛА / В.И. Петренко [и др.] // Робототехника и техническая кибернетика. – Т. 11. - № 2. – Санкт-Петербург : ЦНИИ РТК. – 2023. – С. 99-109. – Текст : непосредственный.

Литература

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

Полный текст статьи (pdf)