В работе ученых научно-технического университета г. Краков (AGH University of Science and Technology) рассматривается симулятор, построенный на базе агентного подхода, позволяющий имитировать поведение толпы на различных объектах – от небольших помещений до крупных центров притяжения большого количества людей (стадионов, высотных зданий и т.д.). Использование клеточных автоматов в качестве основы для пространственного распределения агентов позволяет эффективно распараллеливать программный код.

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

Рис. 1. Физическое представление агентов в классической модели клеточного автомата (слева) и в модели социальных сил (справа)

В предлагаемой модели, рассматривающей процесс эвакуации, клеточный автомат определяется как кортеж вида CA = (L, S, N, f), где L – это квадратная решетка, содержащая различные типы пространств, определяющих возможности перемещения агентов (лестницы, эскалаторы, препятствия и т.д.); S – набор состояний агента, включая его тип и физическое расположение; N – окрестность Мура; f – функция перехода, зависящая от свойств агента и типа занятой ячейки.

Агент в модели определяется следующим набором A_j = (τ_j, (x_j, y_j), R_j), где τ_j – тип агента j; x_j, y_j – его координаты, а R_j – стратегическая, тактическая и оперативная способности агента.

Большинство моделей, рассматривающих движение агентов, оперируют достаточно простыми правилами их поведения (оперативного и изредка тактического уровня). В предлагаемой авторами модели используются множество дополнительных факторов, влияющих на процесс принятия решений – распространение информации через систему вещания, инструкции для персонала и др. В зависимости от расположения громкоговорителей, ячейки различаются по степени восприятия силы звука, а звуковые поля (sound fields, SF) могут быть определены по следующей упрощенной формуле (1):

SF_x,y = {(xʹ, yʹ): (xʹ – x)² + (yʹ – y)² ≤ r²}, (1)

где x, y – координаты источника звука, а r – всенаправленный радиус сферической волны.

Когда агент попадает в зону звуковых полей, он может услышать сообщение с вероятностью P_SF и изменить свое поведение (пойти к другому аварийному выходу, увеличить/уменьшить скорость и т.д.). Другая важная возможность для корректировки принятия решений на стратегическом уровне – общение внутри группы агентов (в непосредственной близости или с использованием мобильных устройств связи), определяемой набором (L_i, R_i, S_i), где L_i = (x_i, y_i) – лидер группы i, а x, y – его координаты; R_i = (r₁, r₂, …, r_n)_i – правило группы i; S_i ∈ {2, 3, 4, …,} – размер группы i; r – отдельное правило из числа возможных n; i ∈ {1, 2, 3, …, m} – индекс группы.

В начале симуляции агент может быть отнесен к определенной группе с вероятностью P_GB, если расстояние между ним и лидером группы, определяемое следующим образом: D = f(ρ) = Dens_max / ρ, где ρ - плотность агентов на квадратный метр вокруг лидера группы, меньше некоторого задаваемого значения.

В процессе симуляции агенты группы придерживаются определенному набору правил, к примеру: (1) правило r₁ – «следуй за лидером», предписывающее агенту пытаться перемещаться к ячейке где находится лидер, или, в крайнем случае, в окрестность Мура порядка 2; (2) правило r₂ – «не обгоняй», предписывающее сохранять скорость не превышающую скорость лидера группы и др.

Пример принятия агентами решений на стратегическом уровне приведен на рис. 2, где отображен процесс эвакуации с футбольного стадиона на севере Мюнхена – Альянц Арена (Allianz Arena). Во время соответствующей симуляции агентам сообщили о том, что ближайший выход заблокирован и до поступления новой информации им нужно оставаться на текущих позициях, в результате чего средняя скорость агентов снизилась со значения 1.34 до 0.5 м/c.

Рис. 2. Пример эвакуационного участка, расположенного на нижнем уровне стадиона. После получения сообщений о проблемах на выходе, агенты снизили скорость перемещения: на рис. (a) темные цвета означают более высокие скорости, а на рис. (b) светлым цветам соответствуют низкие скорости

Тактический и оперативный уровень

