Применение модели клеточного автомата для моделирования пешеходного движения с гетерогенными участниками

С. А. АЛЮШИН, Д. А. КОЗЛОВЦЕВ

Научный руководитель – Н. И. ИЛЬИНСКИЙ, к. т.н., доцент

Московский инженерно-физический институт (государственный университет)

ПРИМЕНЕНИЕ МОДЕЛИ КЛЕТОЧНОГО АВТОМАТА
ДЛЯ МОДЕЛИРОВАНИЯ ПЕШЕХОДНОГО ДВИЖЕНИЯ
С ГЕТЕРОГЕННЫМИ УЧАСТНИКАМИ

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

В последнее время получают всё большее распространие компьютеризированные интерактивные системы обучения вождению. Важной частью организации эффективного обучения является моделлирование реалистичной окружающей среды [1]. Для создания представления реального мира необходимо имитировать движение множества динамических разнородных объектов – транспортных и пешеходных потоков.

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

Существующие методы и модели непригодны для задачи моделирования пешеходного движения [2]. Классические модели клеточных автоматов неприменимы для систем моделирования пешеходного движения реального времени [3]. Существующие модели, основанные на многоагентном подходе, включают точные спецификации самого объекта и логики его поведения, что неэффективно при большом числе объектов с точки зрения вычислительной сложности [4].

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

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

CA = (L, Σ, δ) (1)

где L – набор дискретных ячеек, представляющий моделируемую среду;

Σ – набор всех возможных состояний автомата;

δ – локальные правила перехода.

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

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

Список литературы:

1.  Wangl Y., Zhangl W., Wul. S. Simulators for driving safety study – a literature review // Virtual reality, LNCS 4563. – Berlin: Springer-Verlag, 2007. P.584-593.

2.  Dijkstra J., Jessurun A. J., Timmermans H. J.P. A multi-agent cellular automata model of pedestrian movement // Peddestrian and evacuation dynamics. – Berlin: Springer-Verlang, 2001. P.173-181.

3.  Maerovet S., Moor B. Cellular automata models of road traffic // Physics reports. 2005. № 000. P.1-64.

4.  Maroto J., Delso E., Felez J. Real-time traffic simulation with a microscopic model // IEEE Transactions on intelligent transportation systems. 2006. Vol. 7. №4.