Метод декомпозиции глобальной задачи на локальные задачи посредством процесса коллективного принятия решений в роевых робототехнических системах

Цель. Целью работы является повышение эффективности процесса распределения задач за счет предварительной декомпозиции и определения приоритетов задач посредством процесса коллективного принятия решений (КПР) в роевых робототехнических системах (РРТС).

Метод. Декомпозиция задач осуществляется с помощью гибридной стратегии принятия решений, мажоритарном принципе смены мнений с применением технологии распределенного реестра для распространения мнений среди агентов РРТС и агрегации накопленных знаний о среде функционирования. Элементом научной новизны является предложенная процедура КПР, обеспечивающая возможность оценки приоритета выполнения задач, что в свою очередь, позволяет повысить эффективность функционирования агентов РРТС.

Результат. Для апробации предложенного метода была выполнена его программная реализация на языке программирования C++. Для проведения экспериментов был использован сценарий коллективного восприятия агентами РРСТ в специализированной имитационная среде ARGoS.

Вывод. Метод, реализованный с помощью предложенных в работе решений, оказался эффективнее, чем метод на основе жадного алгоритма. Предложенные решения можно применять не только в РРТС, но и любых других робототехнических системах с децентрализованным управлением, предназначенных для мониторинга и контроля параметров среды. 

1. Даринцев О.В., Мигранов А.Б. Декомпозиция задач в группе роботов с использованием технологий облачных вычислений // Труды Института механики им. Р.Р. Мавлютова УНЦ РАН. 2017. Т. 12, № 1. С. 83–88.

2. Solovey, K., Bandyopadhyay, S., Rossi, F., Wolf, M. T., Pavone, M.. Fast Near-Optimal Heterogeneous Task Allocation via Flow Decomposition // 2021 IEEE International Conference on Robotics and Automation (ICRA). 2021. P. 9117–9123.

3. Lavendelis E. Responsibility Area Based Task Allocation Method for Homogeneous Multi Robot Systems // Ad-hoc Networks Wireless. Lect. Notes Comput. Sci. 2015. V. 8629. P. 232–245.

4. Motes, J., Sandström, R., Lee, H., Thomas, S.,mAmato, N. M. Multi-Robot Task and Motion Planning With Subtask Dependencies // IEEE Robot. Autom. Lett. 2020. V. 5, № 2. P. 3338–3345.

5. Adamey E., Oğuz A.E., Özgüner Ü. Collaborative Multi-MSA Multi-Target Tracking and Surveillance: a Divide & Conquer Method Using Region Allocation Trees // J Intell Robot Syst. 2017. V. 87. P. 471–485.

6. Strobel V., Castelló Ferrer E., Dorigo M. Blockchain Technology Secures Robot Swarms: A Comparison of Consensus Protocols and Their Resilience to Byzantine Robots // Front. Robot. AI. 2020. V. 7. P. 1–22.

7. Петренко В.И., Рябцев С.С., Тебуева Ф.Б., Стручков И.В. Метод достижения консенсуса для роя роботов относительно наиболее часто встречающейся особенности окружающей среды на основе технологии блокчейн // Фундаментальные проблемы информационной безопасности в условиях цифровой трансформации, Ставрополь, 2020. С. 249–254.

8. Zakiev A., Tsoy T., Magid E. Swarm robotics: Remarks on terminology and classification // Lect. Notes Comput. Sci. Springer Verlag, 2018. V. 11097. P. 291–300.

9. Dudek G., Jenkin M., Milios E., Wilkes D. A taxonomy for multi-agent robotics. Auton. Robots. 1996. V. 3, № 4. P. 375–397.

10. Lamport L., Shostak R., Pease M. The Byzantine Generals Problem // C. Trans. Program. Lang. Syst. 1982; 4(3): 382–401.

11. Petrenko V.I., Tebueva, F.B., Ryabtsev S.S., Antonov V.O., Struchkov I.V. Data Based Identification of Byzantine Robots for Collective Decision Making // 2022 13th Asian Control Conf. IEEE, 2022. P. 1724–1727.

12. Tebueva F., Ryabtsev S., Struchkov I. A method of counteracting Byzantine robots with a random behavior strategy during collective design-making in swarm robotic systems // E3S Web Conf. EDP Sciences, 2021. V. 270. P. 1–6.

13. Петренко В.И., Тебуева Ф.Б., Павлов А.С., Стручков И.В. Анализ рисков нарушения информационной безопасности в роевых робототехнических системах при масштабировании численности агентов // Прикаспийский журнал: управление и высокие технологии. 2022. № 2 (58). С. 92-109.

14. Павлов А.С., Свистунов Н.Ю., Петренко В.И., Тебуева Ф.Б., Линец Г.И., Мочалов В.П. Система разграничения доступа к информационным ресурсам роевых робототехнических систем в условиях наличия внедренных вредоносных агентов // Информатизация и связь. 2022. № 5. С. 121-130.

15. Valentini G., Brambilla D., Hamann H.,Dorigo M. Collective perception of environmental features in a robot swarm // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, 2016. V. 9882. P. 65–76.

16. Рябцев С.С. Метод выявления вредоносных роботов на основе данных процесса коллективного принятия решений в роевых робототехнических системах // Системы управления, связи и безопасности. 2021. № 5. С. 224-258.

17. Павлов А.С. Методика планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями // Системы управления, связи и безопасности. 2021. № 3. С. 38-59.

18. Юдинцев Б.С. Синтез нейросетевой системы планирования траекторий для группы мобильных роботов. // Системы управления, связи и безопасности. 2019. № 4. С. 163–186.

19. Иванов Д. Я. Формирование строя группой беспилотных летательных аппаратов при решении задач мониторинга // Известия ЮФУ. Технические науки. 2012. № 4 (129). С. 219-224.

20. Веселов Г.Е., Лебедев Б.К., Лебедев О.Б. Управление формированием и поддержанием строя автономных беспилотных летательных аппаратов // Системный синтез и прикладная синергетика. сборник научных работ X Всероссийской научной конференции. Ростов-на-Дону, Таганрог, 2021. С. 104–108.

21. Hamann H. Swarm Robotics: A Formal Approach. Springer International Publishing. 2018. – 210 p.

22. Petrenko V.I., Tebueva F.B., Ryabtsev S.S., Gurchinsky M.M., Struchkov I.V. Сonsensus achievement method for a robotic swarm about the most frequently feature of an environment // IOP Conference Series: Materials Science and Engineering. Krasnoyarsk Science and Technology City Hall of the Russian Union of Scientific and Engineering Associations. Krasnoyarsk, Russia, 2020. P. 42025.

23. Koubaa A., Bennaceur H., Chaari I., Trigui S., Ammar A., Sriti M., Alajlan M., Cheikhrouhou O., Javed Y. Robot Path Planning and Cooperation - Foundations, Algorithms and Experimentations // Studies in Computational Intelligence. 2014. V. 772. P. 1–160.

24. Pinciroli C., Trianni V., O'Grady R., Pini G., Brutschy A., Brambilla M., Mathews N., Ferrante E., Caro G. D., Ducatelle F., Birattari M., Gambardella L., Dorigo M. ARGoS: A modular, parallel, multi-engine simulator for multi-robot systems // Swarm Intelligence. 2012. V. 6. № 4. P. 271–295.