Известия высших учебных заведений

Прикладная нелинейная динамика

ISSN 0869-6632 (Print)
ISSN 2542-1905 (Online)


Для цитирования:

Kiselev O. М. Boundaries of computational complexity and optimal cluster’s quantity for controlled swarm in non-cooperative games [Киселев О. М. Ограничения вычислительной сложности и оптимальные размеры кластера для управления роем в некооперативных играх] // Известия вузов. ПНД. 2021. Т. 29, вып. 3. С. 376-385. DOI: 10.18500/0869-6632-2021-29-3-376-385


Полный текст в формате PDF(Ru):
(загрузок: 27)
Язык публикации: 
английский
Тип статьи: 
Научная статья
УДК: 
519.67
DOI: 
10.18500/0869-6632-2021-29-3-376-385

Boundaries of computational complexity and optimal cluster’s quantity for controlled swarm in non-cooperative games
[Ограничения вычислительной сложности и оптимальные размеры кластера для управления роем в некооперативных играх]

Авторы: 
Киселев Олег Михайлович, Институт математики с вычислительным центром Уфимского федерального исследовательского центра Российской академии наук
Аннотация: 

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

Благодарности: 
Я благодарю проф. В.Ю. Новокшенова за указание на близкую аналогию кластеризации объектов в рое с теорией коагуляции Смолуховского
Список источников: 
  1. Teruel E, Aragues R, Lopez-Nicol as G. A distributed robot swarm control for dynamic region coverage. Robotics and Autonomous Systems. 2019;119:51–63. DOI: 10.1016/j.robot.2019.06.002.
  2. Hu J, Lanzon A. An innovative tri-rotor drone and associated distributed aerial drone swarm control. Robotics and Autonomous Systems. 2018;103:162–174. DOI: 10.1016/j.robot.2018.02.019.
  3. Yu D, Chen CLP, Ren CE, Sui S. Swarm control for self-organized system with fixed and switching topology. IEEE Transactions on Cybernetics. 2020;50(10):4481–4494. DOI: 10.1109/TCYB.2019.2952913.
  4. Cao YU, Fukunaga AS, Kahng A. Cooperative mobile robotics: Antecedents and directions. Autonomous Robots. 1997;4(1):7–27. DOI: 10.1023/A:1008855018923.
  5. Gazi V, Fidan B, Marques L, Ordonez R. Robot Swarms: Dynamics and Control. In book: Mobile Robots for Dynamic Environments. Chapter 4. ASME; 2015. P. 79–125. DOI: 10.1115/1.860526_ch4.
  6. Bayindir L. A review of swarm robotics tasks. Neurocomputing. 2016;172:292–321. DOI: 10.1016/j.neucom.2015.05.116.
  7. Kiselev O. Estimation of computational complexity for sub-optimal swarm control in noncooperative games. 2020 4th Scientific School on Dynamics of Complex Networks and their Application in Intellectual Robotics (DCNAIR). 7-9 Sept. 2020, Innopolis, Russia. P. 133–134. DOI: 10.1109/DCNAIR50402.2020.9216775.
  8. MailRuChamps/miniaicups [Electronic resource]. GitHub Inc.; 2018. Access mode: https: //github.com/mailruchamps/miniaicups/tree/master/agario.
  9. Dichkovskii A. Mini ai cup 2 or almost AgarIO – what could have been done to win [Electronic resource]. Habr; 2018. Access mode: https://habr.com/ru/post/420737.
  10. von Neumann J, Morgenstern O. Theory of Games and Economic Behavior. Princeton: Princeton University Press; 2007. 776 p.
  11. Glebov SG, Kiselev OM, Tarkhanov NN. Nonlinear Equations with Small Parameter. Vol. 16 of De Gruyter Series in Nonlinear Analysis and Applications. De Gruyter; 2017. 335 p.
  12. Smoluchowski MV. Drei Vortrage uber Diffusion, Brownsche Bewegung und Koagulation von Kolloidteilchen. Physik. Zeit. 1916;17:557–585 (in German).
Поступила в редакцию: 
27.10.2020
Принята к публикации: 
23.12.2020
Опубликована: 
31.05.2021