Патерни самоорганізації стратегій у грі мобільних агентів

Abstract

Розглянуто актуальну проблему самоорганізації стратегій стохастичної гри багатоагентної системи. Проявом самоорганізації є формування скоординованих поведінкових патернів групи мобільних агентів, наділених здатністю переміщуватися в обмеженому дискретному просторі. Агент – це автономний об’єкт, який може взаємодіяти із навколишнім середовищем, іншими агентами і людиною для вибору варіантів рішень. Багатоагентна система складається із групи агентів, які виконують спільну роботу, співпрацюючи між собою у межах локальних підмножин агентів. Поведінковий патерн багатоагентної системи – це візуалізована форма впорядкованого переміщення агентів, яка виникає із їх початкового хаотичного руху під час навчання стохастичної гри. Повторювальна стохастична гра полягає у реалізації керованого випадкового процесу вибору варіантів рішень. Для цього ігрові агенти випадково, одночасно і незалежно вибирають одну із власних чистих стратегій у дискретні моменти часу. Чисті стратегії гравців визначають напрямки переміщення у двовимірному просторі: вперед, назад, направо, наліво. Після завершення вибору усіх стратегій обчислюють поточні програші гравців. Для формування впорядкованого переміщення кожен агент повинен повторювати дії сусідніх агентів. Тоді поточні програші визначаються індикаторною функцією подібності стратегій сусідніх гравців. Обчислені поточні програші використовують для адаптивного перерахунку змішаних стратегій гравців. Імовірність вибору чистої стратегії збільшується, якщо її реалізація призвела до зменшення поточного програшу. Під час повторювальної гри агенти сформують вектори змішаних стратегій, які мінімізують функції середніх програшів гравців. Для розв'язування ігрової задачі побудови патернів самоорганізації багатоагентної системи використано адаптивний марківський рекурентний метод, побудований на основі стохастичної апроксимації модифікованої умови доповняльної нежорсткості, яка справедлива у точках рівноваги за Нешем. Для нормування елементів векторів змішаних стратегій застосовано операцію їх проектування на одиничний розширюваний епсілон-симплекс. Збіжність ігрового методу забезпечується дотриманням фундаментальних умов та обмежень стохастичної оптимізації. Комп'ютерне моделювання підтвердило можливість застосування моделі стохастичної гри для побудови патернів самоорганізації багатоагентної системи. Форма отриманих патернів залежить від способу локального орієнтування мобільних агентів. Під час комп’ютерного експерименту отримано вихрові та лінійні патерни переміщення агентів. Достовірність експериментальних досліджень підтверджується подібністю отриманих результатів для різних послідовностей випадкових величин. Результати цієї роботи доцільно застосувати для вивчення патернів колективної поведінки агентів для глибшого розуміння процесів самоорганізації природних систем та для побудови розподілених систем прийняття рішень.In this research the actual problem of self-organizing of strategies of stochastic game of multiagent systems is considered. Self-organizing display are formations of the co-ordinated behavioural patterns of group of the mobile agents endowed with the ability to move within a limited discrete space. The agent is an independent object which can interact with environment, other agents and the person for a choice of variants of decisions. The multiagent system consists of group of agents which perform the general work, co-operating among themselves within local subsets of agents. The behavioural pattern of multiagent systems is the visualised form of purposeful moving of agents which arises from their initial chaotic movement during training of stochastic game. A repetitive stochastic game is to implement a controlled random process of selecting decision options. To do this, game agents randomly, simultaneously and independently choose one of their own pure strategies at discrete times. Pure player strategies determine the direction of movement in twodimensional space: forward, back, to the right, to the left. When all strategies have been selected, the current player losses are calculated. To form an orderly move, each agent must repeat the actions of neighboring agents. The current losers are then determined by the indicator function of the similarity of the strategies of the neighboring players. The calculated current losses are used to adaptively recalculate mixed player strategies. The probability of a pure strategy selection increases, if its realisation has led to reduction of current loss. In the course of a recurring game, agents will form vectors of mixed strategies that will minimize the functions of the players' average losses. To solve the game problem of constructing patterns of self-organization of a multiagent system it is used the markovian adaptive recurrent method constructed on the basis of stochastic approximation of the modified complementary slackness condition which is correct in balance to Nash points. For a normalization of elements of vectors of the mixed strategies operation of their projecting on a unit expanded epsilon-simplex is applied. Convergence of a game method is provided with observance of fundamental conditions and restrictions of stochastic optimisation. Computer simulation confirmed the possibility of using a stochastic game model to build patterns of self-organization of a multi-agent system. The form of the received patterns depends on a way of local orientation of mobile agents. During computer experiment vortical and linear patterns moving of agents are received. The reliability of the experimental studies is confirmed by the similarity of the results obtained for different sequences of random variables. The results of this work are expedient for applying to studying of patterns of collective behaviour of agents for deeper understanding of the processes of self-organizing of natural systems and for the construction of distributed decision-making systems.