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

For citation:

Kiselev O. М. Boundaries of computational complexity and optimal cluster’s quantity for controlled swarm in non-cooperative games. Izvestiya VUZ. Applied Nonlinear Dynamics, 2021, vol. 29, iss. 3, pp. 376-385. DOI: 10.18500/0869-6632-2021-29-3-376-385

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Full text PDF(Ru):
PDF icon kiselev.pdf
(downloads: 807)
Language: 
English
Heading: 
Nonlinear Dynamics and Neuroscience
Article type: 
Article
UDC: 
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

Autors: 
Kiselev Oleg Михайлович, Institute of Mathematics with Computing Centre
Abstract: 

The purpose of the work is to determine the relationship between the computational complexity of controlling a swarm of particles and the available computational resources for choosing the optimal control strategy. We find formulas for the relationship between the available computational complexity, the number of clusters in the swarm, the number of interacting players, and the depth of calculations to search the suboptimal control. Methods. To find the optimal control, the method of maximizing the target objective function is used. The computational complexity of the objective function is determined for suboptimal control on the grid for the maximum number of particle swarms and the minimum of the grid size. To study the swarm dynamics in the configuration space we investigate the properties of the convex hull of the swarm using elements of the particle diffusion theory. Results. The objective function of controlling a swarm of particles in the conditions of interaction with stationary objects and in the presence of competitive swarms is constructed. It is shown that the swarm of particles spread in the configuration space due to instability and mixing in the general situation. Formulas for the maximum possible size of clusters and the number of particles in clusters, the depth of calculation of control steps and the detail of the grid are obtained. The connection between the dynamics of the swarm of controlled particles and the theory of Smolukhowski’s coagulation in colloidal solutions is shown. Conclusion. Constraints on the computational complexity of the control lead to a restriction on the size of the iteration grid for finding the minimax and to a restriction on the number of swarm clusters for which the optimal strategy can be chosen. The clustering capability of the swarm leads to the fact that the product of the number of positions in the grid in the optimization of the number of clusters in a swarm depth calculation steps should be no more than the order of the logarithm of acceptable computational complexity.

Key words: 
Swarm of clusters
optimal control
computational complexity
Acknowledgments: 
I thank Prof. V. Y. Novokshenov for pointing out a close analogy of clustering objects in a swarm with Smolukhowsky’s theory of coagulation
Reference: 
  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).
Received: 
27.10.2020
Accepted: 
23.12.2020
Published: 
31.05.2021
  • 2316 reads