Кравець, ПетроKravets, Petro2023-06-072023-06-072021-03-012021-03-01Кравець П. Самоорганізація стратегій у грі переміщення агентів / Петро Кравець // Вісник Національного університету "Львівська політехніка". Інформаційні системи та мережі. — Львів : Видавництво Львівської політехніки, 2021. — № 9. — С. 131–141.https://ena.lpnu.ua/handle/ntb/59146Розроблено стохастичну ігрову модель самоорганізації стратегій стохастичної гри мобільних агентів у вигляді циклічних поведінкових патернів, які складаються із узгоджених стратегій переміщення агентів у обмеженому дискретному просторі. Поведінковий патерн багатоагентної системи є візуалізованою формою впорядкованого переміщення агентів, яка виникає із їх початкового хаотичного руху в ході навчання стохастичної гри. Мобільність агентів багатокрокової стохастичної гри забезпечено тим, що у дискретні моменти часу вони випадково, одночасно і незалежно вибирають власну чисту стратегію переміщення в одному із можливих напрямків. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців. Ці функції сформовано зі штрафу за нерівномірність розміщення агентів у обмеженому дискретному просторі та штрафу за зіткнення під час переміщення агентів. Випадковий вибір чистих стратегій гравців спрямовано на мінімізацію їхніх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі векторів змішаних стратегій. Елементи векторів змішаних стратегій є умовними імовірностями вибору відповідних чистих стратегій переміщення. Змішані стратегії змінюються у часі, адаптивно враховуючи значення поточних програшів. Цим забезпечено зростання імовірностей вибору тих чистих стратегій, які приводять до зменшення функцій середніх програшів. Динаміку векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого виконано стохастичну апроксимацію модифікованої умови доповняльної нежорсткості, яка справедлива у точках рівноваги за Нешем, та застосовано оператор проєктування на розширюваний одиничний епсилон-симплекс. Збіжність рекурентного ігрового методу забезпечено дотриманням фундаментальних умов та обмежень стохастичної апроксимації. Стохастична гра розпочинається із ненавчених змішаних стратегій, які задають хаотичну картину переміщення агентів. У ході навчання стохастичної гри вектори змішаних стратегій цілеспрямовано змінюються так, щоб забезпечити впорядковане безконфлікне переміщення агентів. У результаті комп’ютерного моделювання стохастичної гри отримано циклічні патерни самоорганізації мобільних агентів на поверхні дискретного тора та у межах прямокутної області на площині. Достовірність експериментальних досліджень підтверджено подібністю отриманих патернів переміщення агентів для різних послідовностей випадкових величин. Результати дослідження запропоновано використати на практиці для побудови розподілених систем із елементами самоорганізації, розв’язування різноманітних потокових і транспортних задач та колективного прийняття рішень в умовах невизначеності.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 nonrigidity, 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 uncertainty131-141ukсамоорганізаціяциклічний поведінковий патернбагатоагентна системастохастична грамарковський рекурентний методself-organizationcyclic behavioral patternmulti-agent systemstochastic gameMarkov recurrent methodArticle© Національний університет “Львівська політехніка”, 2021© Кравець П., 202111doi.org/10.23939/sisn2021.09.131004.[85294]Kravets P. Self-organizing strategies in game of agent movement / Petro Kravets // Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Informatsiini systemy ta merezhi. — Lviv : Lviv Politechnic Publishing House, 2021. — No 9. — P. 131–141.