Лекція 19. Розподілений штучний інтелект:
моделі колективної поведінки
1. Розподілений пошук припустимого рішення (Distributed Constraint Satisfaction)
Постановка задачі. Проблема пошуку припустимого рішення (CSP, distributed constraint satisfaction problem) задається трійкою P=<X,D,C>, де
X = {x1,x2,…,xn} – множина змінних
D = {D1,D2, …,Dn} – множина обмежених дискретних областей визначення відповідних змінних,
C = {C1(K1),C2(K2), …,Cm(Km)} – множина обмежень, що накладаються на значення змінних, Ki(X – підмножина змінних, Ci – предикат (логічна умова, яка приймає значення істина, якщо всі змінні з Ki одночасно приймають задані значення)
Треба знайти хоча б одне (не обов’язково оптимальне) рішення X* з множини усіх можливих комбінацій X(D1(D2(…(Dn, яке б відповідало заданим обмеженням (було припустимим).
Розподіелний пошук припустимого рішення. Змінні та обмеження розподілені між агентами. В найпростішому випадку одному агенту ставиться у відпоідність одна змінна. При цьому агент знає всі обмеження, в яких "задіяна" ця змінна.
Вирішення задачі. Два основних підходи 1) generate-and-test (consistency) 2) backtracking (search)
Приклад. Задача про розміщення чотирьох королев. Треба розмістити 4 королеви на дошці 4 на 4 в такій спосіб, щоб вони не загрожували одна одній (будь-яким двом королевам забороняється стояти в одному рядку, в одному стовпцю та на одній діагоналі). Кожна з королев може рухатись лише в своєму рядку. Початкове розміщення – випадкове.

X = {x1,x2,x3,x4}
D = {D1,D2,D3,D4}, Di([1,2,3,4]
C = {C1,C2,C3,C4}, Ci = {<b,c>|b(Di, c(Dj, b(c, i - j ( b - c, i - j ( c - b}
2. Пошук в реальному часі (Realtime Search)
Постановка задачі. На заданому ненаправленому графі, в будь-яких двох вершинах випадковим чином розміщюються ціль (target) та агент. Перед агентом ставиться мета знайти найкоротший (найшвидший) шлях до цілі. Довжина шляху складається з суми цілих чисел, що приписані ребрам графу. За одни такт агент поже перейти на одну сусідню вершину (вибір). В кожній вершині агент бачить "відстань" до цілі (кількість вершин, що відділяють його від цілі).
Пошук рухомої цілі (moving target search), Колективний пошук (N>=2). Вирішення задачі. Приклад.
3. Організоване вирішення проблем (problem solving organization)
Постановка задачі. Вирішення задачі. Приклад. Задача побудови башти (tower building task).
Задача побудови вежі сформульована японським вченим Тору Ішида як тестова задача для оцінки рівня інтелектуальності колективної поведінки агентів різної архітектури (в даному випадку інтелектуальність розуміється як здатність самостійно знаходити спосіб вирішення складної проблеми). Рішення задачі базується на алгоритмах пошуку в реальному часі (real-time search).
В задачі розглядається обмежений дискретний двовимірний простір, який складається з прямокутних комірок (“черепичний світ”). В центрі цього простору в одній з комірок знаходиться “будівельний майданчик”, на якому має буди зведена вежа. “Будівельні блоки”, кожний з яких також займає одну комірку, випадковим чином розкидані у просторі. Перед колективом агентів ставиться завдання за як можна меншу кількість часових кроків побудувати вежу (знайти та встановити блоки на “будівельному майданчику” згідно їх порядкових номерів). Метою досліджень є знаходження таких архітектур агентів, які б дозволяли колективу агентів самостійно знаходити найкращі (найшвидші) наперед невідомі досліднику способи (алгоритми) побудови вежі. Алгоритми: 1) некоординовані агенти, 2) скоординовані агенти 3) організовані агенти