Стигмергія: непряма координація через середовище

1. Що таке стигмергія

Стигмергія (від грецьк. stigma — «мітка», і ergon — «робота») — це механізм непрямої координації, коли агенти залишають сліди у спільному середовищі, і саме ці сліди — а не прямі повідомлення — запускають наступні дії інших агентів. Термін увів ентомолог П'єр-Поль Грассе у 1959 році, вивчаючи будівництво гнізд термітами, і згодом він став наріжним каменем досліджень роєвого інтелекту та мультиагентних систем.

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

2. Сематектонічна проти маркерної стигмергії

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

3. Математика феромонів

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

Термін випаровування ρ є критично важливим: без нього перший коли-небудь досліджений шлях домінував би назавжди, навіть якщо пізніше знайдено значно коротший. Випаровування дозволяє системі "забувати" застарілу інформацію та адаптуватись до змінного середовища.

4. Фуражування мурах і подвійний міст

Найяскравіша експериментальна демонстрація стигмергічної координації — експеримент з подвійним мостом Жана-Луї Денебура (1990): гніздо з'єднане з джерелом їжі двома шляхами різної довжини. Спочатку мурахи обирають кожну гілку приблизно випадково. Але мурахи, що йдуть коротшою гілкою, повертаються швидше, відкладаючи феромон з вищою швидкістю на одиницю часу, ніж ті, що на довшій гілці.

Це створює петлю позитивного зворотного зв'язку: більше феромону на короткому шляху приваблює більше мурах, які відкладають більше феромону, що приваблює ще більше мурах. За кілька хвилин майже вся колонія сходиться на найкоротшому шляху — при цьому жодна мурашка ніколи не "вирішує", який шлях коротший; рішення виникає суто з різниці у тривалості подорожей.

5. Стигмергія поза біологією

Стигмергію запозичено як шаблон проєктування далеко за межами біології:

• Оптимізація мурашиною колонією (ACO) — розв'язує задачу комівояжера та маршрутизацію мереж за допомогою віртуальних феромонних слідів на графі.
• Вікі та відкрите ПЗ — редагування та коміти є стигмергічними слідами, що спрямовують майбутніх учасників без прямої координації.
• Рої роботів — прості роботи залишають віртуальний "феромон" через радіомаяки чи фізичні мітки (світло, хімічний спрей) для координації пошуково-рятувального покриття.
• Міські стежки бажання — протоптані стежки на траві виявляють і закріплюють найефективніші пішохідні маршрути, підказуючи ландшафтним архітекторам, де насправді прокладати доріжки.

6. Компроміси проти прямої комунікації

Порівняно з явними протоколами переговорів, розглянутими у нашій статті про мультиагентні системи, стигмергія пропонує:

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

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

7. Псевдокод

function stepAntColony(ants, pheromone, dt):

  // 1. Випаровування — застосовується до кожного ребра щотику
  for each edge e in pheromone:
    pheromone[e] *= (1 - RHO)

  // 2. Кожна мурашка обирає наступне ребро ймовірнісно
  for each ant in ants:
    candidates = getAllowedEdges(ant)
    weights = candidates.map(e =>
      pow(pheromone[e], ALPHA) * pow(1/length(e), BETA)
    )
    edge = weightedRandomChoice(candidates, weights)
    ant.moveAlong(edge, dt)

    // 3. Відкладаємо феромон, поки мурашка йде
    pheromone[edge] += Q / ant.tripLengthSoFar

  // 4. Мурахи, що дійшли до гнізда, скидають лічильник подорожі
  for each ant in ants if ant.atNest:
    ant.tripLengthSoFar = 0

Типові константи: RHO = 0.1–0.3 (швидкість випаровування), ALPHA = 1 (вага феромону), BETA = 2–5 (вага евристики відстані), Q — константа масштабування відкладення.