В Аргоннской национальной лаборатории (национальный исследовательский центр Министерства энергетики США) разработано программное обеспечение для построения агент-ориентированных моделей, в основном используемых для симуляции транспортных потоков.

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

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

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

Таким образом, проект POLARIS, удовлетворяющий сформулированному выше требованию, также позволяет:

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

2. Быстро создавать программные конструкции, используя функции автодополнения кода.

3. При необходимости использовать язык программирования низкого уровня для низкоуровневой оптимизации и распараллеливания разрабатываемого приложения с целью достижения его высокой производительности.

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

Комплект разработчика программного обеспечения с использованием агентного подхода – POLARIS

Ниже описывается модель, разработанная с использованием агент-ориентированного подхода и платформы POLARIS, которая состоит из двух компонент. Первый – высокоуровневая среда для проектирования агент-ориентированных моделей, а второй – комплект разработчика, позволяющий настраивать и оптимизировать построенные с помощью высокоуровневого компонента модели. Эта платформа представляет собой среду разработки с открытым исходным кодом, а также набор определенных стандартов и протоколов, позволяющих эффективно разрабатывать транспортные модели с возможностью параллельных вычислений. Одна из функциональных особенностей POLARIS – участие в общем проекте нескольких групп программистов в рамках единой моделируемой среды.

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

  

Рис. 1. Схема платформы POLARIS

На самом низком уровне находятся основные библиотеки, реализующие дискретные события, механизмы управлению памятью и межпроцессорного взаимодействия, а также стандарты оформления кода. Эти библиотеки жестко контролируются с целью минимизации их модификации. На следующем уровне платформы находятся основные расширения, представляющие собой набор утилит для визуализации, ввода/вывода данных и т.д. Оба уровня являются общими и их можно использовать для любой модели (и не только транспортной). Ниже мы рассмотрим эти библиотеки и утилиты более подробно. Следующий уровень – репозитарий, включающий в себя модули, которые прошли неоднократное тестирование и могут быть использованы в разных моделях – это хорошо отработанные алгоритмы прокладывания маршрутов, интерфейсы для изменения геометрии транспортных сетей и др. Основной функционал данного репозитария – использование отлаженных компонент в составе будущих моделей, а также его постоянное пополнение силами внешних разработчиков. Следующий уровень – пользовательское пространство POLARIS, в рамках которого разработчики могут экспериментировать с новыми расширениями платформы и тестировать узкоспециализированные функции. Используя элементы всех уровней, разработчики могут собрать готовое приложение, и пример такой сборки будет описан ниже.

Распределитель памяти для симуляций

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

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

В качестве основного распределителя был выбран TCMalloc (Thread-Caching Malloc), разработанный Google. TCMalloc отличается от традиционных распределителей тем, что специально разработан для многопоточных приложений и он был выбран среди других альтернатив за счет своей производительности и кроссплатформенности.

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

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

Модуль для обработки параллельных событий

Одним из центральных элементов платформы POLARIS является модуль для обработки дискретных событий (Discrete EVent Engine, DEVE), оптимизированный для разработки многопоточного кода с использованием распределителя памяти. Он предоставляет собой программный интерфейс, который позволяет создать агента любого типа (человека, автомобиль и т.д.) и описать его деятельность (вид, время начала функционирования, продолжительность и др.).

Агенты проявляют свои намерения посредством «событий», а в свою очередь DEVE организует выполнение функций агентов в установленном разработчиком порядке и вместе с тем упорядочивает потоки для их бесконфликтной работы. Помимо этого, модуль DEVE разрешает проводить различные имитации с использованием программного обеспечения Intel VTune, позволяющего выявить и устранить узкие места в плане производительности.

Дополнительные возможности платформы

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

Библиотека Antares предоставляет разработчикам инструменты для 2D или 3D визуализации. Сначала создается слой для представления определенного типа объекта (автомобилей, дорог и др.), а затем слой конфигурируется для передачи геометрических фигур (треугольников, квадратов, точек, линий, многоугольников). Кроме того, можно определить отдельное изображение под конкретный объект (к примеру, рисунок автомобиля поверх первоначальной точки).

В основе Antares лежит графическая библиотека OpenGL, определяющая программный интерфейс для написания приложений, использующих двумерную и трехмерную компьютерную графику, а также wxWidgets – кроссплатформенная библиотека инструментов с открытым исходным кодом для разработки приложений с использованием графического интерфейса пользователя. Также отметим, что Antares обеспечивает многопоточность и оптимизацию за счет Intel VTune.

Другой возможностью построения многоагентных моделей, обеспечивающей стандартизацию, является использование унифицированного механизма обмена данными, реализованного в SQLite – компактной встраиваемой СУБД. Библиотеки C++ и Python, доступные как часть проекта POLARIS, позволяют разработчикам считывать все данные из базы данных SQLite, причем реализованная в платформе объектная база данных позволяет использовать язык запросов, написанный на C++ вместо использования SQL.

И, наконец, модуль задания сценариев предоставляет собой набор инструментов для формирования и запуска различных наборов сценариев, описываемых с использованием JavaScript и реализуемых затем в параллельном режиме. При задании сценариев возможно варьировать большим набором параметров (это могут быть погодные условия, дорожные происшествия и др.), а во время реализации в интерактивном режиме можно осуществлять мониторинг их состояния, включая такие показатели как процент выполнения, оставшееся время работы, загрузку кластеров и др. Менеджер сценариев использует PBS (Portable Batch System) – систему управления распределенными вычислениями, основной функцией которой является запуск задач в вычислительной среде по расписанию.

