В совместной работе исследователей университета им. Иоганна Кеплера в Линце (Австрия), Лондонского университета (Великобритания), высшей технической школы Ингольштадта (Германия) и университета Бахри (Исламабад, Пакистан) рассматривается программная платформа для моделирования городской мобильности на основе агент-ориентированного подхода, геоинформационных и суперкомпьютерных технологий. Разработчики использовали реальную растровую карту небольшого города в Центральной Европе с очень высоким разрешением, преобразованную в мелкозернистую (1.25 м2) двумерную решетку. Соответствующий клеточный автомат связывает перемещающихся агентов с их жизненным пространством. Вместе с тем, учитывая масштаб моделируемого объекта, техническая реализация модели практически невозможна без использования параллельных вычислений.
Параллельная симуляция на основе агент-ориентированного подхода: компоненты платформы
Разработанная программная платформа для агент-ориентированного моделирования включает в себя три основных компонента, показанных на рис. 1 в виде трех блоков: 1) блок для обработки изображений; 2) блок для параллельных симуляций с использованием агент-ориентированного подхода; 3) блок для обработки и визуализации выходных данных.
Рис. 1. Схема программной платформы для параллельных симуляций с использованием агент-ориентированного подхода: основные компоненты
1. Обработка изображений
Подробная карта города, представляющая собой детализированное растровое изображение, передается в модель с обозначением соответствующих областей (рис. 2). Затем отмеченная часть разбивается на сегменты в зависимости от вычислительных ресурсов и затрат на межпроцессорную синхронизацию – в рассматриваемом примере на 200 квадратов равных размеров (т.е. карта представляется в виде матрицы из 20 строк и 10 столбцов (рис. 3)). Каждый сегмент обрабатывается одним процессором. Для моделирования эвакуации в масштабах города, сектора 22, 64, 96, 124 и 196 определяются как выходы (exits), а в процессе симуляции сегмент 22 затопляется. На рис. 4 отображен детализированный сектор 33. Для обработки растрового изображения используется алгоритм низкочастотной фильтрации, а полученные при этом 200 файлов сохраняются в формате ASCII для последующего использования в ГИС.
Рис. 2. Растровая карта города. Разработанная модель относится к выделенной части пространства
Рис. 3. Используемая для симуляций карта города, поделенная на 200 сегментов – квадратов одинакового размера
Рис. 4. Слева – часть обрабатываемого 25 (5 × 5) процессорами пространства с выделенным сектором (33 на рис. 3), составляющим примерно 1/500 часть от всей карты города (рис. 2) и 1/200 от используемого для симуляций пространства. Справа – увеличенный (один из 25) фрагмент карты слева, обрабатываемый одним процессором. Области пространства белого цвета соответствуют улицам и доступны для перемещающихся агентов. Соответственно все остальные области для движения недоступны.
2. Агент-ориентированный параллельный симулятор
Моделируемое пространство разделено между двумя видами памяти: локальной (для каждого процессора) и разделяемой, используемой процессами для обмена информацией посредством общего сегмента памяти.
Настройка работы каждого процесса может осуществляться во время симуляции и с помощью файлов конфигурации модели, в которых определяются различные параметры. Наиболее важными из них являются: значения границ пространства (x и y координаты), количество процессоров и их вертикальное (и горизонтальное) распределение относительно моделируемого ландшафта, параметры синхронизации и время симуляции в рамках итерационного алгоритма. Каждому процессу автоматически присваивается идентификационный номер, значение которого зависит от вертикального (и горизонтального) местоположения процесса в рамках разделенного на сегменты пространства. Нумерация начинается с 0 и заканчивается на N – 1, где N – общее количество сегментов. На рис. 5 видно, что для расчетов используется 200 процессов со значениями идентификаторов от 0 до 199, а каждый отдельный процесс включает в себя три составляющих модуля: 1) настройка; 2) модель; 3) синхронизация.
Рис. 5. Схема работы агент-ориентированного параллельного симулятора
2.1. Настройка
Инициализация модуля предполагает выполнение следующих шагов
- Обновление карты (с первоначальными настройками ячеек) с использованием информации из файлов ASCII.
- Настройка «центров притяжения» (point of attractions) для агентов с использованием информации из файлов конфигурации модели.
- Создание агентов с использованием информации (относительно типов агентов) из файлов конфигурации модели.
- Распределение агентов по пространству с использованием информации (координаты, плотность расселения и др.) из файлов конфигурации модели.
Модуль настройки выполняется только один раз перед началом симуляции.
2.2. Модель
В процессе выполнения модели происходит выполнение следующих процедур:
- Обновление параметров – к примеру, совместно используемых процессами глобальных переменных.
- Обновление пространственных переменных.
- Изменение параметров агентов с учетом изменения пространства и поведения агентов, находящихся в непосредственной близости.
- Изменение поведения агентов, т.е. выполнение запланированных ранее действий.
2.3. Синхронизация
Основной целью этой процедуры является синхронизация буферного и сетевого пространства.
3. Параметры эффективности
Для масштабируемости системы (т.е. эффективного использования дополнительных вычислительных ресурсов для ускорения счета) разработчики определили ряд факторов, в наибольшей степени влияющих на производительность:
- Интенсивность взаимодействия агентов и горизонт их видимости.
- Сложность в поведении агентов. В своем предыдущем исследовании авторы показали, что во многих случаях увеличение сложности агентов и изменение их поведения в целом снижает эффективность распараллеливания соответствующей модели.
- Распределение пространства между процессорами. Здесь имеет значение равномерность распределения агентов по сегментам пространства.
- Алгоритм синхронизации.
4. Модель
4.1. Карта
Изначальная карта (г. Линц, Австрия) представляла собой растровый рисунок размерностью 10 000 × 15 000 ячеек (соответствующих квадратам с размером 1.25 м2). Далее карта была обрезана до центрального района города (рис. 2) размерностью 5 000 × 10 000 ячеек и поделена на 200 сегментов, каждый из которых (с площадью 250 000 ячеек) при распараллеливании обслуживался отдельным процессом pi, где i – его идентификационный номер (от 0 до 199).
Также разработчиками введена пространственная единица – патч (patch). В терминах разработанной платформы патч – это структурная единица с информацией о типе структуры и ее координатами (к примеру, улица, здание, зеленая зона и т.д.). Для упрощения вычислений у пространственной единицы могут быть только два получаемых агентом состояния: (1) доступно для прохода; (0) недоступно для прохода. На рис. 6 показан пример пространства, созданного на основе данных из файла ASCII.
Рис. 6. Пример сетки патчей (справа) созданной на основе данных из файла (слева). Согласно правилам, белые патчи доступны для агентов, а черные – нет.
4.2. Полевая модель (Floor Field model)
В теории клеточных автоматов есть тип моделей, в основе которых лежит использование полей, в которых хранится информация, оказывающая влияние на навигацию агентов. Поля могут быть динамическими и статическими, в зависимости от характера используемой информации. К примеру, динамическое поле, имеющее собственную динамику, может рассеивать и забывать виртуальные следы агентов. В свою очередь статические поля не меняются, и информация о всех недвижимых препятствиях сохраняется. В рамках текущей модели, знания и память агентов также могут влиять на информацию поля, а каждый патч сетки имеет три дополнительные переменные:
- Направление (Direction) из текущего патча до выхода – DOM.
- Расстояние (Distance) от текущего патча до выхода – HOPC.
- Маршрут – ROUTE.
Типовая структура переменных для стандартного патча показана на рис. 7.
Рис. 7. Структура поля стандартного патча: (a) направление d варьируется в определенном диапазоне и рассчитывается как относительный угол между отправляющим и принимающим патчами; (b) расстояние h определяется перемещениями до целевого патча; (c) маршрут представляет собой последовательность передающих информацию процессов
Изначально, этим переменным не присвоено значений и соответствующие патчи являются недоступными для агентов препятствиями (рис. 8(d)).
Рис. 8. Примеры патча-выхода (заштрихованная область) и значений дополнительных переменных
Каждый доступный для перемещения патч p (не являющийся выходом) во время итеративного пересчета обновляет имеющуюся у него информацию (в окрестности Мура) о патчах-выходах. Если соседний с ним патч имеет информацию о новом выходе в своей коллекции DOM или же имеет информацию о расстоянии до него, то он сообщает эти сведения патчу p со ссылкой на источник (рис. 8(а) и рис. 8(c)). Это позволяет вычислить правильное направление и необходимое количество переходов (в используемой нотации они записываются последовательно через символ «.»). Для более частых случаев, когда выход обслуживается другим процессом, маршрут от патча должен содержать примерно следующую информацию {(15, 2.12.13.14.15) (0, 2.1.0)}, где патч относится к процессу 2 и для него есть два возможных выхода на процессах 15 и 0. Пример изменения полей модели показан на рис. 9, а соответствующий псевдокод приведен в листинге 1.
1 if patch p structure_Type == “walkable” and is not a “exit”
2 for each neighboring patch n
3 // рассматриваются патчи в окрестности Мура
4 for each pair p <key, value> of DOMn
5 // сравниваются пары key и value среди доступных выходов в DOMp
6 if key does not exists in DOMp
7 // если подходящих нет, то происходит обновление
8 DOMp [key] = relative-angle to n
9 HOPCp [key] = value (HOPCn [key]) + 1
10 ROUTEp [key] = value (ROUTEn [key]).ProcessID
Листинг 1. Псевдокод, генерирующий поля для патчей
Рис. 9. Распространение информации о патче-выходе, находящемся внутри помеченной области (a); через 1 итерацию (b); 3 (c); 6 (d) и 10 (e).
4.3. Механизмы взаимодействий и синхронизация
Разработанная платформа поддерживает два режима синхронизации – (1) синхронизация буфера и (2) сетевая синхронизация. Оба режима позволяют работать как с патчами, так и с мобильными агентами.
Синхронизация буфера (Buffer synchronization). В моделируемом пространстве используемая процессами информация может быть синхронизирована с использованием буферов обмена. На рис. 10 (a) показана синхронизация данных между процессом 64 и процессами 54, 63, 74 и 65 с использованием буферов с 1 размером. Диагональные процессы также синхронизируются, но на схеме это не показано.
Сетевая синхронизация (Network synchronization). В этом случае информация синхронизируется между связанными патчами (или агентами) из соседних процессов. Пример синхронизации двух связанных патчей, находящихся в процессах 64 и 74, показан на рис. 10 (a).
Патчи и мобильные агенты используют три переменные (“agent_id”, “process_id”, “agent_type”), идентифицирующие их в процессе синхронизации, а другие переменные необходимы для спецификации некоторых функций. Часть из них приведена в табл. 1.
Таблица 1. Переменные, используемые при синхронизации и спецификации
Переменная |
Тип агента |
Краткое описание |
agent_id |
любой |
уникальный идентификатор агента |
process_id |
любой |
идентификатор процесса, который в настоящий момент обслуживает агента |
agent_type |
любой |
тип агента |
structure_type |
патч |
тип участка ГИС пространства |
DOM |
патч |
переменная поля |
HOPC |
патч |
переменная поля |
ROUTE |
патч |
переменная поля |
orientation |
мобильный |
относительный угол направляющей между текущим патчем и патчем-выходом |
curr_exit |
мобильный |
текущий патч-выход (пункт назначения) для агента |
wait |
мобильный |
длительность ожидания перехода с позиции агента (в терминах итерационного пересчета) |
speed |
мобильный |
скорость агента при выполнении текущего перехода |
following? |
мобильный |
проверка – является ли агент ведомым по отношению к агенту, обладающему большей информацией, чем он сам? |
Рис. 10. Обмен данных между процессами: (a) синхронизация буфера и сетевая синхронизация; (b) параметры процесса; (c) совместное использование параметров процесса.
Параметры процесса
Во время симуляций возможны ситуации, при которых информация на уровне процессов должна быть разделена. Например, «процессная единица плотности»:
Процессная единица плотности = pop / wal, (1)
где pop – количество перемещающихся агентов, обслуживаемых текущим процессом и wal – количество доступных для перемещения патчей, также обслуживаемых текущим процессом. Этот параметр рассчитывается и хранится на уровне одного процесса, но при этом доступен всем агентам для расчета скорости передвижения (рис. 10 (b)).
Глобальные параметры
Значения упомянутого ранее параметра крайне важны для планирования маршрутов, но в силу больших вычислительных затрат на каждой итерации они не рассчитываются. В этой связи, в разработанной платформе используются глобальные параметры, используемые несколькими процессами (рис. 10 (c)), сохраняющие необходимые данные.
4.4. Поведение и адаптация агентов
Все агенты в модели являются пешеходами двух типов:
- интеллектуальные агенты, имеющие доступ ко всей информации в рамках симуляции;
- неинтеллектуальные агенты, имеющие доступ только к локальной информации (на уровне обслуживающего их процесса).
Создание агентов и их случайное размещение
Количество создаваемых агентов рассчитывается по приведенной ниже формуле:
countType = (PercType / 100) × ((ProccessW / TotalW) × TotalP), (2)
где PercType – доля агентов определенного типа, ProccessW – количество доступных для перемещения патчей в рамках текущего процесса, TotalW – количество всех доступных патчей в моделируемом пространстве, TotalP – общее количество мобильных агентов.
При инициализации, каждому агенту присваиваются следующие значения основных переменных (независимо от типа агента): orientation (– 999), curr_exit (– 1), speed(0), wait(– 1), confidence(– 1) и following(false). Агент генерируется на еще незанятом патче и ему присваивается тип “walkable”.
Скорость агентов
Скорость конкретного агента зависит от количества агентов в локальном пространстве и рассчитывается следующим образом:
speed_on_density = v0 × (1 – count (agents) / count (walkables) / max_density_per_patch) (3)
speed = max {vmin, speed_on_density} (4)
Процедура принятия решения агентом по перемещению приведена в листинге 2. Она выполняется для каждого агента в соответствии с правилами, показанными на рис. 11, в результате применения которых обновляются переменные агента.
1 heading (orientation)
2 p = patchAtHeadingAndDistance (heading, speed)
3 if (p → turtlesHere.size > 0 || p → turtlesHere.size > 0
4 if (scanNeighborinOrderRight (angle))
5 heading (angle)
6 move (speed)
7 reset_wait ()
8 confidence (x)
9 else
10 inc_wait ()
11 else
12 move (speed)
13 reset_wait ()
14 confidence (100)
Листинг 2. Псевдокод, описывающий процедуру принятия решения агентом по перемещению
Рис. 11. Возможные предпочтения объекта, движущегося под углом 45°. Черные кружки обозначают занятые объектом ячейки, а заштрихованные – целевые.
4.5. Моделирование передвижения агентов
При моделировании передвижения учитывается множество факторов, среди которых важнейшими являются следующие:
(1) Тип агентов. Для проведения экспериментов разработчики предусмотрели три вариации:
- все агенты являются неинтеллектуальными: стратегия 1 и стратегия 4 (см. ниже).
- все агенты являются интеллектуальными: стратегия 2.
- часть агентов является интеллектуальными, а часть – нет: стратегия 3 и стратегия 5.
(2) Уровень информационной осведомленности, влияющий на поиск оптимального для агентов патча-выхода.
(3) Аппроксимация результатов. Метод, позволяющий сократить время расчетов, если не так важна точность полученных значений (реализуется путем использования стратегии 4 вместо стратегии 1 и стратегии 5 вместо стратегии 3).
Далее переходим к рассмотрению различных стратегий передвижения, реализованных в рамках экспериментальных расчетов.
Стратегия 1
Все агенты модели являются неинтеллектуальными и каждый из них использует только стратегию с локальными маршрутами к ближайшему патчу-выходу. Пример реализации стратегии 1 приведен в листинге 3.
1 p = patchHere
2 selected_exit = min {key (HOPCp)}
3 if (selected_exit == null)
4 inc_wait()
5 else
6 find pair <key, value> in DOMp
7 orientation (value (DOMp [key]))
8 current_exit (selected exit)
9 Proceed_to_Next_Cell()
Листинг 3. Псевдокод, реализующий стратегию 1
Стратегия 2
Все агенты модели являются интеллектуальными, и все они реализуют стратегию с учетом всех возможных вариантов (листинг 4).
1 if there exits an intelligent agent a in interation_range
3 if (a ® current_exit != -1)
4 following (true)
5 current_exit (a → current_exit)
6 if (following())
7 p = patchHere
8 find pair <key, value> in DOMp where key = current_exit
9 orientation (value (DOMp [key]))
10 Proceed_to_Next_Cell()
11 else
12 Move_to_Nearest()
Листинг 4. Псевдокод, реализующий стратегию 2
Стратегия 3
В случае гибридной популяции, неинтеллектуальные агенты (95% от общего числа) ищут в доступной окрестности интеллектуальных (5%) и следуют за ними. В листинге 5 приведен псевдокод, реализующий стратегию неинтеллектуальных агентов, а агенты другого типа, в свою очередь, реализуют стратегию 2.
1 if (current_exit != -1)
2 p = patchHere
3 if (size (p → DOMp) >= 2)
4 set_OptimalExit()
5 find pair <key, value> in DOMp where key = current_exit
6 orientation (value (DOMp [key]))
7 Proceed_to_Next_Cell()
8 else
9 if (size (p → DOMp) >= 2)
10 set_OptimalExit()
11 inc_wait()
12 else
13 if (size (p → DOMp) == 1)
14 set_AvailableExit()
15 inc_wait()
16 else
17 inc_wait()
18 set_OptimalExit()
19 current_weight = 999999;
20 aggregate_route_density = 0;
21 selectedExit = -1;
22 for each pair <key, value> in ROUTEp
23 current_process = key
24 current_route_sequence = value
25 for each element e in current_route_sequence
26 find pair <key, value> in DENSITIESprocess where key = e
27 current_density = value (DENSITIESprocess [key])
28 aggregate_route_density = aggregate_route_density + current_density
29 aggregate_route_density – aggregate_route_density / size (current_route_sequence)
30 find pair <key, value> in DOMp where key = current_process
31 temp_value = aggregate_route_density × value (DOMp [key])
32 if (temp_value <= current_weight)
33 current_weight = temp_value
34 selectedExit = current_process
35 current_exit (selectedExit)
36 set_AvailableExit()
37 current_exit (p → DOMp .first[key])
Листинг 5. Псевдокод, реализующий стратегию 3
Стратегия 4
Данная стратегия аналогична первой, но с целью сокращения времени расчетов, первый же найденный патч-выход считается оптимальным.
Стратегия 5
Стратегия аналогична третьей, но в реализующем ее коде первая строка выполняется не каждый раз, а только в случае потери маршрута.
Для соответствия базовым принципам агентного подхода, разработанная платформа должна обладать функциональностью, позволяющей агентам реагировать на изменение окружающей среды, к примеру, на изменения состояний патчей-выходов:
Сценарий 1. Один из выходов x становится недоступным, но с течением времени может снова стать доступным. При этом информация о недоступности выхода распространяется мгновенно, а о повторной доступности появляется постепенно (как в листинге 1).
Сценарий 2. Один из выходов x становится недоступным и остается таким на протяжении всей симуляции, а информация о его недоступности также как в сценарии 1 распространяется мгновенно.
Сценарий 3. Один из выходов x становится недоступным и остается таким на протяжении всей симуляции, но информация о его недоступности распространяется постепенно.
Описанные сценарии реализованы в следующих стратегиях, основанных на базе стратегии 5.
Стратегия 6
Во время выполнения i-ой итерации информация о выходе x стирается из коллекций DOM, HOPC и ROUTE для всех патчей. На итерации i + 1 запускается алгоритм, генерирующий поля для патчей (листинг 1).
Стратегия 7
Во время выполнения i-ой итерации информация о выходе x стирается из коллекций DOM, HOPC и ROUTE для всех патчей.
Стратегия 8
Во время выполнения i + 1 итерации запускается измененный алгоритм из листинга 1. Модификация касается распространения информации о недоступности выхода – теперь она распространяется постепенно и пока патчи ее не получат, они будут дезинформированы и считать выход валидным.
5. Симуляция процесса эвакуации и некоторые результаты
Для тестового запуска пространство было ограничено размерностью 500´500, что составляет примерно 1/500 часть от всей карты города (рис. 2) и обрабатывается 25 (5 × 5) процессами, на каждый из которых приходится сегмент размерностью 100´100 (рис. 12). В процессе симуляции патч-выход 12 через определенное время (на 150-ой итерации) меняет свое состояние от «доступного» на «недоступный». Всего в тестовом режиме было задействовано 12 500 агентов, отработано все 8 стратегий, а общее количество итераций – 500.
Рис.12. Пространство для тестового запуска. Сектора 0, 4, 12, 21 и 23 являются патчами-выходами, причем выход 12 в процессе симуляции затапливается
Поскольку цель разработки модели – оценка эффективности той или иной стратегии эвакуации, то особое внимание в результатах уделяется затраченному времени. В табл. 2 приведены соответствующие оценки и, как видно, разница во времени между 1 и 4 стратегиями весьма существенна, в то время как между 2 и 5 незначительна.
Таблица 2. Сравнительная оценка производительности параллельной версии симулятора для различных стратегий передвижений в рамках тестового пространства
Стратегии передвижений |
Процессорное время чч:мм:сс |
Память Кб |
Виртуальная память Кб |
Затраченное время чч:мм:сс |
Стратегия 1 (100 % неинтеллектуальных агентов) |
11:32:22 |
1068744 |
20562304660 |
00:27:58 |
Стратегия 2 (100 % интеллектуальных агентов) |
01:56:21 |
1067968 |
20562303596 |
00:04:53 |
Стратегия 3 (5 % интеллектуальных и 95 % неинтеллектуальных агентов) |
06:56:40 |
1067512 |
20562302904 |
00:16:57 |
Стратегия 4 (100 % неинтеллектуальных агентов) |
01:57:28 |
1065856 |
20562301428 |
00:04:54 |
Стратегия 5 (5 % интеллектуальных и 95 % неинтеллектуальных агентов) |
02:24:3 |
1068116 |
20562303472 |
00:06:02 |
Стратегия 6 (5 % интеллектуальных и 95 % неинтеллектуальных агентов) |
02:27:33 |
1067432 |
20562302588 |
00:06:37 |
Стратегия 7 (5 % интеллектуальных и 95 % неинтеллектуальных агентов) |
01:52:50 |
1052036 |
20562287592 |
00:04:42 |
Стратегия 8 (5 % интеллектуальных и 95 % неинтеллектуальных агентов) |
02:13:37 |
1061136 |
20562296924 |
00:05:33 |
Если сравнивать стратегии 1 и 4 на основе рис. 13 и табл. 3, то видно, что процент агентов, эвакуировавшихся через выходы 0 и 21 в случае применения стратегии 4 снизился, в силу того, что эти выходы имеют меньшую пропускную способность (по сравнению с 4 и 23), а агенты в модели не тратят времени на поиск другого, возможно более оптимального выхода. На рис. 14 видно, что общее число эвакуированных агентов в случае применения стратегий 1 и 4 практически не отличается, но судя по данным из табл. 2, время реализации стратегии 1 почти в семь раз превышает время реализации стратегии 4. В этой связи, для симуляции всего пространства была выбрана стратегия 4.
Рис. 13. Результаты применения восьми стратегий передвижений для параллельной версии симулятора в рамках тестового пространства: количество эвакуированных агентов через разные патчи-выходы (0, 4, 12, 21 и 23) в течение 500 итераций
Таблица 3. Результаты применения восьми стратегий передвижений для параллельной версии симулятора в рамках тестового пространства: количество эвакуированных агентов через разные патчи-выходы (0, 4, 12, 21 и 23), в процентах
Стратегии |
Выход 0 |
Выход 4 |
Выход 12 |
Выход 21 |
Выход 23 |
1 |
8% |
26% |
32% |
14% |
20% |
4 |
4% |
33% |
27% |
12% |
22% |
3 |
10% |
27% |
26% |
14% |
23% |
5 |
9% |
27% |
25% |
14% |
24% |
7 |
9% |
33% |
10% |
19% |
31% |
8 |
8% |
35% |
8% |
16% |
33% |
При реализации стратегий 3 и 5 эвакуация агентов через выходы происходит более равномерно, т.е. даже небольшой процент интеллектуальных агентов может оказать влияние на весь процесс. Сравнивая результативность обеих стратегий (рис. 13 и табл. 3) можно отметить, что большой разницы в скорости эвакуации и использовании выходов нет. Однако время реализации стратегии 3 почти в три раза превышает время реализации стратегии 5 (табл. 2), поэтому для симуляции всего пространства была выбрана последняя.
Предпосылки стратегий 2 и 6 не являются реалистичными, поэтому они были обсчитаны только для теоретического сравнения и для симуляции всего пространства использованы не будут.
Стратегии 7 и 8 позволяют перенаправить агентов к новому выходу, если в процессе симуляции выход 12 станет недоступным. По данным рис. 13 и табл. 3 видно, что агенты, изначально направляющиеся к выходу 12, далее были перенаправлены к выходам 4, 21 и 23. Стратегия 7 производительнее, чем стратегия 8 (табл. 2), в связи с чем, она и была выбрана для симуляции всего пространства.
Рис. 14. Результаты применения восьми стратегий передвижений для параллельной версии симулятора в рамках тестового пространства: количество эвакуированных агентов безотносительно выходов (Sn – стратегии, n – номер конкретной стратегии)
Моделирование эвакуации в городском масштабе
Для симуляций в масштабах города карта была поделена на 200 сегментов – квадратов одинакового размера (рис. 3), распределенных по прямоугольнику размерностью 10 × 20. Каждый из сегментов, обслуживаемый отдельный процессором, содержит подпространство размерностью 500 × 500. Количество агентов, соответствующее населению города, составляет 200 000. Патчи-выходы представляют собой городские достопримечательности: центр города – 64 патч, промышленная зона – 96, стадион – 124, пригородный центр – 22, выезд на автомагистраль – 196. В рамках одной симуляции осуществлялось 5 000 итераций, а выход – 22 меняет свое состояние с «доступного» на «недоступный» на 1 000 итерации.
Результаты
В ходе экспериментов, предусматривающих применение 4, 5 и 7 стратегий, вычислялось общее количество эвакуировавшихся в процессе симуляции агентов. На рис. 15 приведены соответствующие результаты, показывающие эффективность стратегии 5. Так, при ее применении 80% агентов эвакуировались на итерации 3 690, а при реализации стратегии 4 тоже количество агентов эвакуируется только на 4 540 итерации. Также очевидно, что седьмая стратегия по сравнению с пятой является проигрышной, поскольку переориентация агентов с 22 патча на другие выходы потребовала дополнительного времени, и за 5000 итераций удалось эвакуировать только 60% агентов.
Рис. 15. Результаты применения отобранных стратегий (4, 5 и 7) передвижений для параллельной версии симулятора в рамках масштаба всего города: количество эвакуированных агентов безотносительно выходов (Sn – стратегии, n – номер конкретной стратегии)
Если более подробно рассмотреть результаты по патчем-выходам (рис. 16 и табл. 4), то мы увидим, что при реализации стратегии 5, выходы используются более равномерно. Кроме того, в случае стратегии 4 в определенный момент времени только 2 из 5 выходов остаются активными.
Рис. 16. Результаты применения отобранных стратегий (4, 5 и 7) передвижений для параллельной версии симулятора в рамках масштаба всего города: количество эвакуированных через выходы 22, 64, 96, 124 и 196 агентов
Таблица 4. Результаты применения восьми стратегий передвижений для параллельной версии симулятора в рамках масштаба всего города: количество эвакуированных агентов через разные патчи-выходы (22, 64, 96, 124 и 196), в процентах
|
Выход 22 |
Выход 64 |
Выход 96 |
Выход 124 |
Выход 196 |
Стратегия 4 |
43% |
12% |
3% |
40% |
18% |
Стратегия 5 |
27% |
26% |
10% |
33% |
4% |
Стратегия 7 |
8% |
29% |
11% |
47% |
5% |
Распределение агентов в рамках пяти процессов, содержащих патчи-выходы, показано на рис. 17. Агенты на схемах представлены в виде крошечных точек, а более крупные точки – патчи-выходы. Как видно, при реализации стратегии 5 агенты лучшим образом распределяются по улицам (к примеру, если сравнить (b) и (g)). Кроме того, (h) еще используется при реализации стратегии 5, а в стратегии 4 уже нет.
Рис. 17. Визуализация пяти патчей-выходов на середине симуляции (2 500 итерация) для стратегии 4 (a-e) и стратегии 5 (f-j)
Визуальное сравнение стратегий 4, 5 и 7 приведено на рис. 18. К примеру, видно, что когда патч-выход 22 становится недоступным (на итерации 1100), то агенты перемещаются в сторону других выходов.
Общий же вывод по использованным стратегиям следующий. При моделировании систем с большим количеством агентов, несмотря на применение суперкомпьютерных технологий, принципиальное значение имеет детализация модели и степень коммуникации агентов, влияющая на частоту межпроцессорного взаимодействия. Так, упрощение в действиях агентов при применении стратегии 4 (по сравнению со стратегией 1) позволило уменьшить время расчета 5 000 итераций симуляции в рамках масштаба всего города до 12 часов (в то время как за 278 часов удалось просчитать только 4% от общего объема вычислений, необходимых для реализации стратегии 1).
Рис. 18. Визуализация агентов вокруг патча-выхода 22 при реализации стратегии 4 (верхний ряд), стратегии 5 (средний ряд) и стратегии 7 (нижний ряд)
Более подробно про результаты проведенного исследования можно прочитать, к примеру, здесь: [Zia, Kashif & Riener, Andreas & Farrahi, Katayoun & Ferscha, Alois. (2013). An Agent-Based Parallel Geo-Simulation of Urban Mobility during City-scale Evacuation. Simulation. DOI: 10.1177/0037549713485468].