Agent-Based Modelling: архітектура та дизайн

Що таке агент-орієнтоване моделювання?

Агент-орієнтована модель замінює одне глобальне рівняння популяцією автономних агентів, кожен з яких дотримується простих локальних правил і реагує лише на своє найближче оточення. Замість того, щоб розв'язувати "яка середня поведінка системи", ви симулюєте кожного індивіда й дозволяєте сукупному патерну виникнути знизу вгору. Це протилежний підхід до моделі диференціальних рівнянь на кшталт SIR чи Лотки-Вольтерри, які описують популяції як неперервні величини.

ABM — природний інструмент, коли важлива гетерогенність, локальна взаємодія чи дискретні рішення: пішоходи обирають вихід, домогосподарства обирають район, трейдери вирішують купувати чи продавати. Симуляції евакуації натовпу, сегрегації Шеллінга та Дилеми в'язня на цьому сайті — всі це ABM, побудовані на архітектурі, описаній нижче.

Стан агента та поведінка

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

Часта помилка — переплітати логіку поведінки з кодом рендерингу. Тримайте агентів як прості дані (Structure-of-Arrays або легкий клас) і трактуйте малювання як окремий прохід, що лише читає стан — це робить модель тривіально переносимою між Canvas 2D, WebGL і headless-запусками пакетів для перебору параметрів.

Цикл perceive-decide-act

Майже кожна агент-орієнтована модель, незалежно від домену, розбиває своє оновлення за тік на три фази:

Розділення decide і act — не стилістичний вибір, а те, що робить симуляцію незалежною від порядку обробки. Якщо агент A діє одразу після рішення, агент B (наступний у тій самій ітерації) сприйматиме нову позицію A замість тієї, яку A мав на початку тіку. Це непомітно змінює динаміку і робить результати залежними від порядку ітерації, що рідко буває бажаним.

Просторове індексування: сітки, quadtree, spatial hashing

Фаза perceive зазвичай потребує "хто поруч зі мною", і наївне сканування всіх пар O(N²) стає вузьким місцем уже за кілька тисяч агентів. Три структури покривають майже всі випадки використання ABM:

Для евакуації натовпу чи ринкової симуляції Больцмана-Парето рівномірна сітка з розміром клітини приблизно рівним радіусу взаємодії майже завжди є правильним першим вибором: перебудуйте її кожен тік за O(N), тоді кожен запит сусідів сканує лише блок 3×3 (9 клітин) навколо агента замість усієї популяції.

class SpatialGrid {
  constructor(cellSize) {
    this.cellSize = cellSize;
    this.cells = new Map();  // ключ: "cx,cy" -> масив індексів агентів
  }
  key(x, y) {
    const cx = Math.floor(x / this.cellSize);
    const cy = Math.floor(y / this.cellSize);
    return cx + ',' + cy;
  }
  rebuild(agents) {
    this.cells.clear();
    for (let i = 0; i < agents.length; i++) {
      const k = this.key(agents[i].x, agents[i].y);
      if (!this.cells.has(k)) this.cells.set(k, []);
      this.cells.get(k).push(i);
    }
  }
  neighbours(x, y, agents) {
    const cx = Math.floor(x / this.cellSize);
    const cy = Math.floor(y / this.cellSize);
    const out = [];
    for (let dx = -1; dx <= 1; dx++)
      for (let dy = -1; dy <= 1; dy++) {
        const bucket = this.cells.get((cx+dx) + ',' + (cy+dy));
        if (bucket) out.push(...bucket);
      }
    return out;
  }
}

Порядок планування: синхронний vs асинхронний

Окрім розділення decide/act, потрібно обрати хто оновлюється й коли:

• Синхронне (паралельне) оновлення: усі агенти сприймають один "заморожений" стан світу, потім усі діють разом. Детерміновано, легко паралелізується, але може створювати штучні артефакти лок-степ (наприклад, два агенти одночасно переходять у ту саму клітину в моделях типу клітинних автоматів).
• Асинхронне (послідовне) оновлення: агенти оновлюються по одному, кожен бачить результати всіх, оброблених до нього цього тіку. Дешевше для аналізу моделей прийняття/поширення думок, але результати залежать від порядку ітерації, якщо цей порядок сам не рандомізується щотіку.
• Випадкове асинхронне: перемішуйте порядок агентів щотіку перед послідовним оновленням — стандартний вибір для Voter Model і сегрегації Шеллінга, оскільки уникає систематичного упередження на користь агентів з малими індексами.

Звідки береться емерджентність

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

1. Локальна взаємодія: агенти реагують лише на найближчих агентів/клітини, ніколи на глобальне середнє.
2. Нелінійність або пороги: маленька зміна локальної змінної (ще один несхожий сусід, ще один панічний пішохід) може повністю змінити рішення агента.
3. Зворотний зв'язок: дія агента змінює локальне оточення, яке сусіди сприймають наступного тіку, що змінює їхні дії, які знову змінюють оточення.

Саме тому модель сегрегації Томаса Шеллінга така вражаюча: жоден агент у моделі не має сильної переваги до повної сегрегації — достатньо порогу "лише 30% схожих сусідів" — але емерджентний патерн на рівні цілого міста наближається до повного розділення. Урок узагальнюється: щоб зрозуміти складний соціальний патерн, шукайте просте локальне правило і петлю зворотного зв'язку, що його підсилює, а не одну "причину" на рівні системи.

Мінімальний скелет ABM на JavaScript

Зібравши все з попередніх розділів, ось форма, якої дотримується кожна ABM на цьому сайті — просторовий індекс, розділення decide/act і рандомізоване планування:

class Simulation {
  constructor(n, worldSize) {
    this.agents = Array.from({ length: n }, () => ({
      x: Math.random() * worldSize,
      y: Math.random() * worldSize,
      vx: 0, vy: 0,
      state: 'idle',
    }));
    this.grid = new SpatialGrid(10);
  }

  step(dt) {
    this.grid.rebuild(this.agents);
    const order = this.agents.map((_, i) => i);
    shuffle(order); // випадкове асинхронне планування

    // 1) DECIDE — обчислити наміри, не мутуючи стан
    const intents = new Array(this.agents.length);
    for (const i of order) {
      const a = this.agents[i];
      const nearby = this.grid.neighbours(a.x, a.y, this.agents);
      intents[i] = decide(a, nearby, this.agents);
    }
    // 2) ACT — застосувати всі наміри
    for (const i of order) {
      act(this.agents[i], intents[i], dt);
    }
  }
}

Усе інше — Social Force Model для евакуації, оновлення стратегій за матрицею виграшів для Дилеми в'язня чи поріг схожості Шеллінга — підключається до decide() і act(). Каркас навколо (сітка, планування, подвійна буферизація) лишається тим самим у радикально різних доменах.