Децентрализованное клеточноавтоматное планирование эвакуации раненых

Децентрализованно планируем эвакуацию раненых: под огнем, в бардаке, с постоянно меняющимся путем отхода и нервным поиском плана Б, если…, вернее, когда.

Привет, я Егор The Hawk, и я тоже, своего рода, разработчик. Надо успеть написать про работу, пока не завершил карьеру. Постараюсь кратко. Геймдевелоперам зайдет.

Поле боя, оно же Сцена — это слоистая карта. Самый нижний слой — клеточный автомат шестиугольных ячеек («хексов»), передающих Воздействие своим соседям. Оно влияет на меру риска для эвакуационных групп, а ячейки обычно связаны и отражают то, что на них стоит — Недвижимость. Недвижимость «Мост» после «Воздействия» «Тюльпана» превращается в тыкву «Завал», что влияет потом на построение маршрутов.

Размер хексов — несколько метров, и их слишком дофига, чтобы наши носимые «ПипБои» и «Еписи» вмещали их много, поэтому близколежащие однотипные хексы сжимаются в «зоны» чтобы Епись держала хотя бы локальную область карты.

Поэтому планирование маршрутов децентрализовано и опирается на Dec‑POMDP — это модель координации и принятия решений между множеством агентов, но поля тут слишком узки, чтобы углубляться, поэтому направьте свои стопы в википедию и гугл, искать по «Шломо Зильбирштейн». Это как Майлз Дайсон, только полурак, и я его еще не раз вспомню добрым словом: отладить и заставить это работать второй раз — нет, спасибо. Пишем на компилируемом языке с указателями, ибо машины слабые, что добавляет хардкора.

Выше слоем Юниты — то, что может двигаться по хексам: транспорт, эвакуационные группы, противник — это влияет на Риск. Раненые двигаться обычно не могут, но они сюда тоже относятся. При моделировании раненые обычно ухудшаются и их статус смещается в сторону «нет связи N мин.» У раненых есть Приоритет, который во время планирования компенсирует Риск: к ценному раненому группа эвакуации попрётся даже через зону, где работает миномет противника, если другого пути нет. В зависимости от статуса и пути раненым нужны носилки, транспорт, медикаменты — всё это позволяет направлять к ним только тех эвакуаторов, которые имеют необходимое. Таким образом я подвожу к мысли, что движущиеся юниты имеют при себе Стафф и Транспорт (который могут потерять).

Планирование эвакуации — это построение миров (в смысле Эверетта), где группа эвакуаторов двигается к цели, а потом обратно, и в процессе сталкивается с Наблюдениями:

• непосредственно наблюдаемый огонь;

• расширение известной зоны обстрела;

• перемещение угрозы (вражеских юнитов);

• сообщения о потерях (своих юнитов);

• разрушение запланированных укрытий;

• отказы транспорта.

Каждое наблюдение имеет Влияние, то есть список Воздействий, которые красят хексы в нужный цвет, чтобы дубоголовым командирам при моделировании было понятнее, где они потеряют свои эвакуационные группы.

Старые Наблюдения не исчезают мгновенно, а постепенно теряют уверенность, чтобы отразить что иногда «какая‑то черепашка привирает». Ещё у наблюдений есть источник, а у источника есть доверие, но это уже легаси и вроде не используется, потому что у одного источника не так много наблюдений, чтобы там что‑то вычислять.

В фазе планирования мы стараемся не показывать самые пессимистичные сценарии развития событий, чтобы уравновесить количество потерь эвакуационных групп и количество потерь раненых. Коэффициенты — подбираются на глаз. В фазе исполнения постоянно нет связи, поэтому она, в основном, сравнивается с реальной историей постмортем.

Ладно, вроде с клеточными автоматами понятно, теперь перейдем к конечным автоматам.

Раненые конечные автоматы

Раненый задаётся состоянием: Pj=(lj,sj,dj,wj,rj,cj,fj).

lj последнее известное положение; sj предполагаемая тяжесть; dj функция ухудшения состояния; wj трудоёмкость эвакуации; rj риск непосредственно около пациента; cj уверенность в сведениях; fj время последнего подтверждения.

В планировании используется функция ожидаемой полезности, она применяется к пути туда (и пути обратно — но на пути обратно веса домножаются на коэффициенты). И там пригодился бы модуль обучения, но его хрен напишешь — всё постоянно меняется (или я не знаю ML/RL).