Многоагентная модель, реализованная в POLARIS

Ниже описывается пример модели, реализованной с помощью платформы POLARIS. В реализующем агента классе прописываются методы, отвечающие за различный функционал (формирование спроса на поездки, поведение во время движения и т.д.). Набор компонент интеллектуальной транспортной системы (ИТС) и центр управления движением (ЦУД), реализованные в модели, контролируют всех агентов, представляющих собой участников дорожного движения в Чикаго.

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

• субагент-обработчик информации – собирает и обрабатывает внешнюю информацию;
• субагент-планировщик – решает вопросы планирования и перепланирования;
• субагент-диспетчер – создает и по мере необходимости изменяет ежедневный график поездок;
• субагент-управляющий перемещениями – осуществляет имитацию перемещений в системе;
• субагент-маршрутизатор – выбирает маршруты в сети.

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

Действия агентов можно разделить на четыре компоненты: генерирование активности, планирование, составление графиков поездок, перемещения.

 

Рис. 2. Платформа многоагентной модели спроса

Генерирование активности

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

Планирование и перепланирование деятельности

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

Изменение ежедневного графика поездок

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

Имитация перемещений

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

Модель имитации транспортной сети

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

  

Рис. 3. Схема взаимодействие между агентами в рамках транспортной сети

Модель выбора маршрута

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

Модель генерации маршрута

В рамках модели генерации маршрута рассчитываются кратчайшие расстояния от исходной точки до пункта назначения. У каждого субагента-маршрутизатора есть своя копия сетевой топологии, включающая персонифицированную информацию о прогнозировании транспортных расходов исходя из накопленного опыта. Что касается алгоритма поиска кратчайшего маршрута, то он осуществляется с использованием алгоритма поиска «А звезда» (A star, A*), позволяющего найти путь с наименьшей стоимостью от одной вершины (начальной) к другой (конечной). Кроме того, его использование позволяет эффективно распараллелить мультиагентное приложение.

Модель имитации трафика

Совокупное поведение водителей описывается нелинейным дифференциальным уравнением с частными производными первого порядка. Модель рассчитывает динамику плотности трафика, являющуюся макроскопической характеристикой потока трафика. В POLARIS есть три компоненты, разработанные для вычисления спроса на поездки, работы с сетевыми утилитами и для обработки ряда событий, получаемых от датчиков системы и срабатывающих в процессе симуляции (рис. 4). Последние обеспечивают данными ЦУД, обрабатывающий события, связанные с заторами, ДТП, изменениями погодных условий и т.д.

 

Рис. 4. Компоненты модели управления трафиком

Симуляции и предварительные результаты

Для оценки эффективности платформы POLARIS исследователи провели симуляции для Большого Чикаго (метрополитенский ареал Чикаго) – городской агломерации, в которую входят 10 млн. человек, совершающих в среднем 27 млн. поездок. Компоненты модели были откалиброваны с использованием данных подробной матрицы корреспонденций. На рис. 5 приведены усредненные данные тестовых прогонов модели.

 

Рис. 5. Количество автомобилей в сети в зависимости от времени суток: пунктирная линия – реальные данные, сплошная линия – данные симуляции платформы POLARIS

Для более тщательного анализа был выделен центральный деловой район Чикаго(Chicago CBD), который содержит примерно 5000 дорожных отрезков, 3000 перекрестков, 6500 зон притяжения для 400 000 агентов – участников дорожного движения. Транспортная инфраструктура также включает в себя 20 информационных табло, расположенных вдоль скоростных автомагистралей по всей территории, с меняющимися сообщениями относительно загрузки дорог. В рамках симуляций рассчитывались последствия трех сценариев: 1) обычный день без происшествий; 2) сценарий с ДТП с отключенной информационной инфраструктурой; 3) сценарий с ДТП и включенной информационной инфраструктурой. ДТП в рамках имитации включает в себя девять аварийных событий (это среднестатистический показатель для выбранного района).

На рис. 6 приведен скриншот платформы POLARIS применительно к описанной симуляции. В случае ДТП у соответствующих дорожных отрезков снижается пропускная способность и скорость потока. Агенты, получая информацию с табло, или же непосредственно наблюдая затор, могут инициировать запуск соответствующей субмодели для изменения маршрута.

 

Рис. 6. Дорожная сеть центрального делового района Чикаго с информационными табло, реализованная в платформе POLARIS. Графический пользовательский интерфейс предоставляет возможность интерактивного взаимодействия с симуляцией в процессе ее реализации (к примеру, назначить какие сообщения должны показываться на табло). Места ДТП помечены желтыми маркерами.

Отметим, что пользовательский интерфейс POLARIS поддерживает широкий спектр возможностей для редактирования элементов дорожной сети (перекрестков, слоев ГИС с различными метками и т.д.). Скриншоты упомянутого редактора приведены на рис. 7.

Рис. 7а. Редактор дорожной сети

Рис. 7b. Редактор перекрестков

На рис. 8 отражено влияние ДТП на эффективность дорожной сети с точки зрения времени задержек автомобилей в заторах. Как видно, информационные табло оказывают положительное влияние на отслеживаемый показатель – так, их использование снижает общее время задержек на 3462 часа или 18%.

 

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

Более подробно про POLARIS можно прочитать здесь: [Joshua Auld, Michael Hope, Hubert Ley, Vadim Sokolov, Bo Xua, Kuilin Zhang (2016): POLARIS: Agent-based modeling framework development and implementation for integrated travel demand and network and operations simulations // Transportation Research Part C: Emerging Technologies, Volume 64, March 2016, pp. 101-116.]