Geodesic
Boundaries of computational complexity and optimal cluster's quantity for controlled swarm in non-cooperative games
Izvestiya VUZ. Applied Nonlinear Dynamics, Tome 29 (2021) no. 3, pp. 376-385.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: Swarm of clusters, optimal control, computational complexity. 
@article{IVP_2021_29_3_a4,
     author = {O. M. Kiselev},
     title = {Boundaries of computational complexity and optimal cluster's quantity for controlled swarm in non-cooperative games},
     journal = {Izvestiya VUZ. Applied Nonlinear Dynamics},
     pages = {376--385},
     publisher = {mathdoc},
     volume = {29},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IVP_2021_29_3_a4/}
}
TY  - JOUR
AU  - O. M. Kiselev
TI  - Boundaries of computational complexity and optimal cluster's quantity for controlled swarm in non-cooperative games
JO  - Izvestiya VUZ. Applied Nonlinear Dynamics
PY  - 2021
SP  - 376
EP  - 385
VL  - 29
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVP_2021_29_3_a4/
LA  - en
ID  - IVP_2021_29_3_a4
ER  - 
%0 Journal Article
%A O. M. Kiselev
%T Boundaries of computational complexity and optimal cluster's quantity for controlled swarm in non-cooperative games
%J Izvestiya VUZ. Applied Nonlinear Dynamics
%D 2021
%P 376-385
%V 29
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVP_2021_29_3_a4/
%G en
%F IVP_2021_29_3_a4
O. M. Kiselev. Boundaries of computational complexity and optimal cluster's quantity for controlled swarm in non-cooperative games. Izvestiya VUZ. Applied Nonlinear Dynamics, Tome 29 (2021) no. 3, pp. 376-385. http://geodesic.mathdoc.fr/item/IVP_2021_29_3_a4/