Теорія колективної поведінки інтелектуальних систем (ТКП) (22 лекції, 4 курс, КСМ)
Частина 1. Основні приципи теорії колективної поведінки (9 лекцій)
1. Предмет і задачі ТКП. Основні ідеї та визначення.
1.1. Предмет і задачі теорії колективної поведінки (ТКП).
1.2. Інтелектуальна система (агент).
1.3. Поняття функціональної цілісності. Принцип колективної дії.
1.4. Поняття елементарного поведінкового акту. Гіпотеза М.Л. Цетліна про простоту.
1.5. Наукові напрямки, що складають ТКП.
2. Поняття агента в ТКП. Узагальнена функціональна структура агента.
2.1. Визначення інтелектуальної системи (агента).
2.2. Поняття середовища агента. Типи середовища.
2.3. Узагальнена функціональна структура агента.
2.4. Формальний опис системи <середовище, колектив>.
2.5. Цільовоа функція агента (agent utility function).
2.6. Класифікація агентів. Приклади змістовної інтерпретації.
3. Поняття колективу в ТКП.
3.1. Визначення колективу агентів (багатоагентної системи).
3.2. Основні характеристики колективу агентів.
3.3. Цільова функція колективу (world utility function).
3.4. Способи опису колективної поведінки.
3.5. Основна проблема ТКП.
4. Децентралізоване та централізоване управління. Самоорганізація.
4.1. Визначення централізованого та децентралізованого управління.
4.2. Порівняння централізованого та децентралізованого управління на прикладі.
4.3. Ентропія (невизначенність) за К. Шеноном (C. Shannon).
4.4. Визначення самоорганізації. Міра порядку (фон Фьорстер).
4.5. Правило самоорганізації.
5. Однорідність та неоднорідність колективу агентів.
1. Поняття однорідності та неоднорідності.
2. Адаптивне управління з механізмом наслідування.
3. Гнучкість та цілеспрямованість колективної поведінки.
4. Приклад моделі колективної поведінки з адаптивним управлінням.
5. Спеціалізація (формування груп взаємодоповнюючих стратегій).
6. Співпраця та суперництво в колективі агентів.
6.1. Поняття співпраці (cooperation) та суперницства (competition).
6.2. Співвідношення між індивідуальною та колективною продуктивністю.
6.3. Ітераційна ділема ув’язненого (Iterated Prisoners Dilemma, IPD).
7. Колективні моделі реальності. Колективне знання.
7.1. Визначення колективної моделі реальності (КМР).
7.2. Приклад організації пам’яті агента на основі його узагальненої функціональної структури.
7.3. Колективне знання.
7.4. Схема утворення колективного знання.
7.5. Способи збереження даних колективних моделей.
8. Колективне прийняття рішень.
8.1. Поняття колективного прийняття рішень.
8.2. Функія колективного вибору.
8.3. Теорема Ерроу про неможливість (парадокс Ерроу, K.J.Arrow).
9. Спілкування в колективі агентів.
9.1. Основна проблема розподілених систем.
9.2. Поняття інформаційної зв’язності.
9.3. Мови спілкування агентів.
Частина 2. Базові алгоритми колективної поведінки (5 лекцій)
10. Утворення колективу. Самоіменування. Самоузгодження.
10.1. Архітектура інтегрального підпорядкування (subsumption architecture, Р.Брукс).
10.2. Основні вимоги до базових алгоритмів колективної поведінки.
10.3. Утворення колективу: самовиявлення (detecting).
10.4. Самоіменування: генерація унікальних імен агентів.
10.5. Самоузгодження: домовленність про однакову для всіх величину.
11. Самоорганізація колективу агентів у просторі (самовпорядкування).
11.1. Загальна постановка задачі самовпорядкування.
11.2. Класифікація задач самовпорядкування за складністю.
11.3. Самоорганізація в задачах самовпорядкування.
11.4. Впорядковане розміщення у просторі (ordered placement).
11.5. Формування правильних геометричних фігур (geometric pattern formation).
11.6. Приклад алгоритму формування сегменту лінії (К.Сугіхара, І.Сузукі).
11.7. Управління впорядкованим переміщенням (motion control).
11.8. Приклад алгоритму узгодженого групового переміщення (Д.Кромбі).
12. Самоорганізація колективу агентів у часі (самосинхронізація).
12.1. Постановка задачі самосинхронізації колективу.
12.2. Дискретний та аналоговий варіанти задачі самосинхронізації.
12.3. Задача синхронізації ланцюжку стрільців (firing squad synchronization problem, Дж. Майхіл).
12.4. Приклад алгоритму самосинхронізації ланцюжку агентів.
12.5. Самосинхронізація агентів поєднаних статичною мережею зв’язків.
12.6. Самосинхронізація агентів за наявності затримок.
13. Навчання з підкріпленням (самонавчання).
13.1. Зміст та елементи навчання з підкріпленням (Р.Саттон, А.Барто).
13.2. Стаціонарне випадкове середовище (n-armed bandit problem).
13.3. Цілеспрямованість поведінки (М.Л.Цетлін).
13.4. Співвідношення долідження (exploring) та користування (exploiting).
13.5. Метод зваженої оцінки дій (Action-Value Method).
13.6. Середовище з перемиканням (Markov Decision Processes).
13.7. Навчання за методом часових різниць (Temporal Difference Learning).
13.8. Q-навчання (Q-learning).
14. Колективне навчання з підкріпленням (колективне самонавчання).
14.1. Проблема формування відгуку середовища (credit-assignment problem).
14.2. Одночасне ізольоване навчання з підкріпленням (concurrent isolated RL).
14.3. Інтерактивне самонавчання узгодженим діям (interactive RL of coordination).
14.4. Самонавчання та спілкування.
14.5. Зменшення спілкування за рахунок навчання.
14.6. Покращення навчання за рахунок спілкування.
Частина 3. Моделі колективної поведінки (8 лекцій)
15. Опис моделей колективної поведінки в термінах теорії ігор.
15.1. Основні властивості ігор з нулевою сумою. Рівновага за Нешем.
15.2. Ігри з послідовним повторенням партій.
15.3. Стохастичні ігри.
15.4. Рекурсивні ігри.
15.5. Ігри на виживання.
15.6. Ігри на виснаження.
15.7. Ігри з непротележними інтересами гравців.
15.8. Кооперативні ігри.
16. Однорідні симетричні ігри цілеспрямованих автоматів.
16.1. Однорідні ігри з обмеженою взаємодією.
16.2. Однорідна гра на колі.
16.3. Гра в розміщення.
16.4. Гра в розподілення.
16.5. Процедура "спільної каси" (common cash).
16.6. Гра Гура. Співпраця та суперництво в грі Гура.
17. Економічні моделі колективної поведінки.
17.1. Поняття ринкової рівноваги (general equilibrium theory).
17.2. Моделі ринкових механізмів (general equilibrium market mechanisms).
17.3. Проблема "відвідування барів" (El Farol Bar problem).
17.4. Мінорна гра (minority game).
17.5. Створення механізмів взаємодії (mechanism design).
17.6. Аукціони (auctions).
17.7. Досягнення домовленностей шляхом переговорів (nagotiations).
18. Еволюційні моделі колективної поведінки.
18.1. Природний відбір. Поняття екологічної рівноваги.
18.2. Штучне життя (Artificial life). Популяційна динаміка.
18.3. Еволюційні обчислення (evolutionary computation).
18.4. Генетичні алгоритми (genetic algorithms).
18.5. Еволюційне програмування (evolutionary programming).
18.6. Генетичне програмування (genetic programming).
18.7. Кліткові автомати (celular automata, Дж. фон Нейман).
19. Методи пошуку припустимого рішення. Колективний пошук в реальному часі.
19.1. Проблема розподіленого пошуку припустимого рішення (constraint satisfaction).
19.2. Методи розподіленого пошуку припустимого рішення.
19.3. Алгоритми пошуку в реальному часі.
19.4. Пошук рухомої цілі (moving target search).
19.5. Співпраця в умовах нестачі інформації.
19.6. Організація колективу для вирішення проблем (forming problem solving organizations).
19.7. Задача побудови башти (tower building task).
20. Задача механічного врівноваження. Узагальнене поняття рівноваги.
20.1. Постановка задачі механічного врівноваження.
20.2. Аналіз задачі врівноваження. Граф розміщень.
20.3. Узагальнене поняття рівноваги.
20.4. Критерії ефективності алгоритмів врівноваження.
20.5. Централізоване врівноваження.
20.6. Децентралізоване врівноваження несамовиявленим колективом.
20.7. Децентралізоване врівноваження самовиявленим колективом.
21. Колективна поведінка обчислювальних агентів. Мобільні обчислення.
21.1. Моделі розподілених обчислень.
21.2. Мобільний код (mobile code) та мобільні агенти (mobile agents).
21.3. Мобільні обчислення (mobile computing).
21.4. Концепція обчислювальних екологій (computational ecologies, XEROX).
21.5. Самоорганізація динамічних розподілених обчислювальних систем (HP).
21.6. Концепція автономних обчислень (autonomic computing, IBM).
22. Колективна поведінка вимірювальних агентів. Мобільні вимірювання.
22.1. Розподілені вимірювально-обчислювальні системи.
22.2. Картографування (mapping).
22.3. Колективний пошук (search), локалізація (localization) та відслідковування траекторій (tracking).
22.4. Розподілені контактні вимірювання (distributed sensing).
22.5. Інтерполяційна модель колективної поведінки вимірювальних агентів.
22.6. Проблема розміщення вимірювальних агентів.
22.7. Алгоритми поведінки вимірювальних агентів.