Вісники та науково-технічні збірники, журнали
Permanent URI for this communityhttps://ena.lpnu.ua/handle/ntb/12
Browse
3 results
Search Results
Item Ігрова самоорганізація гамільтонового циклу графа(Видавництво Львівської політехніки, 2021-03-01) Кравець, Петро; Пасічник, Володимир Володимирович; Проданюк, Микола; Kravets, Petro; Pasichnyk, Volodymyr; Prodaniuk, Mykola; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityУ роботі запропоновано нове застосування моделі стохастичної гри для розв’язування задачі самоорганізації гамільтонового циклу графа. Для цього у вершинах неорієнтованого графа розміщено ігрових агентів, чисті стратегії яких є варіантами вибору одного із інцидентних ребер. Випадковий вибір стратегій усіма агентами утворює набір локальних шляхів, що розпочинаються у кожній вершині графа. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців, які контролюють суміжні вершини графа. Ці функції сформовано зі штрафу за вибір протилежних стратегій сусідніми гравцями та штрафу за стратегії, які призвели до зменшення довжини локального шляху. Випадковий вибір чистих стратегії гравців спрямовано на мінімізацію їх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі динамічних векторів змішаних стратегій. Елементи векторів змішаних стратегій є імовірностями вибору відповідних чистих стратегій, які адаптивно враховують значення поточних програшів. Формування векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого використано градієнтний метод стохастичної апроксимації. У ході гри метод збільшує значення імовірностей вибору тих чистих стратегій, які призводять до зменшення функцій середніх програшів. Для заданих способів формування поточних платежів результатом стохастичної гри є утворення патернів самоорганізації у вигляді циклічно зорієнтованих стратегій ігрових агентів. Умови збіжності рекурентного методу до колективно оптимальних розв’язків забезпечено дотриманням фундаментальних умов стохастичної апроксимації. Виконано розширення ігрової задачі на випадкові графи. Для цього вершинам приписано імовірності відновлювальних відмов, які спричиняють зміну структури графа на кожному кроці гри. Реалізації випадкового графа адаптивно враховуються під час пошуку гамільтонових циклів. Збільшення імовірності відмов сповільнює збіжність стохастичної гри. Комп’ютерне моделювання стохастичної гри забезпечило отримання патернів самоорганізації стратегій агентів у вигляді декількох локальних циклів або глобального гамільтонового циклу графа залежно від способів формування поточних програшів гравців. Достовірність експериментальних досліджень підтверджено повторенням реалізацій патернів самоорганізації для різних послідовностей випадкових величин. Результати дослідження можна використати на практиці для ігрового розв’язування NPскладних задач, транспортних і комунікаційних задач, для побудови протоколів автентифікації у розподілених інформаційних системах, для колективного прийняття рішень в умовах невизначеності.Item Самоорганізація стратегій у грі переміщення агентів(Видавництво Львівської політехніки, 2021-03-01) Кравець, Петро; Kravets, Petro; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityРозроблено стохастичну ігрову модель самоорганізації стратегій стохастичної гри мобільних агентів у вигляді циклічних поведінкових патернів, які складаються із узгоджених стратегій переміщення агентів у обмеженому дискретному просторі. Поведінковий патерн багатоагентної системи є візуалізованою формою впорядкованого переміщення агентів, яка виникає із їх початкового хаотичного руху в ході навчання стохастичної гри. Мобільність агентів багатокрокової стохастичної гри забезпечено тим, що у дискретні моменти часу вони випадково, одночасно і незалежно вибирають власну чисту стратегію переміщення в одному із можливих напрямків. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців. Ці функції сформовано зі штрафу за нерівномірність розміщення агентів у обмеженому дискретному просторі та штрафу за зіткнення під час переміщення агентів. Випадковий вибір чистих стратегій гравців спрямовано на мінімізацію їхніх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі векторів змішаних стратегій. Елементи векторів змішаних стратегій є умовними імовірностями вибору відповідних чистих стратегій переміщення. Змішані стратегії змінюються у часі, адаптивно враховуючи значення поточних програшів. Цим забезпечено зростання імовірностей вибору тих чистих стратегій, які приводять до зменшення функцій середніх програшів. Динаміку векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого виконано стохастичну апроксимацію модифікованої умови доповняльної нежорсткості, яка справедлива у точках рівноваги за Нешем, та застосовано оператор проєктування на розширюваний одиничний епсилон-симплекс. Збіжність рекурентного ігрового методу забезпечено дотриманням фундаментальних умов та обмежень стохастичної апроксимації. Стохастична гра розпочинається із ненавчених змішаних стратегій, які задають хаотичну картину переміщення агентів. У ході навчання стохастичної гри вектори змішаних стратегій цілеспрямовано змінюються так, щоб забезпечити впорядковане безконфлікне переміщення агентів. У результаті комп’ютерного моделювання стохастичної гри отримано циклічні патерни самоорганізації мобільних агентів на поверхні дискретного тора та у межах прямокутної області на площині. Достовірність експериментальних досліджень підтверджено подібністю отриманих патернів переміщення агентів для різних послідовностей випадкових величин. Результати дослідження запропоновано використати на практиці для побудови розподілених систем із елементами самоорганізації, розв’язування різноманітних потокових і транспортних задач та колективного прийняття рішень в умовах невизначеності.Item Патерни самоорганізації стратегій у грі мобільних агентів(Видавництво Львівської політехніки, 2020-02-24) Кравець, Петро; Юринець, Ростислав; Кісь, Ярослав; Kravets, Petro; Yurynets, Rostyslav; Kis, Yaroslav; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityРозглянуто актуальну проблему самоорганізації стратегій стохастичної гри багатоагентної системи. Проявом самоорганізації є формування скоординованих поведінкових патернів групи мобільних агентів, наділених здатністю переміщуватися в обмеженому дискретному просторі. Агент – це автономний об’єкт, який може взаємодіяти із навколишнім середовищем, іншими агентами і людиною для вибору варіантів рішень. Багатоагентна система складається із групи агентів, які виконують спільну роботу, співпрацюючи між собою у межах локальних підмножин агентів. Поведінковий патерн багатоагентної системи – це візуалізована форма впорядкованого переміщення агентів, яка виникає із їх початкового хаотичного руху під час навчання стохастичної гри. Повторювальна стохастична гра полягає у реалізації керованого випадкового процесу вибору варіантів рішень. Для цього ігрові агенти випадково, одночасно і незалежно вибирають одну із власних чистих стратегій у дискретні моменти часу. Чисті стратегії гравців визначають напрямки переміщення у двовимірному просторі: вперед, назад, направо, наліво. Після завершення вибору усіх стратегій обчислюють поточні програші гравців. Для формування впорядкованого переміщення кожен агент повинен повторювати дії сусідніх агентів. Тоді поточні програші визначаються індикаторною функцією подібності стратегій сусідніх гравців. Обчислені поточні програші використовують для адаптивного перерахунку змішаних стратегій гравців. Імовірність вибору чистої стратегії збільшується, якщо її реалізація призвела до зменшення поточного програшу. Під час повторювальної гри агенти сформують вектори змішаних стратегій, які мінімізують функції середніх програшів гравців. Для розв'язування ігрової задачі побудови патернів самоорганізації багатоагентної системи використано адаптивний марківський рекурентний метод, побудований на основі стохастичної апроксимації модифікованої умови доповняльної нежорсткості, яка справедлива у точках рівноваги за Нешем. Для нормування елементів векторів змішаних стратегій застосовано операцію їх проектування на одиничний розширюваний епсілон-симплекс. Збіжність ігрового методу забезпечується дотриманням фундаментальних умов та обмежень стохастичної оптимізації. Комп'ютерне моделювання підтвердило можливість застосування моделі стохастичної гри для побудови патернів самоорганізації багатоагентної системи. Форма отриманих патернів залежить від способу локального орієнтування мобільних агентів. Під час комп’ютерного експерименту отримано вихрові та лінійні патерни переміщення агентів. Достовірність експериментальних досліджень підтверджується подібністю отриманих результатів для різних послідовностей випадкових величин. Результати цієї роботи доцільно застосувати для вивчення патернів колективної поведінки агентів для глибшого розуміння процесів самоорганізації природних систем та для побудови розподілених систем прийняття рішень.