Пошук по сайту


Лекція 11. Самоорганізація колективу агентів у просторі (самовпорядкування) >11 Постановка задачі самовпорядкування

Лекція 11. Самоорганізація колективу агентів у просторі (самовпорядкування) >11 Постановка задачі самовпорядкування


2004

Лекція 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: Ds (Ds - задана

умовами задачі розділяюча відстань, Ri - радіус

видимості засобів детектування агента Ai)





Рис.4. Формування колективом агентів сегменту лінії:

ситуація, коли Dm1 і Dm2

Рис.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 розглядається як два протилежних вектора:

    1. Da - вектор зближення (attraction), який відповідає ситуаціям, коли відстань між даним агентом Ai та його j-им “сусідом” Aj [AiAj] > Ds (рис.7) і

    2. Dr - вектор відштовхування (repulsion), який відповідає ситуаціям, коли відстань між даним агентом Ai та його j-им “сусідом” Aj [AiAj] < Ds (рис.8).

Тобто в першій ситуації (рис.7) результуючий вектор шукається як векторна сума

R = wlL + waDa , (11.5)

а в другій ситуації (рис.8) як векторна сума

R = wlL + wrDr . (11.6)

11.4.2. Використання коефіцієнтів wl, wa, wr дозволяє збільшувати та зменшувати пріоритетність різних дій агента, в залежності від ситуації, що склалася. Наприклад, в ситуації, коли відстань між сусідніми агентами набагато перевищує розділяючу дистанцію, більш важливою задачею для цих агентів є рух в напрямку зближення (вектор Da), ніж рух в напрямку згладжування своїх траекторій (вектор L). Так само, коли відстань між ними набагато менше розділяючої дистанції, то більш важливим для них є рук в напрямку відштовхування (вектор Dr).
Одним з можливих рішень проблеми пріоритетності напрямків руху є формування вагових коефіцієнтів наступним чином:

, (11.7)

, (11.8)

, (11.9)

де D – біжуча відстань між Ai і Aj,

Rd - радіус видимості засобів детектування сусідніх агентів.
При цьому залежність вагових коефіцієнтів від біжучої відстані між сусідніми агентами буде мати наступний вигляд (рис.9). Ця залежність демонструє в який спосіб вирішується в даному випадку проблема пріоритетності напрямків руху. Зокрема можна побачити, що, коли агент опиняється на заданій розділяючій відстані від сусіда (D = Ds), вагові коефіцієнти wa и wr приймають нульові значення і рух агента здійснюється лише в напрямку вирівнювання траектроії.




Рис.7. Зглажування траекторії руху агента в групі (ситуація зближення)



Рис.8. Зглажування траекторії руху агента в групі (ситуація відштовхування)






Рис.9. Залежність
вагових коефіцієнтів wl, wa, wr
від відстані D
між сусідніми агентами
(Ds=60, Rd = 120)


поділитися в соціальних мережах



Схожі:

Уроку Тема, зміст уроку
Аналіз контрольної роботи. Робота над помилками. Задачі на перпендикулярність прямих І площин у просторі

Лекція 4 поверхні
Це визначення дозволяє розглянути поверхню як неперервну множину послідовних положень змінної лінії – твірної, що рухається в просторі...

Тема: Декартові координати в просторі. Перетворення фігур в просторі...
На осі ординат знайдіть точку М, відстань від якої до точки А(4; 3; 0) дорівнює 5

Застосування векторів до розв’язування простих задач на площині та...

Урок в темі №1 Тема уроку. Аналіз контрольної роботи. Взаємне розміщення прямих у просторі
«Вектори»; повторити, привести в систему й розширити відомості про взаємне розміщення двох прямих у просторі

Задачі з географії
Лавренчук Г. М. Задачі з географії: навчально-методичний посібник. – Біла Церква, 2009. – 60 с

Нестандартних задач з математики
Для формування логічних умінь учнів необхідна цілеспрямована система вправ. Я пропонувала учням цікаві нестандартні задачі, що вимагають...

Освітньо-виховної роботи
Завдання педагогічного колективу комунального санаторного дошкільного навчального закладу №164

Розв'язування задач на знаходження суми І остачі. Пряма лінія. Відрізок Мета
...

| Організаційно-підготовчий етап. 1Визначення проблеми яка спонукає до роботи
Постановка мети І завдання проекту. 3Проведення міні-маркетингових досліджень, спрямованих на вибір об’єкта проектування. 4Історико-технічна...



База даних захищена авторським правом © 2017
звернутися до адміністрації

geo.lekciya.com.ua
Головна сторінка