Мультиагентні системи: координація та переговори

1. Що таке мультиагентна система

Мультиагентна система (MAS) — це набір автономних агентів, які поділяють спільне середовище, сприймають його через локальні сенсори та впливають на нього через локальні дії, при цьому жоден агент не володіє повним глобальним станом. Кожен агент переслідує власну мету — доставити пакунок, зібрати ресурс, захистити територію — але система в цілому не повинна впадати в хаос: агенти не мають зіштовхуватись, марнувати ресурси чи працювати всупереч одне одному.

Дослідження MAS перебуває на перетині розподілених обчислень, теорії ігор та штучного інтелекту. Воно лежить в основі роєвої робототехніки, алгоритмічної торгівлі, команд роботів для ліквідації наслідків катастроф, мереж світлофорів та ігрового ШІ. Центральне питання завжди одне й те саме: як отримати емерджентну, корисну глобальну поведінку з суто локальних рішень?

2. Механізми координації

Кожна реальна система поєднує ці механізми. Флот доставних роботів може використовувати аукціон для розподілу посилок, протокол переговорів для обміну посилками при зміні маршрутів і алгоритм консенсусу для узгодження спільної карти заблокованих доріг.

Централізована проти децентралізованої координації

Централізований координатор має повну видимість і видає оптимальні (або близькі до оптимальних) команди, але є єдиною точкою відмови і погано масштабується понад кілька сотень агентів. Децентралізований протокол масштабується до тисяч агентів і толерує окремі відмови, ціною втрати гарантій доведено оптимального рішення — децентралізовані рішення зазвичай лише локально оптимальні.

3. Contract Net Protocol

Contract Net Protocol (CNP), запропонований Рідом Дж. Смітом у 1980 році, — це архетипний протокол переговорів для розподілу завдань у розподілених системах. Він працює у чотири етапи:

1. Оголошення — менеджер розсилає запит на пропозиції (CFP), що описує завдання та обмеження.
2. Подання заявок — кожен здатний виконати завдання агент обчислює свою вартість чи корисність і відповідає заявкою.
3. Присудження — менеджер порівнює всі заявки та присуджує контракт найкращій (найнижча вартість або найвища корисність).
4. Виконання та звітування — переможець виконує завдання і повідомляє результат менеджеру.

4. Аукціони та розподіл завдань

Аукціони узагальнюють ідею Contract Net з добре вивченими теоретико-ігровими властивостями. Три найпоширеніші формати в літературі MAS:

• Англійський аукціон — ціна зростає, учасники відкрито перебивають ставки одне одного, доки не залишиться один.
• Закрита заявка першої ціни — кожен агент подає одну приховану заявку; найвищий переможець платить власну ставку.
• Аукціон Вікрі (другої ціни) — переможець найвищої заявки платить другу за розміром ставку, що робить чесну ставку домінантною стратегією.

У комбінаторних аукціонах агенти роблять ставки на пакети завдань, а не на окремі елементи, що краще відображає синергії (наприклад, дві доставки на одній вулиці дешевші разом), але робить визначення переможця NP-складним у загальному випадку.

5. Алгоритми консенсусу

Протоколи консенсусу дозволяють групі агентів узгодити єдине значення — точку збору, середнє показання сенсора, лідера — використовуючи лише локальну комунікацію з сусідами, без трансляції всім одразу.

Це просте правило оновлення лежить в основі вирівнювання швидкостей при флокінгу (див. нашу статтю про Boids), розподіленого злиття даних сенсорів і блокчейн-подібного узгодження (хоча з набагато суворішими вимогами до відмовостійкості у візантійському випадку, коли деякі агенти можуть брехати).

6. Комунікація та мовленнєві акти

Щоб агенти могли вести переговори, їм потрібен спільний словник. Стандарт FIPA-ACL (Agent Communication Language) визначає набір перформативів — мовленнєвих актів, запозичених із лінгвістики — які надають кожному повідомленню однозначний намір:

• cfp — запит на пропозиції (початок раунду Contract Net)
• propose — заявка чи контрпропозиція
• accept-proposal / reject-proposal — рішення менеджера
• inform — повідомлення факту чи спостереження
• request — прохання до іншого агента виконати дію

Така структура повідомлень дозволяє різнорідним агентам — створеним різними командами, різними мовами — взаємодіяти, бо значення повідомлення стандартизоване навіть тоді, коли зміст відрізняється.

7. Псевдокод: Contract Net Protocol

function runContractNet(manager, contractors, task):

  // 1. Оголошення
  manager.broadcast(cfp(task), contractors)

  // 2. Подання заявок
  bids = []
  for each agent in contractors:
    if agent.canPerform(task):
      cost = agent.estimateCost(task)
      bids.push({agent, cost})

  // 3. Присудження — обираємо найдешевшу заявку
  if bids.length == 0:
    return null  // ніхто не може виконати
  winner = minBy(bids, b => b.cost)
  manager.send(accept-proposal, winner.agent)
  for each other in bids if other != winner:
    manager.send(reject-proposal, other.agent)

  // 4. Виконання та звітування
  result = winner.agent.execute(task)
  winner.agent.send(inform(result), manager)
  return result

Реальні варіанти додають тайм-аути (заявки повинні надійти до дедлайну), повторне оголошення (якщо переможець зазнає невдачі, повторити протокол серед решти підрядників) та вкладені контракти (підрядник може стати менеджером для підзавдань).