Используемый на этом уровне алгоритм состоит из двух основных этапов: принятие решения и разрешение конфликтов. На первом этапе агент выбирает следующую для перемещения ячейку c_i,j, учитывая конфигурацию окружающего пространства, наличия рядом стен и других препятствий в рамах окрестности Мура порядка 1. Горизонт его видимости, визуализированный на рис. 3, вычисляется по следующей формуле:

, (2)

где x, y – координаты центральный ячейки, r – радиус окрестности Мура, dx и dy – координаты ячейки c минимальными значениями; а – вектор (xʹyʹ), b – вектор (dx, dy).

Рис. 3. Агент занимает центральную ячейку с координатами (0, 0), черная ячейка – локальный минимум со значением (dx, dy) = (0, 1), светлые и темно-серые ячейки – поля видимости, вычисленные по формуле (2).

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

Градиент окружающего пространства указывает выбранный агентом объект (point of interest (POI)) для перемещения, к примеру эвакуационный выход. Таким образом, агент получает информацию о примерном направлении движения, а также об агентах, проделавших этот путь ранее.

Процесс принятия решений агентом, в том числе, включает в себя выбор ячейки для последующего перемещения. С использованием формулы (3) рассчитывается конкретная ячейка из набора доступных ячеек в рамках горизонта видимости VF, а за счет варьирования весовых параметров отдельных агентов, траектории их движения незначительно различаются.

, (3)

где S^a_ij – значение в возможном для перемещения статическом поле, a – индекс возможного поля, ведущего к POI; α Î [0, ∞) – весовой параметр; dens (c_ij) – плотность в окрестности ячейки c_ij; D_ij – значение динамического поля; δ ∈ [0, ∞) – весовой параметр; dist (c_ij, POI) – расстояние между ячейкой с координатами i, j и ближайшим POI; W – параметр, определяющий возможность уклонения от стен и учитывающий расстояние от них; I – параметр инерции, определяющий возможность сохранения направления движения.

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

Рис. 4. Возможные сценарии разрешения конфликта. Слева – начальная фаза конфликтной ситуации, справа – возможные варианты разрешения конфликта, подразумевающие изменения положения тела агента

В процессе перемещения агент проверяет возможность занятия выбранной ячейки, и если коэффициент ε не позволяет сделать это непосредственно, а также повернувшись на 45°, то агент остается на месте, но при этом алгоритм разрешения конфликта сразу же запускается вновь относительно других, следующих по значимости для агента ячеек. Визуализация результатов симуляции с учетом этого дополнительного шага, повышающего реалистичность модели, приведены на рис. 5.

Рис. 5. Пример моделирования одного сектора стадиона «Висла» (г. Краков): без использования дополнительного шага (слева) и с его применением (справа)

Симулятор

Построенный симулятор, одновременно являющийся и фреймворком для разработки аналогичных моделей, реализован с использованием многоуровневой архитектуры, слои которой перечислены ниже:

1. Данные и логика работы симулятора (пакет core).
2. Слой обработки пользовательских запросов и также содержащий служебные утилиты (пакеты engine и tools).
3. Слой, содержащий графический интерфейс пользователя (пакет gui).

На рис. 6 приведена схема взаимодействия между слоями и компонентами программных пакетов.

Рис. 6. Архитектура симулятора

На логическом слое симулятора разработчики могут оперировать глобальным объектом (Global Object) и уровнями (Levels; к примеру, стадионом, отдельными трибунами, секциями и т.п.). В такой нотации стадион «Висла» является глобальным объектом, его четыре трибуны (восток, запад, север и юг), соответствуют объектам, а секции трибун являются уровнями (рис. 7).

Структура симулятора хорошо масштабируема для разных объектов (стадионы, высотные здания и т.д.). Среди важных компонентов, учитываемых в уровнях можно выделить статические и динамические поля, геометрию помещений и настройку симуляций.

Статическое поле определяется трехмерным массивом S[x][y][POIs], позволяющим агентам модели двигаться к POI (например, к аварийному выходу). В свою очередь динамическое поле определяется двумерным массивом D[x][y], меняющимся на каждом шаге моделирования.

Рис. 7. Иерархия объектов на слое логики и данных (а); разделение стадиона на секции, связанные с логическим слоем (b)