Общий смысл: тяжёлый пациент далеко в опасной зоне может проиграть менее тяжёлому, которого можно быстро эвакуировать.

Интересная докрутка на месте — это штраф за слишком частую смену решений — люди на местах этого не любят.

Распределенная карта убеждений

Ни одна группа не хранит полную карту. У каждой есть только локальная область. Соседние группы обмениваются Убеждениями. Так как связь херовая, сначала передаются наиболее срочные убеждения. После передачи они домножаются на доверие к источнику и «применяются». Уверенность складывается, если наблюдение пришло несколько раз из разных источников. Полную шляпу можно откатить вручную, история поддерживается. По конкретным алгоритмам гуглить «Gossiping in Distributed Systems».

Клетки асинхронно вычисляют локальную оценку стоимости движения к активной цели. Вычисляется несколько маршрутов, эвристически отбрасываются совсем негодные, для каждого из них вычисляется стоимость туда и обратно. Процесс отбраковки продолжается, пока не остается несколько хороших вариантов. Для них моделируются Наблюдения, предпочтение отдаётся таким наблюдениям, которые увеличивают накопленный риск большими скачками — чтобы не замыливать глаз тем, кто планирует, это держит их в тонусе.

При новых наблюдениях пересчитывается только затронутая область. Это близко по идее к инкрементальному поиску D* Lite: предыдущие результаты используются повторно, вместо запуска полного поиска с нуля. Но так как алгоритмам распределенный — Bellman‑обновления выполняются клетками асинхронно и могут временно расходиться из‑за задержек сообщений.

Распределённое назначение групп

Каждая обнаруженная задача распространяется как запись:

• casualty_id

• last_known_position

• estimated_severity

• required_capabilities

• required_team_count

• report_time

• confidence

• task_epoch

Получив задачу, свободная или потенциально переназначаемая группа вычисляет предложение:

• id

• deltaV

• alfaETA

• RouteRisk

• ExtractionCost

• OpportunityCost

OpportunityCost означает ожидаемую потерю от того, что группа не сможет обслуживать другие известные задачи.

Асинхронный аукцион

Не существует единого аукциониста. Предложения и назначения являются реплицированными записями:

Claim:

• task_id

• team_id

• bid

• task_epoch

• commitment_level

• lease_expiration

• message_time

Все узлы применяют одно правило сравнения. Это вариант Contract Net Protocol (см. «The Contract Net Protocol: High‑Level Communication and Control in a Distributed Problem Solver»): задача объявляется, исполнители рассчитывают предложения, после чего выбирается подходящий исполнитель.

Задачи распределяются между автономными узлами через локальные переговоры, напоминающие тендер. Узел с задачей становится менеджером, публикует объявление, узлы‑кандидаты оценивают задачу и подают заявки, после чего узел‑менеджер выбирает исполнителя подрядчика. Роли не закреплены: один узел может одновременно исполнять чужую задачу и раздавать собственные подзадачи. Благодаря этому управление возникает динамически, без постоянного центрального диспетчера.

Из‑за нестабильной связи пара идей была имплементирована из работы «Auctions for Multi‑Robot Task Allocation in Communication Limited Environments». Это свежак (опубликовано в этом десятилетии), там сравниваются несколько разных аукционных протоколов и их деградация при плохой связи. Оттуда стоит взять простую идею добавлять сведения о прежних раундах к последующим. Это уменьшает число потерянных назначений и дублированных задач. Количество отправок почти не увеличивается, хотя сами сообщения становятся больше.

Также очень хорошая идея заключена в методе Repeated G‑Prim: это многораундовый пакетный аукцион для распределения задач. В каждом раунде он старается выдать не одну задачу, а несколько: распределение идёт серией раундов. Каждый узел‑исполнитель выбирает наиболее привлекательные задачи из всего множества ещё не распределённых задач. Ранжирование выбора зависит от оснащенности группы и её местополжения, в вычислении участвует ETA (Estimated Time Arrival) и то насколько раненый тяжёлый.

Из‑за потери связи две группы могут временно направляться к одному пациенту. Полностью запрещать такое поведение нельзя без риска, что задача вообще останется без исполнителя. Это допустимая цена сохранения активности системы. Чтобы это происходило пореже, применяется «Назначение» — это своего рода токен, присваеваемый задаче. Так как система аукциона задач децентрализованная и с плохой связью, не всегда информация о назначении доходит до всех узлов, иногда бывают конфликты назначений.

