Лекція 11. Самоорганізація колективу агентів у просторі (самовпорядкування)
11.1. Постановка задачі самовпорядкування.
11.1.1. Задача самовпорядкування полягає у знаходженні локального уніфікованого алгоритму поведінки окремого агента, який би дозволяв колективу агентів управляти розміщенням та переміщенням своїх представників у геометричному просторі середовища, виходячи з поставленої перед ним задачі більш високого рівня. Конкретна постановка задачі впорядкування залежить від структури (будови) середовища, в якому розміщено колектив. Задача впорядкування має зміст, коли кількість агентів N менша за кількість точок середовища M. В більшості задач самовпорядкування в перший момент часу агенти розміщенні у просторі випадковим чином.
11.1.2. Основні задачі, що вирішуються
впорядковане розміщення у просторі (ordered placement): рівномірне заповнення обмеженого деякими границями простору; формування правильної решітки з заданим кроком; формування гнучкої решітки, форма якої залежить від характеристик середовища (змістовна інтерпретація: розподілені вимірювання, контроль тереторії),
формування правильних геометричних фігур (geometric pattern formation) [спонтанне або за наказом]: лінія (відрізок), коло, квадрат (каре) із заданим кроком міжагентної відстані (змістовна інтерпретація: формування пошукового ланцюжку, створення периметру охорони навколо заданого об’єкту),
впорядковане переміщення у просторі (motion control): узгоджене групове переміщення, лідер-наслідувач (leader-follower), слідування заданій траекторії (path following),
уникнення зіткнень з іншими агентами (collision avoidance),
колективне подолання (обминання) перешкод (obstacle avoidance).
11.1.3. Основний критерій ефективності: час за який агенти вирішують задачу самовпорядкування (мінімізація кількості часових кроків). Додатковий критерій: кількість просторових кроків, які витрачають агенти на вирішення задачі (мінімізація витрат енергоресурсу).
11.2. Класифікація задач самовпорядкування.
11.2.1. За фізичними характеристиками (механіка)
голономність ( агент представляється у вигляді геометричної точки, відбувається абстрагування від швидкістних характеристик агента. (Голономна система – це механічна система, в якій всі мезанічні зв’язки є геометричними, тобто такими, що накладають обмеження лише на положення (переміщення) точок або тіл системи, а не на їх швидкості, як це має місце у неголономних системах.)
неголономність ( враховуються інерційність руху агента, нездатність до миттєвої зміни напрямку руху, геометричні розміри агента (які, наприклад, можуть заважати детектуванню іншого агента) + агенти не можуть знаходитись в одній геометричній точці простору
11.2.2. За характеристиками засобів детектування сусідніх агентів
в умовах повної видимості чи в умовах обмеженої видимості
вигляд діаграми направленості засобів детектування (повне коло, сектор (<180(), сектор (>180())
засіб детектування одного типу чи комбінація декількох засобів детектування різних типів (тактильні, інфрачервоні, ультрозвукові, лазерні, електромагнітні сенсори)
11.2.3. За типом інформаційної взаємодії
з обміном інформацією ( колективне прийняття рішень, колективне планування
без обміну інформацією ( лише детектування (для вирішення більшості задач самовпорядкування, як правло, достатньо детектування з визначенням відстані та напрямку на сусіда)
11.2.4. За типом вхідної інформації
в абсолютних координатах,
у відностих координатах.
11.3. Приклад алгоритму формування сегменту лінії.
11.3.1. Простий алгоритм (голономність + обмежена видимість).
1. Серед виявлених сусідів визначити найближчого агента A1 та самого дального агента A2.
2. Рухатись к точці P, що є основою перпендикуляру, який опущено з біжучої позиції даного агента на лінію A1A2.
11.3.2. Моделювання цього алгоритма показало, що можливі ситуації, в яких агенти, виконючи цей алгоритм, не вирішують задачу формування лінії у встановлені строки. Як правило, це ситуації, коли декілько агентів знаходяться поруч один з одним. В результаті цього відбувається потсійна зміна агента, що детектується як найближчий (A1), що в свою чергу призводить до постійної зміни напрямку руху окремого агента і “безцільному блуканню” всіх агентів колективу в цілому. Крім цього цей алгоритм не передбачає рівномірного розміщення агентів на лінії з заданим кроком.
Рис.1. Робота простого алгоритму формування сегменту лінії

11.3.3. Складний алгоритм (голономність + обмежена видимість). Розглянемо вільний від цих недоліків алгоритм формуваняя сегменту лінії. Загальна ідея: агент визначає (обирає) двох сусідів, і, якщо між ними є вільне місце, то намагається встати між ними, інакше він намагається встати поряд з ними. Алгоритм викноується i-им агентом, K – кількість виявлених сусідніх агентів, Ds - задана дистанція між сусідами (відстань, що розділяє сусідніх агентів в сегменті лінії).
1. Якщо ( K = 0 ), то рухатись далі, не змінюючи напрямку руху;
2. Якщо ( K = 1 ), то
- визначити відстань D до виявленого сусіднього агента;
- Якщо ( D > Ds ), то рухатись до виявленого сусіда (випадок 1, рис.2);
Інакше рухатись від нього (випадок 2, рис.3);
3. Якщо ( K = 2 ), то
- визначити відстані D1 і D2 до виявлених агентів A1 і A2;
- визначити відстань Dm до точки M, що ділить відрізок [A1A2] навпіл по формулі
(11.1)
та напрямок на цю точку по формулі
; (11.2)
Якщо ( Dm < D1 і Dm < D2 ), то
- рухатись до точки M (рис.4)
- Якщо ( D1 > Ds ), то рухатись до точки A1 (випадок 1);
Інакше рухатись від точки A1 (випадок 2);
- Якщо ( D2 > Ds ), то рухатись до точки A2 (випадок 1);
Інакше рухатись від точки A2 (випадок 2);
Інакше
Якщо ( Dm > D1 ), то
- рухатись до точки B1 на лінії A1A2, такій що B1 ( [A1A2] і [B1A1] < [B1A2] (рис.5);
- Якщо ( D1 > Ds ), то рухатись до точки A1 (випадок 1);
Інакше рухатись від точки A1 (випадок 2);
Інакше
- рухатись до точки B2 на лінії A1A2, такій що B2 ( [A1A2] и [B2A1] > [B2A2] (рис.6);
- Якщо ( D2 > Ds ), то рухатись до точки A2 (випадок 1);
Інакше рухатись від точки A2 (випадок 2);
4. Якщо ( K > 2 ), то визначити двох найближчих агентів: A1, A2 і перейти на крок 3.



Рис.2. Випадок, коли агент Ai знаходиться занадто далеко від сусіднього агента А1: D>Ds (Ds - задана умовами задачі розділяюча відстань, Ri - радіус видимості засобів детектування агента Ai)
Рис.3. Випадок, коли агент Ai знаходиться занадто
близько до сусіднього агента А1: D<Ds (Ds - задана
умовами задачі розділяюча відстань, Ri - радіус
видимості засобів детектування агента Ai)




Рис.4. Формування колективом агентів сегменту лінії:
ситуація, коли Dm<D1 і Dm<D2
Рис.5. Формування колективом агентів сегменту лінії:
ситуація, коли Dm>D1


Рис.6. Формування колективом агентів сегменту лінії:
ситуація, коли Dm>D2


11.3.4. Оскільки в даному випадку сегмент лінії формується в умовах обмеженого радіусу видимості, то алгоритм має ряд обмежень, основним з яких є обмеження на розмір кроку міжагентної відстані в сегменті лінії. Це обмеження має такий вигляд , (11.3)
де Rd - радіус видимости засобів детектування агента (розглядається однорідний колектив, в якому цей радіус однаковий для всіх агентів). Тобто крок сегменту лінії не може перевищувати радіусу видимості окремого агента. Крім цього можна вивести залежність розділяючої відстані від радіуса видимості та кількості агентів в колективі N. Ця залежність буде відображати перехід від більш простих умов повної видимості (коли кожний з агентів детектує (виявляє) усіх інших агентів) до більш складних умов обмеженої видимості. Згідно цій залежності, якщо
, (11.4)
то для формування сегменту лінії можна використати більш ефективний алгоритм для умов повної видості (відповідно формування сегменту лінії буде відбуватися швидше).
11.4. Приклад алгоритму узгодженого переміщення колективу.
11.4.1. Узгоджене переміщення агентів колективу в просторі передбачає зглажування траекторії руху кожного з агентів, за рахунок чого досягається більш плавне та стійке переміщення агентів в групі. Для цього кожний агент виконує для кожного свого j-го сусіда додавання двох векторів з використанням вагових коефіцієнтів:
L – вектор вирівнювання руху, який співпадає за напрямком з напрямком руху j-го сусіда,
D – вектор напрямку руху, який регулює дотримання дистанції до j-го сусіда (виходячи з заданої розділяючої відстнані Ds).
При цьому вектор D розглядається як два протилежних вектора:
Da - вектор зближення (attraction), який відповідає ситуаціям, коли відстань між да