25.07.2017

В совместной работе исследователей университета им. Иоганна Кеплера в Линце (Австрия), Лондонского университета (Великобритания), высшей технической школы Ингольштадта (Германия) и университета Бахри (Исламабад, Пакистан) рассматривается программная платформа для моделирования городской мобильности на основе агент-ориентированного подхода, геоинформационных и суперкомпьютерных технологий. Разработчики использовали реальную растровую карту небольшого города в Центральной Европе с очень высоким разрешением, преобразованную в мелкозернистую (1.25 м2) двумерную решетку. Соответствующий клеточный автомат связывает перемещающихся агентов с их жизненным пространством. Вместе с тем, учитывая масштаб моделируемого объекта, техническая реализация модели практически невозможна без использования параллельных вычислений.

Параллельная симуляция на основе агент-ориентированного подхода: компоненты платформы

Разработанная программная платформа для агент-ориентированного моделирования включает в себя три основных компонента, показанных на рис. 1 в виде трех блоков: 1) блок для обработки изображений; 2) блок для параллельных симуляций с использованием агент-ориентированного подхода; 3) блок для обработки и визуализации выходных данных.

Evacuation1.JPG 

Рис. 1. Схема программной платформы для параллельных симуляций с использованием агент-ориентированного подхода: основные компоненты

1. Обработка изображений

Подробная карта города, представляющая собой детализированное растровое изображение, передается в модель с обозначением соответствующих областей (рис. 2). Затем отмеченная часть разбивается на сегменты в зависимости от вычислительных ресурсов и затрат на межпроцессорную синхронизацию – в рассматриваемом примере на 200 квадратов равных размеров (т.е. карта представляется в виде матрицы из 20 строк и 10 столбцов (рис. 3)). Каждый сегмент обрабатывается одним процессором. Для моделирования эвакуации в масштабах города, сектора 22, 64, 96, 124 и 196 определяются как выходы (exits), а в процессе симуляции сегмент 22 затопляется. На рис. 4 отображен детализированный сектор 33. Для обработки растрового изображения используется алгоритм низкочастотной фильтрации, а полученные при этом 200 файлов сохраняются в формате ASCII для последующего использования в ГИС.

 Evacuation2.JPG

Рис. 2. Растровая карта города. Разработанная модель относится к выделенной части пространства

 Evacuation3.JPG

Рис. 3. Используемая для симуляций карта города, поделенная на 200 сегментов – квадратов одинакового размера

 Evacuation4.JPG

Рис. 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) синхронизация.

 Evacuation5.JPG

Рис. 5. Схема работы агент-ориентированного параллельного симулятора

2.1. Настройка

Инициализация модуля предполагает выполнение следующих шагов

  • Обновление карты (с первоначальными настройками ячеек) с использованием информации из файлов ASCII.
  • Настройка «центров притяжения» (point of attractions) для агентов с использованием информации из файлов конфигурации модели.
  • Создание агентов с использованием информации (относительно типов агентов) из файлов конфигурации модели.
  • Распределение агентов по пространству с использованием информации (координаты, плотность расселения и др.) из файлов конфигурации модели.

Модуль настройки выполняется только один раз перед началом симуляции.

2.2. Модель

В процессе выполнения модели происходит выполнение следующих процедур:

  • Обновление параметров – к примеру, совместно используемых процессами глобальных переменных.
  • Обновление пространственных переменных.
  • Изменение параметров агентов с учетом изменения пространства и поведения агентов, находящихся в непосредственной близости.
  • Изменение поведения агентов, т.е. выполнение запланированных ранее действий.

2.3. Синхронизация

Основной целью этой процедуры является синхронизация буферного и сетевого пространства.

3. Параметры эффективности

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

  1. Интенсивность взаимодействия агентов и горизонт их видимости.
  2. Сложность в поведении агентов. В своем предыдущем исследовании авторы показали, что во многих случаях увеличение сложности агентов и изменение их поведения в целом снижает эффективность распараллеливания соответствующей модели.
  3. Распределение пространства между процессорами. Здесь имеет значение равномерность распределения агентов по сегментам пространства.
  4. Алгоритм синхронизации.

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.

 Evacuation6.JPG

