Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекція 6. Колективне навчання (1).
6.1. Стратегії колективного навчання
6.2. Постановка задачі колективного навчання з підкріпленням
6.3. Проблема розпізнавання стану та інтерпретації відгуку середовища
6.4. Класифікація задач колективного навчання з підкріпленням
6.5. Одночасне ізольоване навчання з підкріпленням
6.6. Інтерактивне навчання узгодженим діям
6.1. Стратегії колективного навчання
-- "надзвичайні" можливості (приклади: 1) мобільний робот з великою точністю може пам’ятати весь пройдений ним шлях від деякої стартової позиції; 2) один мобільний робот може "подивитись" на світ "очами" іншого мобільного робота; 3) агенти можуть з надзвичайно великою швидкістю обмінюватись великими об’ємами інформації та багато інших можливостей) -> як використовувати ці "надзвичайні" можливості при розробці багатоагентних систем? Цікаве рішення: влаштувати так, щоб багатоагентна система самостійно навчалась наперед невідомим способам використання "надзвичайних" можливостей для вирішення поставлених перед нею задач (наприклад, в рамках еволюційного підходу).
-- стратегії колективного навчання [в порядку зростання складності]:
1. Навчання шляхом механічного запам’ятовування (rote learning): безпосереднє запам’ятовування досвіду та навичок, здобутих іншими агентами, без їх подальших змін та "переосмислення".
2. Навчання шляхом обміну інструкціями та порадами (learning from instruction and by advice taking), які не передбачають їх обов’язкового виконання (на власний розсуд).
3. Навчання на прикладі інших агентів (learning from examples and by practice): використання кожним агентом власних спостережень або інформації про вдалі чи невдалі дії інших агентів для прийняття рішень.
4. Навчання за аналогією (learning by analogy): модифікація вже знайдених рішень одних задач колективної поведінки для вирішення інших подібних за змістом нових задач.
5. Навчання на основі досліджень (learning by discovery): здобуття нових знань та навичок шляхом спостережень, планування та проведення експерементів, синтезу та перевірки гіпотез на основі результатів спостережень та експерементів.
6.2. Постановка задачі колективного навчання з підкріпленням
-- Передбачається, що агенти колективу мають повністю або частково спільну мету навчання (у відповідності до тих задач, що поставлені перед колективом агентів розробником). В такому випадку зміст колективного навчання з підкріпленням полягає у:
-- Основний момент полягає в тому, що кожний окремий агент отримує відгук середовища не на власну індивідуальну дію, а на сумісні дії всього колективу (тобто так звану колективну дію). В більшості випадків це різко ускладнює процес навчання з підкріпленням, оскільки з’являється додаткова невизначеність щодо того, дії яких агентів призвели до отриманого усім колективом результату (позитивного або негативного). З іншого боку можна зробити припущення, що за рахунок колективних зусиль навчання може відбуватися значно швидше в порівнянні з індивідуальним навчанням, наприклад, за рахунок використання кожним окремим агентом досвіду інших агентів колективу.
-- Приклад модифікації задачі навчання з підкріпленням в маркіському випадковому середовищі для випадку колектива агентів: N – кількість агентів в колективі, Ai – множина доступних i-му агенту дій, S – множина станів середовища, R – функція виграшу (функція підкріплення), T – функція переходів.
|
Правило нарахування виграшів (reward rule) та правило переходу (transition rule) |
Функція виграшу (reward function) та функція переходу (transition function) |
|
|
Individual RL, індивідуальне навчання з підкріпленням |
R: SA→ T: SA → S |
R(s,a) → rt , rt T(s,a) → s′, s,s′S |
|
Multiagent RL, багатоагентне навчання з підкріпленням |
R: S A1…AN→ T: SA1…AN → S |
R(s,a1,a2,…,aN) → {ri,t} T(s,a1,a2,…,aN) → s′ |
-- Замість стохастичних функцій вигаршу та перехду з двома аргументами (Individual RL) розглядаються функції вигаршу та перехду з N незалежними аргументами (по кількості агентів).
-- Опосередкований зв’язок цих аргументів (в межах деякого методу навчання з підкріпленням) визначає два способи колективного навчання:
-- Основний висновок (по прикладу): різке ускладнення задачі, по-перше за рахунок зростання розмірності задачі, і, по-друге, за рахунок виникнення нових видів невизначеності.
-- Зауваження:
6.3. Проблема розпізнавання стану та
інтерпретації відгуку середовища
-- проблема розпізнавання стану середовища
-- В загальному випадку проблема інтерпретації відгуку середовища (credit-assignment problem САР) полягає у визначенні того, яка дія або послідовність дій системи (окремого агента або колективу) призвели до отриманого виграшу (програшу) на даному кроці взаємодії з середовищем.
-- Для багатоагентних систем загальну САР зручно розбити на дві підпроблеми:
-- На практиці ці дві проблеми вирішуються одночасно, тобто в більшості методів колективного навчання не має чіткого поділу між цими проблемами.
-- Приклад між-агентної проблеми інтерпретації відгуку середовища (рис.6.1). Колектив з чотирьох агентів (N=4) отримує виграш у розмірі 90 одиниць за колективну дію (a11, a21, a32, a42) A1A2A3A4, де aij – j-та дія i-го агента. В даному прикладі цей виграш розподілився між агентами в наступний спосіб: перший агент отримав 10 одиниць виграшу, другий – також 10, третій – 40 і четвертий – 30. В загальному випадку механізм розподілу спільного виграшу є інтегральною частиною алгоритму колективного навчання.
Рис.6.1. Приклад між-агентної проблеми
інтерпретації відгуку середовища.
6.4. Класифікація задач колективного навчання з підкріпленням
1) за метою навчання -> дві основні мети навчання:
- оптимальна схема взаємодії агентів -> оптимальний спосіб організації колективних дій (приклади: розподіл функцій (спеціалізація) в середені колективу, розподіл спільного ресурсу, регулювання рівня інформаційної зв’язності)
- оптимальна колективна поведінка в середовищі, в якому розміщені агенти -> оптимальний спосіб взаємодії колективу з середовищем (згідно обраної моделі оптимальної колективної поведінки) (приклади: перевезення вантажів, виявлення порушників заданого периметру, розподіл обчислювального навантаження)
|
Фіксована схема взаємодії агентів |
Змінна схема взаємодії агентів |
|
|
Фіксований спосіб взаємодії з середовищем |
навчання відсутнє |
навчання міжагентній взаємодії |
|
Змінний спосіб взаємодії з середовищем |
навчання взаємодії з середовищем |
одночасне навчання міжагентній взаємодії та взаємодії з середовищем |
2) за способом інформаційної взаємодії
- без інформаційної взаємодії між агентами (так зване ізольоване навчання)
- з інформаційною взаємодією (так зване інтерактивне навчання)
- з обмеженою (локальною) інформаційною взаємодією
- з "необмеженою" інформаційною взаємодією
3) за типом колективних дій
- сильнозв’язані/слабозв’язані дії агентів
- рівноцінні/нерівноцінні по впливу дії агентів
- кількісний/синергетичний еффект спільних дій
4) за організацією процесу навчання у часі
- одночасне (паралельне) навчання
- навчання з зсувом у часі (staggered of lock-step learning) -> кожному агенту відводиться певний час, на протязі якого він один серед усіх інших агентів навчається; після цього він реалізує ту поведінку, який навчився (а до навчання переходить інший агент)
6.5. Одночасне ізольоване навчання з підкріпленням
Concurrent Isolated Reinforcement Learning
-- Кожний агент виконує індивідуальний алгоритм навчання з підкріпленням (при цьому інші агенти не моделюються). Обмін інформацією між агентами відсутній (несамовиявлений колектив). Мета колективного навчання – знайти оптимальну колективну поведінку. Основна проблема – формування таких індивідуальних функцій виграшу та оцінки, які б гарантували збіжність колективної поведінки до оптимальної (це варіант основної проблеми ТКП для процесу навчання).
-- Одночасне ізольоване навчання з підкріпленням набуває особливої ваги в ситуаціях, коли зв’язок між агентами або взагалі неможливий, або тимчасово недоступний (аварія або збій в роботі систем зв’язку; високий рівень завад, наприклад, внаслідок навмисних дій ворогуючих сторін).
-- Два випадки застосування таких алгоритмів:
6.6. Інтерактивне навчання узгодженим діям
Interactive Reinforcement Learning of Coordination
-- На кожному кроці взаємодії агенти повідомляють один одному, які дії вони збираються реалізувати або повідомляють свій вибір на попередніх кроках взаємодії. При цьому кожний агент "моделює" поведінку інших агентів, що дає змогу оцінити які дії агентів в межах всього колективу є найбільш успішними.
-- Приклад (N = 3): Якщо двоє "сусідів" і сам агент реалізували першу дію і лише один "сусід" реалізував другу дію, і в наслідок цих колективних зусиль було отримано виграш, то ваговий коефіцієнт першої дії треба збільшити, оскільки саме вона швидше за все призвела до цього виграшу.
-- В даному випадку за рахунок обміну інформацією в рамках відповідної моделі інформаційної зв’язності з’являється можливість в явний спосіб обирати (організовувати) узгоджені колективні дії. При цьому використовуються різні схеми (методи, алгоритми) узгодження.
-- Приклад ідеї методу узгодження: Кожний з агентів формує вагові коефіцієнти, що відповідають діям, які він може реалізувати, і повідомляє значення цих коефіцієнтів іншим агентам. Після кожного кроку взаємодії з середовищем значення всіх вагових коефіцієнтів модифікуються згідно заданого правила навчання з підкріпленням з урахуванням значень вагових коефіцієнтів, що надійшли від інших агентів. Внаслідок цього з часом колектив знаходить оптимальну поведінку у вигляді дійсних вагових коефіцієнтів дій.
-- Приклад методу колективного навчання з підкріпленням: Модифікація методу зваженої оцінки дій для випадку колективу агентів -> Оціночна вага дії перераховується не лише на основі власного "досвіду", але і на основі "досвіду", здобутого іншими агентами.
-- Інтуїтивно можна зробити висновок пришвидшення процесу навчання (тобто збіжності значень оціночної ваги до дійсних значень) за рахунок збільшення кількості вибірок (samles)
-- Для даного прикладу: чим більша пропускна здатність системи міжагентого зв’язку, тим швидше відбувається процес навчання
-- проблема розпізнавання стану середовища
-- проблема формування глобального відгуку