Лекція 20. Задача механічного врівноваження.
1. Постановка та аналіз задачі механічного врівноваження.
1.1. Загальна постановка задачі. Розглянемо площину з однією точкою опори, яка обрана так, що ця площина знаходиться у стані рівноваги. Розмістимо випадковим чином на цій площині N агентів. Всі агенти мають однакову вагу, яку приймемо за одниницю. Кожний з агентів здатний переміщуватись по площині за власною ініціативою в будь-якому напрямку. Внаслідок розміщення агентів площина вийде зі стану рівноваги (новий центр ваги перестане співпадати з обраною раніше точкою опори). Перед колективом агентів ставиться задача врівноважити площину, тобто знайти таке взаєморозміщення, яке б повернуло її у стан рівноваги. Врівноважити площину треба за можливо меншу кількість часових кроків (основний критерій).
1.2. Постановка задачі для одновимірного дискретного випадку. З урахуванням того, що кут відхилення буде рівний нулю при нульовій різниці правого та лівого моментів, отримаємо рівняння задачі
,де M – кількість дискретів одновимірного простору, N – кількість агентів, F – координата точки опоры (N/2 ( F ( (M – N/2)), а ci – координата i–го агента при j-му розміщенні (1 ( c1 ( M – N + 1, N ( cN ( M, ci-1 < ci < ci+1, i=2,…,N-1), mj – різниця моментів при j-му розміщенні (j=1,…,K1, K1 – кількість всіх можливих розміщень N агентів в M дискретах простору, K1=M!/(N!(M-N)!)), |mj| ( [mmin,mmax], mmin = N ( (1 + N) / 2, mmax = N ( (1 + 2M – N) / 2, кількість різних значень |mj| (різниць моментів) K2 = N ( (M – N) + 1.
1.3. Основною проблемою в цій задачі є те, що окремий агент діє на власний розсуд і тому в найгіршому випадку знаходиться в ситуації повної невизначеності стосовно правильності своїх дій (credit assignment problem). Зробивши хід і отримавши відгук (реакцію) середовища у вигляді різниці моментів, агент не може зробити однозначного висновку про те, чи був цей його хід виграшним (врівноважуючим) чи програшним (розрівноважуючим), так як середовище (терези) реагує на колективну дію усіх агентів, а не на одну лише дію даного агента. Внаслідок цього агент, що не володіє інформацією про дії інших агентів колективу, приречений на сумніви відносно правильності своїх дій. Таким чином, найкращим є те рішення задачі, яке в найкращий спосіб долає цю невизначенність.
1.4. Аналіз задачі за допомогою графа розміщень. Кожне розміщення агентів з множини всіх можливих розміщень можна розглядати як вершину деякого графу. Якщо з даного розміщення можна перейти до іншого шляхом преміщення одного чи більше агентів на один крок, то ці два розміщення поєднюються ребром графу. Вага ребра дорівнює кількості одночасних переміщень агентів необхідних для переходу від одного розміщення до другого. Особливі вершини – це врівноважуючі розміщення. Задача зводиться до пошуку найкоротшого шляху від вершини початкового розміщення до найближчої вершини, що відповідає врівноважуючому розміщенню.
1.5. Критерії ефективності алгоритмів врівноваження. З точки зору зовнішнього спостерігача, який володіє повною інформацією про задачу, існує найкоротший можливий шлях з будь якого стану нерівноваги в стан рівноваги Существует кратчайший возможный путь из любого состояния неравновесия в состояние равновесия тривалістю Tj,s (ідеальне врівноваження). Об’єктивно оцінити ефективність роботи алгоритму врівноваження можна лише шляхом порівняння середньої швидкості врівноваження даним алгоритмом Tj,a з часом Tj,s. При цьому визначається за формулою Tj,s = [m0 / N] + {(m0 / N) – [m0 / N]},
де – початкова різниця моментів, N-кількість агентів, […] –взяти цілу частину (truncate), {…} –закруглити зверху (ceiling). На основі Tj,s та знайденого Tj, a можна визначити:
1) абсолютний критерій ефективності: Wj,a = Tj,s – Tj, a,
2) відносний критерій ефективності: wj,a = Tj, a / Tj,s.
2. Вирішення задачі механічного врівноваження.
обмеження:
кожному агенту за однин такт дозволяється зробити лише один крок (т.ч., наприклад, для одновимірного випадку набір всіх можливих дій агента містить три дій: {крок вліво, крок вправо, крок на місці})
два агенти не можуть займати один дискрет простору та “перестрибувати” один через одного
в алгоритмі агента забороняється використовувати значення M,N,F
в кожному такті всім агентам повідомляється біжуча різниця моментів mj
задача вважається вирішеною, коли mj=0
початкове розміщення агентів випадкове
2.1. Централізоване врівноваження. Рішення шукається методами математичного програмування з точки зору центру управління та повністю підпорядкованих йому агентів.
2.2. Децентралізоване врівноваження. Рішення шукається у вигляді локального уніфікованого алгоритму агента (вирішується основна проблема ТКП для повністю однорідного колективу).
2.2.1. Децентралізований повний перебір ( педантичний агент (pedantic agents), загальний алгоритм: спочатку збираються в N крайніх дискретах простору коромисла (справа або зліва) і після визначення моменту повного збору починають по одному переміщуватись на іншу сторону коромисла до моменту врівноваження.
2.2.2. Несамовиявлений колектив ( УНК-1,2,3,4, загальний алгоритм: всі агенти роблять випадковий крок, переміщуючись при цьому в іншу вершину графу розміщення, якщо mj+1 > mj, то кожний з агентів робить зворотню дію (відкат, backtracking) і таким чином повертаються у попередню вершину графу розміщення, інакше вони повторюють процедуру випадкового вибору. Алгоритм можна покращити використанням техніки навчання з підкріпленням (взважений випадковий вибір дій).
2.2.3. Самовиявлений колектив( УСК-2в,3,4, загальний алгоритм: такий самий як для 2.2.2., але нестача інформації про колективну дію зменшується за рахунок спілкування. В межах заданих обмежень на інформаційної взаємодію агенти повідомляють один одному дію, яку вони реалізували на попередньому кроці. Ця інформація використовується під час взваженого випадкового вибору наступної дії.