Рис. 6. Пример сетки патчей (справа) созданной на основе данных из файла (слева). Согласно правилам, белые патчи доступны для агентов, а черные – нет.

4.2. Полевая модель (Floor Field model)

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

  1. Направление (Direction) из текущего патча до выхода – DOM.
  2. Расстояние (Distance) от текущего патча до выхода – HOPC.
  3. Маршрут – ROUTE.

Типовая структура переменных для стандартного патча показана на рис. 7.

 Evacuation7.JPG

Рис. 7. Структура поля стандартного патча: (a) направление d варьируется в определенном диапазоне и рассчитывается как относительный угол между отправляющим и принимающим патчами; (b) расстояние h определяется перемещениями до целевого патча; (c) маршрут представляет собой последовательность передающих информацию процессов

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

 Evacuation8.JPG

Рис. 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. Псевдокод, генерирующий поля для патчей

 Evacuation9.JPG

Рис. 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?

мобильный

проверка – является ли агент ведомым по отношению к агенту, обладающему большей информацией, чем он сам?

 Evacuation10.JPG

Рис. 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. Псевдокод, описывающий процедуру принятия решения агентом по перемещению

 Evacuation11.JPG

Рис. 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_densityaggregate_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.

 Evacuation12.JPG

Рис.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.

 Evacuation13.JPG

Рис. 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), в связи с чем, она и была выбрана для симуляции всего пространства.

 Evacuation14.JPG

Рис. 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% агентов.

 Evacuation15.JPG

Рис. 15. Результаты применения отобранных стратегий (4, 5 и 7) передвижений для параллельной версии симулятора в рамках масштаба всего города: количество эвакуированных агентов безотносительно выходов (Sn – стратегии, n – номер конкретной стратегии)

Если более подробно рассмотреть результаты по патчем-выходам (рис. 16 и табл. 4), то мы увидим, что при реализации стратегии 5, выходы используются более равномерно. Кроме того, в случае стратегии 4 в определенный момент времени только 2 из 5 выходов остаются активными.

 Evacuation16.JPG

Рис. 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 уже нет.

 Evacuation17.JPG

Рис. 17. Визуализация пяти патчей-выходов на середине симуляции (2 500 итерация) для стратегии 4 (a-e) и стратегии 5 (f-j)

 Визуальное сравнение стратегий 4, 5 и 7 приведено на рис. 18. К примеру, видно, что когда патч-выход 22 становится недоступным (на итерации 1100), то агенты перемещаются в сторону других выходов.

Общий же вывод по использованным стратегиям следующий. При моделировании систем с большим количеством агентов, несмотря на применение суперкомпьютерных технологий, принципиальное значение имеет детализация модели и степень коммуникации агентов, влияющая на частоту межпроцессорного взаимодействия. Так, упрощение в действиях агентов при применении стратегии 4 (по сравнению со стратегией 1) позволило уменьшить время расчета 5 000 итераций симуляции в рамках масштаба всего города до 12 часов (в то время как за 278 часов удалось просчитать только 4% от общего объема вычислений, необходимых для реализации стратегии 1).

 Evacuation18.JPG

Рис. 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].

rss
Назад

Статьи
Суперкомпьютерные технологии Транспортные модели пешеходная модель Монография Биомедицина Parallel computing Параллельные вычисления Axum Repast Агент-ориентированные модели Исследования Модель экономики Евросоюза Пространственно-распределенные агентные модели большие данные CUDA Russian Supercomputing Days Агент-ориентированный подход Исторические процессы Мониторинг планеты Пространственные модели FuturICT SEGMEnT БРИКС Контакты Публикации Экономические процессы GPU SSC Междисциплинарное исследование Новости Революция Эксафлопная производительность HPABM SWAGES Высокопроизводительные вычисления Методология запуска О проекте Социальная сеть Эпидемия Microsoft Social Simulation Conference ГИС Механизм раделяемой памяти Пандемия Ссылки Ядерная атака на США POLARIS TSUBAME Демография Моделирование мира Пандора Стратегии распараллеливания автоматическое распараллеливание XAXIS Иерархическая платформа Моделирование эпидемий Суперкомпьютерная Академия агентная модель