Лекція 10. Утворення колективу. Самоіменування. Самоузгодження.
10.1. Архітектура інтегрального підпорядкування (subsumption architecture, Р.Брукс).
10.1.1. Відноситься до так званих реактивних або поведінкових архетектур, які базуються на наступних вихідних ідеях:
Інтелектуальна (розумна) поведінки нерозривно пов’язана з середовищем, в якому розміщено агента. Ця поведінка є результатом взаємодії агента з його середовищем.
Інтелектуальна поведінка виникає сама собою шляхом взаємодії різних простих поведінок.
10.1.2. Дві основні складові архітектури інтегрального підпорядкування:
В процесі прийняття рішення використовується набір проблемно-орієнтованих поведінок, кожна з яких є окремою функцією прийняття рішення, яка відображає сприйнятий стан середовища у деяку дію. Кожна з цих поведінок має свою цільову функцію і ініціюється лише при виникненні відповідних умов.
Декілько поведінок можуть реалізовуватись одночасно. Визначається механізм узгодження цих поведінок (вибір одної дії з декількох запропонованих) у вигляді ієрархії інтегрального підпорядкування: поведінки розбиваються на рівні. Поведінка нижчого рівня переважує поведінку верхнього рівня: чим нижче рівень, тим більше пріоритет поведінки.
Ключова ідея: чим вище рівень, тим більш абстрактною є поведінка + поведінки вищих рівнів користуються результатами поведінок нижчих рівнів. Поведінки нижчих рівнів = базові алгоритми КП.
10.2. Основні вимоги до базових алгоритмів колективної поведінки.
Робота в реальному масштабі часу (on-line, real-time): вибір рішення агентом (колективом) має займати деякий незмінний (constant) проміжок часу, який не перевищує заданої величини затримки.
Локальність поведінки: алгоритм КП має бути поданий у вигляді алгоритмів індивідуальної поведінки агентів (децентралізація).
Локальність взаємодії: алгоритм КП має коректно працювати в умовах обмеженої (локальної) взаємодії агентів, наприклад, в умовах обмеженого радіуса видимості засобів зв’язку.
Уніфікованість (однаковість): всі агенти мають виконувати один і той самий локальний алгоритм (однорідність колективу).
Незалежність від кількості агентів N: алгоритм КП має продовжувати працювати коректно при зміни чисельності колективу, наприклад, після виходу деяких агентів з ладу.
10.3. Утворення колективу: самовиявлення (detecting).
10.3.1. Під утворенням колективу будемо розуміти отримання агентом інформації про інших агентів колективу (тобто перехід від несамовиявленого до самовиявленого колективу). Формат та зміст цієї інформації визначається розробником (див. приклад класифікації агентів за складністю) в рамках моделі інформаційної зв’язності.
10.3.2. Приклад алгоритму самовиявлення (self-detecting) (ts, tw, Z, V, R) [для реалістичної ACM].
Початок. i := 0.
Згенерувати широкомовне (broadcast) повідомлення-запит.
Перейти в режим очікування повідомлень. (t := 0.
t1 := gettime().
Якщо отримано нове повідомлення-відповідь, то
5.1. дешифрувати повідомлення (ID сусіда, координати, статус),
5.2. зберегти отриману інфомацію в моделі колективу,
Якщо отримано повідомлення-запит, то
6.1. Якщо це новий (необроблений) запит, то
- згенерувати повідомлення-відповідь,
- запам’ятати цей запит,
- записати в лічильник цього запиту одиницю,
6.2. Інакше
Якщо значення лічильника цього запиту менше V, то
- згенерувати повідомлення-відповідь,
- збільшити лічильник запиту на один,
Інакше ігнорувати запит.
t2 := gettime().
(t := (t + (t2 – t1).
Якщо (t < tw, то перейти до п.4., інакше до п.10.
Якщо i < Z, то i := i + 1 та перейти до п.2., інакше Кінець.
ts – період самовиявлення (задає періодичність спрацювання алгоритму)
tw – час очікування (задає тривалість очікування, що припадає на один запит)
V – задає кількість відповідей на один запит (надійність)
Z – задає кількість запитів для одного спрацюваня алгоритму
R – радіус видимості засобів зв’язку та детектування
10.3.3. Для випадку мобільних агентів ts має залежати від швидкості руху агентів: чим швидше переміщуються агенти, тим частіше має спрацьовувати алгоритм самовиявлення і навпаки. У випадку поганої (неправильної, несвоєчасної, повільної) роботи алгоритму самовиявлення колектив буде отримувати неправдиву інформацію про свою біжучу структуру з усіма випливаючими негативними наслідками.
10.3.4. Програмні агенти: В IP-мережі в якості радіуса видимості може використовуватись деяка відстань від IP-адреси агента (сканування адрес в діапазоні від <моя IP-адреса> - R до <моя IP-адреса> + R). При цьому можна використовувати тактику динамічної зміни радіуса видимості R в залежності від кількості виявлених сусідів (наприклад, збільшувати радіус, якщо не виявлено жодного сусіда).
10.3.5. Супутні задачі:
- утримання інформаційної зв’язності колективу
- управління інформаційною зв’язністю колективу
- локалізація агентів колективу (localization)
10.4. Самоіменування: генерація унікальних імен агентів.
10.4.1. Нехай в нас є N агентів здатних запам’ятовувати своє ім’я. Розглядається ситуація, коли жоден з них першопочатково не має імені (тобто всі агенти названі однаково і не можуть розрізнити один одного). Задача самоіменування (naming) полягає у знаходженні деякого локального уніфікованого алгоритму який би в умовах обмеженого радіусу видимості R породжував у колективі множину унікальних імен (ідентифікаторів) за можливо меншу кількість часових кроків. Додаткова вимога до алгоритму: можливість роботи в умовах популяційної динаміки (вмирання старих + народження нових агентів).

10.4.2. Приклади вирішення:
- резервування унікальних імен (мережева технологія Ethernet)
- генерація та порівняння випадкових чисел (процедура жеребкування)
10.5. Самоузгодження: домовленність про однакову для всіх величину.
10.5.1. Нехай в нас є N агентів здатних запам’ятовувати значення деякої величини. Розглянемо ситуацію, коли в кожного з них це значення відрізняється від значень інших агентів. Задача самоузгодження полягає у знаходженні деякого локального уніфікованого алгоритму який би в умовах обмеженого радіусу видимості R встановлював однакове для всіх агентів колектива значення заданої величини за можливо меншу кількість часових кроків. Цією величиною може бути деяка константа (наприклад, єдина еталонна міра деякої вимірюваної величини – взірцева величина).
10.5.2. Для вирішення цієї задачі, як правило, використовуються механізми прийняття колективних рішень (ускладнення – обмеженність радіусу видимості ( спілкування лише з сусідніми агентами).