Слой, содержащий служебные утилиты, включает в себя директивы для распараллеливания программного кода, а при синхронизации используется авторская методика с применением барьеров памяти для компонентов трех уровней (глобального объекта и объектов двумя уровнями ниже). Обработка событий, связанных с переходом агента на другой уровень (секцию или к POI), т.е. обращение к памяти после барьера, будет возможна только после выполнения всех инструкций в рамках текущего уровня (рис. 8).

Рис. 8. Синхронизация потоков с использованием барьеров памяти

Слой, содержащий графический интерфейс пользователя, включает в себя диалоговые окна, кнопки, виджеты и др., а результаты симуляции обновляются в соответствующем окне с периодом 1/8 секунды. Для отображения агентов предусмотрено четыре уровня детализации (рис. 9, левая часть), а для отслеживания траекторий их движения и сбора статистики реализован специальный функционал (рис. 9, правая часть).

Рис. 9. Отображение агентов с различной степенью детализации (слева) и траектория их движения (справа)

Результаты симуляций

Для тестирования адекватности симулятора сначала были проведены эксперименты по оценке времени эвакуации из лекционной аудитории. Усредненные результаты 50 прогонов показали время эвакуации всего класса за 6.6 сек., а эмпирические данные 6.24 сек. На рис. 10 приведены полученные значения для 31 участника экспериментов.

Рис. 10. Первоначальное размещение агентов в аудитории. В верхней части каждой ячейки приведен персональный номер участника, а в нижней – время, затраченное на эвакуацию. В левой части (a) рисунка – результаты моделирования, в правой части (b) – эмпирические данные.

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

Далее были проведены симуляции для восточной трибуны стадиона «Висла». Общее количество агентов в симуляции – 11 808, время эвакуации для 95% агентов – 653 сек., самая быстрая эвакуация – 3 сек., самая медленная – 653 сек., средняя скорость перемещения агентов – 0.316 м/сек. На рис. 11 приведены дополнительные результаты. Отметим то, что с течением времени средняя скорость снижалась, что связано с заполнением ближайших выходов (рис. 11b). По мнению разработчиков симулятора, такой результат указывает на ошибки в проектировании стадиона.

Рис. 11. Результаты эвакуации восточной трибуны стадиона «Висла»: (a) пройденное расстояние и время эвакуации для каждого агента; (b) количество эвакуированных агентов в различные промежутки времени и средняя скорость перемещения.

Наблюдение за выходом болельщиков восточной трибуны стадиона «Висла» показало, что результаты моделирования (рис. 5 справа) повторяют реальный процесс (рис. 12).

Рис. 12. Болельщики покидают восточную трибуну стадиона «Висла»

Для более крупного стадиона – Альянц Арена, вмещающего 70 000 зрителей, были проведены симуляции для 58 000 агентов. Усредненное время эвакуации после множества прогонов составило 1117 сек., средняя скорость перемещения агентов – 0.726 м/сек., самая быстрая эвакуация – 2 сек., самая медленная – 1117 сек.

На рис. 13 видно, что после первых 300 сек. от момента начала симуляций, средняя скорость агентов стабилизируется на уровне 0.7 м/сек. и в течение 70% времени процесс эвакуации осуществляется в стабильном режиме и с довольно высокой скоростью.

Рис. 13. Количество эвакуированных с течением времени агентов и средняя скорости их перемещения на стадионе Альянц Арена

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

Рис. 14. Визуализация статистики эвакуации агентов нижней части стадиона Альянц Арена: частотная матрица (справа), тепловое отображение времени эвакуации (слева)

По мнению разработчиков, построенный симулятор может быть использован как для выявления узких мест в оцениваемых объектах (стадионах, зданиях и т.д.), так и для интегрирования в системы онлайн-мониторинга территорий массового скопления людей, использующих камеры видеонаблюдения с функцией распознавания лиц, датчики глубины, GPS-трекеры и др. Совместное использование таких систем и описываемых моделей позволит прогнозировать поведение толпы в режиме реального времени и может быть дополнительным аналитическим инструментом поддержки принятий решений для органов, обеспечивающих безопасность во время проведения массовых мероприятий.

Более подробно: Lubaś, R., Wąs, J. & Porzycki, J. (2016): Cellular Automata as the basis of effective and realistic agent-based models of crowd behavior // The Journal of Supercomputing, Volume 72, Issue 6, pp 2170-2196. https://doi.org/10.1007/s11227-016-1718-7.