Self-organizing Strategies in Game of Agent Movement

: сс. 131 - 141
Lviv Polytechnic National University, Information Systems and Networks Department

In this paper, a stochastic game model of self-organization of strategies of stochastic game of mobile agents in the form of cyclic behavioral patterns, which consist of coordinated strategies for moving agents in a limited discrete space, is developed. The behavioral pattern of a multi-agent system is a visualized form of orderly movement of agents that arises from their initial chaotic movement during the learning of a stochastic game.

The mobility of multi-step stochastic game agents is ensured by the fact that in discrete moments of time they randomly, simultaneously and independently choose their own pure strategy of moving in one of the possible directions.

Current player payments are defined as loss functions that depend on the strategies of neighboring players. These functions are formed from the penalty for irregular spacing of agents in a limited discrete space and the penalty for collisions when moving agents. Random selection of players’ strategies aims to minimize their average loss functions. The generation of sequences of pure strategies is performed by a discrete distribution based on the vectors of mixed strategies. The elements of the vectors of mixed strategies are the conditional probabilities of choosing the appropriate pure displacement strategies. Mixed strategies change over time, adaptively taking into account the value of current losses. This provides an increase in the probability of choosing those strategies that lead to a decrease in the functions of average losses.

The dynamics of the vectors of mixed strategies is determined by the Markov recurrent method, for the construction of which a stochastic approximation of the modified condition of complementary non- rigidity, which is valid at Nash equilibrium points, is performed, and a projection operator for expandable unit epsilon simplex is applied. The convergence of the recurrent game method is ensured by compliance with the fundamental conditions and limitations of stochastic approximation.

The stochastic game begins with untrained mixed strategies that set a chaotic picture of moving agents. During the learning of the stochastic game, the vectors of mixed strategies are purposefully changed so as to ensure an orderly, conflict-free movement of agents.

As a result of computer simulation of stochastic game, cyclic patterns of self-organization of mobile agents on the surface of a discrete torus and within a rectangular region on a plane are obtained. The reliability of the experimental studies was confirmed by the similarity of the obtained patterns of moving agents for different sequences of random variables.

The results of the study are proposed to be used in practice for the construction of distributed systems with elements of self-organization, solving various flow and transport problems and collective decision-making in conditions of uncertainty.

  1. Gamazine, S., Deneubourg, J.-L., Frank, N.R., Sneyd, J., Theraula, G., Bonabeau, E. (2020). Self-Organization in Biological Systems. Princeton University Press.
  2. Guillot, A., Meyer, J.-A. (2013). Bionics. When the Science Imitates the Nature (in russian). Moscow: Technosphere.
  3. Zhang, W.J. (editor). (2013). Self-organization: Theories and Methods. USA: Nova Science Publishers.
  4. Kravets, P.A., Jurinets R.V, Kis, Y.P. (2020). Patterns of self-organizing strategies in the game of mobile agents (in ukrainian). Bulletin of «Lviv polytechnic national university». Series: «Information systems and networks», Issue 7, 24 - 34. DOI: 10.23939/sisn2020.07.024. p
  5. Kelso, J.A., Scott. (1995). Dynamic patterns: The self-organization of brain and behavior. Cambridge, MA: The Mit Press.
  6. Josselyn, S.A., Tonegawa, S. (2020). Memory engrams: Recalling imagining the future. Review. Science. American Association for the Advancement of Science (AAAS), 367, 6473, 1 - 14. DOI: 10.1126/science.aaw4325. p
  7. Samoilov, V., Bigdaj, Е. (2020). Human physiology for technical specialities: the central nervous and sensory systems. The manual for high schools. The second edition (in russian). Мoscow: Urait.
  8. Galkin, A.Yu., Titova, L.A. (2018). Fundamentals of evolutionary theory. Tutorial (in ukrainian). Kyiv: Igor Sikorsky Kyiv Polytechnic Institute.
  9. Adamatzky, A., Komosinski, M. (Eds). (2005). Artificial Life Model in Software. Springer.
  10. Adami, C. (1998). Introduction to Artificial Life. Springer. p
  11. Langton, C.G. (1995). Artificial Life. An Overview. Cambridge: The MIT Press.
  12. Sadhu, A.K., Konar, A. (2020). Multi-Agent Coordination. Wiley-IEEE Press.
  13. Sun, Z. (2018). Cooperative Coordination and Formation Control for Multi-agent Systems. Springer.
  14. Yang, S., Xu, J.-X., Li, X., Shen, D. (2017). Iterative Learning Control for Multi-agent Systems Coordination. John Wiley & Sons. p
  15. Kravets, P. A. (2015). Game model of self-organizing of multiagent systems (in ukrainian). Bulletin of «Lviv polytechnic national university». Series: «Information systems and networks», 829, 161 - 176.
  16. Chen, B.-S. (2020). Stochastic Game Strategies and their Applications. CRC Press.
  17. Ungureanu, V. (2018). Pareto-Nash-Stackelberg Game and Control Theory: Intelligent Paradigms and Applications. Springer. p
  18. Neogy, S. K., Bapat, Ravindra, B., Dubey, Dipti. (Eds). (2018). Mathematical Programming and Game Theory. Springer. p
  19. Kusuoka, S. (2020). Stochastic Analysis. Springer. p
  20. Kushner, H.J., Yin, G.G. (2013). Stochastic Approximation Algorithms and Applications. Springer.
  21. Nazin, A. V., Poznyak, A. S. (1986). Adaptive Choice of Variants: Recurrence Algorithms (in russian). Moscow: Science.