Лекція 12. Самоорганізація колективу агентів у часі
(самосинхронізація)
1. Постановка задачі самосинхронізації колективу
temporal self-organization ( self-synchronization
Для вирішення більшості прикладних задач колективу агентів необхідно самоорганізуватися у часі, тобто в той або інший спосіб прийти до єдиної для всіх агентів точки відліку часу. Тобто агенти мають зробити щось одночасно (наприклад, підняти вантаж, вмикнути освітлення) або узгодити свою поведінку в часі (спочатку я зроблю одне, а потім ти зробиш друге) + в багатьох випадках успішність колективної дії залежить від того, скільки агентів реалізували свої індивідуальні дії одночасно.
Постановка задачі. В кожного агента є свій внутрішній годинник. На порівняно невеликому проміжку часу при умові попередньої синхнонізації ці годинники показують однаковий час. Після цього їхні покази починають розходитись, внаслідок чого виникає потреба у повторній синхронізації. У випадку повністю децентралізованого колективу відсутня можливість використати для цього т.з. "зовнішній годинник" (тобто деякий аналог центра управління). Т.ч. треба розробити локальний уніфікований алгоритм, який би в умовах локальної взаємодії, дозволяв агентам колективу за злічену кількість часових кроків одночасно встановити внутрішні годинники агентів в нуль. [рисунок 1] До алгоритму самосинхнонізації висуваються вимоги по точності (як правило забезпечується точність до одного часового кроку (такту)).
Змістовна інтерпретація: однорідні обчислювальні середовища (Евреинов, Прангишвилли, Варшавский) + FPGA - [field programmable gate array] – вентильна матриця з можливістю поточного репрограмування ( проблема синхронізації логічних блоків, розташованих на підложці мікросхеми (труднощі, викликані використанням загального(зовнішнього) годинника))
Дискретний та аналоговий варіанти задачі самосинхронізації.
аналоговий ( генератори з багатьма зворотніми зв’язками (осцилятори, биття)
дискретний ( цифрові автомати
2. Задача синхронізації ланцюжку стрільців (firing squad synchronization problem, Дж. Майхіл)
[рисунок 2]
Постановка задачі. Розглянемо ланцюжок стрільців, кожний з яких може спілкуватися лише з двома найближчими сусідами. Ланцюжок складається зі скінченної кількості стрільців (N). Обидва крайніх стрільця мають по одному сусіду. Один з крайніх стрільців отримує наказ, після чого стрільці мають домовитись і одночасно дати постріл. Чи існують правила поведінки стрільців, які вирішують цю задачу за тих умов, що кількість слів, якими можуть обмінятись стрільці та об’єм внутрішньої пам’яті кожного з них обмежені і не залежать від N?
інформація про існуючі рішення + шляхи ускладнення задачі: віддавати наказ будь-якому стрільцю, інщі структури з’єднань (кільце, однонаправлене кільце, графо-подібні структури), затримка між стрільцями (неоднакова, невідома, змінна у часі), латентна (прихована) затримка (затримка спрацювання).
3. Приклад алгоритму самосинхронізації ланцюжку агентів
Розглянемо ланцюжок з N агентів. Позначимо через s0 – деякий початковий стан, в якому знаходяться всі агенти, а через s – стан попередньої готовності. Агенти обмінюються сигналами, кожному з яких поставлена у відповідність певна "швидкість" (кількість тактів, на які агент затримує цей сигнал перед тим як передати його сусіду). Розглянемо алгоритм, в якому агенти обмінюються двома сигналами a1 і a3 зі швидкостями 1 і 1/3 відповідно. Після отримання наказу крайній агент відсилає у ланцюжок обидва сигнали і переходить в стан s. Другий крайній агент переходить в стан s після надходження сигналу a1. Обидва крайні агента після переходу в стан починають "відзеркалювати" (надіслати у зворотньому напрямку) всі сигнали, що до них надходять. Всі інщі агенти виконують наступний алгоритм:
Алгоритм.
Якщо отримано один сигнал (a1 або a3) і агент знаходиться в стані s0, то передати сигнал далі по ланцюжку.
Якщо в одному такті отримано два сигнали, то одночасно "відзеркалити" їх і передати далі + перейти в стан s.
Якщо сам агент і обидва його сусіда знаходяться в стані s, то "дати постріл".
[рисунок 3]
Таким чином відбувається поділ інтервалу між двома агентами, що знаходяться в стані s навпіл і в центрі цього інтервалу агент так само переходить в стан s. Цей процес відбувається доти, доки усі автомати не перейдуть в стан s, після чого вони одночасно "дають постріл".
Доведено, що для алгоритмів цього типу (відсилання сигналів) мінімальний час синхрнонізації ланцюжка T=2N-2. В такий самий спосіб відбувається синхронізація ланцюжка, замкненого в кільце (час синхнонізації T=N)
4. Самосинхронізація агентів поєднаних статичною мережею зв’язків.
Розглянемо N агентів, кожний з яких є вершиною довільного зв’язаного неорієнтованого графу. Нехай у відповідність графу поставлена мережа двонаправлених міжагентних зв’язків без затримок з обмеженою пропускною здатністю. Чи існують правила поведінки агента, які б за цих умов, забезпечили самосинхронізацію колективу?
Приклад вирішення задачі.
1. На заданому графі зв’язків знайти довільний підграф без циклів, який би охоплював всіх агентів. Розглнянемо два сигнала at – спеціальний сигнал формування дерева (токен), ar – сигнал відповідь. Кожний агент може знаходитись в двох станах s0 – початковий стан, s1 – стан приналежності дереву. Агент-ініціатор синхронізації відсилає всім своїм сусідам спец. сигнал (токен) at. Далі кожний з агентів виконуює такий алгоритм:
1.1. Якщо агент знаходиться в стані і отримано токен at, то
- перейти в стан s1
- позначити сусіда, від якого прийшов токен як “батьківський”
- пердати токен at далі всім сусідам окрім “батьківського”
- “батьківському” сусіду відправити сигнал-відповідь ar.
1.2. Якщо агент знаходиться в стані s1, то ігнорувати надходження токену.
1.3. Якщо агент знаходиться в стані s1 і отримано сигнал-відповідь ar, то позначити сусіда, від якого він прийшов як “синівський”
[рисунок 4]
Т.ч. сформується граф-дерево найкоротших зв’язків по відношенню до агента-ініціатора. В кожного агента, окрім ініціатора буде один “батьківський” сусід і більше або рівне нулю “синівських” сусідів.
2. Кожному з агентів створити K внутрішніх вузлів, де K – кількість сусідів у створеному графі-дереві.
[рисунок 5]
3. Створити простий цикл (ланцюжок замкнений в кільце) на внутрішніх вузлах, який охоплює все дерево. При цьому у створеному кільці буде M=2(N-1) вузлів.
[рисунок 6]
4. Виконати алгоритм самосинхронізації кільця. Час синхронізації T=M=2(N-1).