Поэтому, Назначение действует ограниченное время. Остальные группы сначала считают назначение сомнительным, затем могут создать резервное назначение (если heartbeat от первой группы не поступает слишком долго). После истечения lease задача снова считается свободной и другая группа может взять её.

Каждая группа публикует короткий план‑намерение (полные маршруты публиковать себе дороже):

Intent:

• team_id

• cells[0…K]

• approximate_time_windows

• carrying_patient

• task_priority

• confidence

• expiration

Клетки увеличивают локальную стоимость, если через них одновременно собираются пройти несколько групп. Это сделано, чтобы избегать «натоптанных путей», которые становятся целями для противника. Но иногда этого нельзя избежать.

Инерция обязательства и перепланирование в реальном времени

План никогда не считается окончательным. Группа перепланирует его, если в процессе постоянного моделирования обнаружен сценарий где есть неприемлемый ущерб, появились сведения о приоритетном пациенте, потеряна возможность завершить задачу, появился значительно лучший маршрут.

Но смена плана выполняется только при достаточном выигрыше, порог создаёт инерцию обязательства. Уже находящаяся в пути группа не разворачивается из‑за каждого нового сообщения.

Была идея заставлять сеть устройств прогонять варианты маршрутов заранее спекулятивно и кэшировать маршруты, но это бы жрало батарейки и поэтому так и не было реализовано (а жаль, было бы интересно попробовать)

Такты действия

Вроде пошаговой стратегии, за тем исключением, что и клетки и юниты имеют самосинизирующееся тактирование (не знаю как это правильно).

Асинхронный такт клетки:

• Принять доступные локальные наблюдения.

• Принять сообщения, дошедшие на этом такте.

• Объединить сведения по времени, доверию и источникам.

• Уменьшить уверенность в устаревших данных.

• Пересчитать активные поля стоимости.

• Обновить краткосрочные резервирования маршрута.

• Удалить истёкшие назначения и намерения.

• Передать соседям несколько изменения.

Такт эвакуационной группы:

• Обновить локальную belief map.

• Проверить состояние текущей задачи.

• Оценить известные задачи.

• При необходимости отправить ставку или обновить claim.

• Выбрать краткосрочный маршрут по локальному полю.

• Разрешить ближайшие конфликты с другими группами.

• Выполнить одно действие.

• Передать статус, если возможно.

Известные «боль в моя дырка задница».

Потери происходят по таким основным причинам:

• группа не знает, что дорога перекрыта;

• не знает, что пациента уже забрали;

• считает старую зону огня активной;

• не знает о новом пациенте;

• получает сообщение после того, как приняла решение.

Горизонт планирования

В реальном времени планирование использует отсечения, чтобы «не тормозить»: средний план сейчас — лучше хорошего завтра. Дропаются далёкие пациенты, не рассматриваются длинные маршруты, после принятия задачи её субьективная ценность увеличивается, но не бесконечно: при подтвержденной невозможности продолжать (нет пути, утрата транспорта) или под огнём задача отменяется.

Способ реализации: поиск с возвратами в пространстве состояний. При отладке этой задачи больше всего крови выпило управление памятью, в конце концов для упрощения были сделаны арены. Да, оно местами течёт, но это уже не так критично.

Поведение при потере связи и плохой связи

Связь плохая:

• сообщения передаются только по приоритету

• полные карты заменяются дельтами

• группа увеличивает срок действия текущего решения

• растёт неопределённость

• снижается склонность принимать удалённые задачи

• предпочтение отдаётся задачам, подтверждённым локально.

Сообщения помещаются в очередь с маркерами (и приоритетами, см. ниже). Если изменение ситуации на «сцене» затрагивает маркеры — неотправленные сообщения из очереди отправки корректируются или удаляются.

Приоритеты:

• новая опасность

• запрос помощи

• галя, у нас отмена (в смысле: отмена задачи)

• изменение маршрута

• спасать уже некого

• heartbeat

• обновления клеток и зон

Связь потеряна:

Группа продолжает текущую задачу пока может. Она не должна автоматически останавливаться.

Автономные политики при долгой потери (могут быть заданы директивно заранее):

• продолжать до пациента

• продолжать только до контрольной точки

• вернуться в область связи

• завершить погрузку, выбрать ближайший известный пункт эвакуации

Заключение

Сорян, что сегодня без обучения нейросетей, гайз. Работаем на технологиях проатцов. Но если у кого есть идеи — пишите в комментарии.