автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Моделирование поведения толпы с использованием локальных скалярных полей

Гребенников Роман Владимирович

МОДЕЛИРОВАНИЕ ПОВЕДЕНИЯ ТОЛПЫ С ИСПОЛЬЗОВАНИЕМ ЛОКАЛЬНЫХ СКАЛЯРНЫХ ПОЛЕЙ

Специальность 05.13.17 - «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

1 2 МАЙ 2011

Воронеж-2011

4845512

Работа выполнена в ГОУ ВПО «Воронежский государственный университет»

Научный руководитель: кандидат физико-математический наук,

доцент

Тюкачев Николай Аркадиевич

Официальные оппоненты: Доктор технических наук,

профессор

Барабанов Владимир Федорович

Защита состоится « 25 » мая 2011 года в 16-30 на заседании диссертационного совета Д 212.038.24 при Воронежском государственном университете по адресу: 394006, г. Воронеж, Университетская пл., д. 1, ВГУ, ауд.

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО «Воронежский государственный университет».

Автореферат разослан « 22 » апреля 2011 г.

Ученый секретарь диссертационного совета

кандидат физико-математический наук, доцент

Степанцов Михаил Евгеньевич

Ведущая организация: ГОУ ВПО «Воронежский государственный

архитектурно-строительный университет»

226.

Д 212.038.24

Чеботарев А.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

• оптимизация пропускной способности транспортных систем;

• действия толпы в экстремальных ситуациях (например, пожар или террористический акт);

• создание поведенчески-реалистичных виртуальных толп в компьютерной графике в кино и играх.

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

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

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

Разработкой и усовершенствованием моделей, методов и средств компьютерного моделирования толпы занимаются многие отечественные и зарубежные исследователи, среди которых В.М. Предтеченский, М.Я. Ройтман, В.В. Холщевников, C.B. Беляев, А.Н. Овсянников, Д. Толлман (D. Thallmann), С. Мусс (S. Musse), Д. Терзопулос (D. Terzopoulos), Д. Хелбинг (D. Helbing), Р. Хагс (R. Hughes), А. Трюи (A. Treuille), С. Рейнолдс (С. Reynolds) и др. Несмотря на то, что проблема моделирования поведения толпы исследована достаточно глубоко, существующие модели имеют определенные недостатки: зачастую фактически отсутствует этап тестирования и сравнения результатов моделирования с поведением реальных толп - эти модели являются гипотезами. Также в

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

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

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

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

Для достижения цели работы необходимо решить следующие задачи:

1. Проведение анализа существующих моделей поведения толпы.

2. Определение системы показателей эффективности поведения толпы.

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

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

5. Разработка структуры программного обеспечения, реализующего предложенные алгоритмы моделирования поведения толпы.

6. Проведение экспериментальных исследований для оценки практической применимости полученных результатов, проведение натурного эксперимента.

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

Основные результаты, выносимые на защиту, и их научная новизна. В

результате диссертационного исследования получены новые результаты, касающиеся изучения поведения толпы:

1) модель поведения толпы, основанная на использовании локальных скалярных полей и позволяющая с более высокой точностью

проводить имитационные исследования поведения больших групп объектов в различных условиях;

2) роевый алгоритм оптимизации подходящего пути для каждого объекта;

3) система показателей эффективности, позволяющая сравнивать оптимальность поведения толп;

4) процедура проверки адекватности предложенной модели на основании данных, полученных в результате проведения эксперимента;

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

В диссертации получены следующие результаты, обладающие научной новизной:

• предложена модель поведения толпы, основанная на локальных скалярных полях, отличающаяся высоким уровнем соответствия поведению реальной толпы;

• впервые сформулирована система показателей эффективности для сравнения различных моделей поведения толпы;

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

Экспериментально подтверждена адекватность предложенной модели в рамках проведенного натурного эксперимента.

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

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

Теоретические и практические результаты работы внедрены в деятельность ООО «МарКо» и реализованы в виде программной системы, о чем свидетельствует соответствующий акт внедрения. Данная программная система также зарегистрирована в отраслевом фонде алгоритмов и программ СФАП.

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

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

Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.17 «Теоретические основы информатики» (технические науки) по следующим областям исследований:

п. 2 «Разработка и анализ моделей информационных процессов и структур»;

п. 8 «Исследование и когнитивное моделирование интеллекта, включая моделирование поведения, рассуждений различных типов, моделирование образного мышления».

Апробация работы. Основные результаты диссертационного исследования докладывались на IX международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2009), международной научной конференции студентов, аспирантов и молодых учёных "Ломоносов-2010" (Москва, 2010), XXIX научно-технической конференции «Информационные технологии в науке, проектировании и производстве» (Нижний Новгород, 2010), международной научно-практической конференции «Гибридный Интеллект 2010» (Воронеж, 2010), а также на научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов ГОУ ВПО «Воронежский государственный университет».

Структура и объем работы. Диссертационная работа изложена на ИЗ страницах и состоит из введения, четырех глав, разбитых на параграфы, заключения, приложений и библиографического списка из 101 пункта. Данная работа также включает в себя 38 рисунков и 10 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

1) многие модели не позволяют работать с гетерогенными толпами;

2) зачастую отсутствует этап проверки модели на адекватность;

3) не объясняется выбор свободных параметров системы, ощутимо влияющих на поведение объектов.

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

Во второй главе предлагается гибридная модель поведения толпы, совмещающая в себе положительные черты нескольких подходов к моделированию поведения толп и расширяющая собой модель А. Трюи по следующим направлениям: использование множества локальных полей вместо одного глобального, учет области видимости для агентов, устойчивость к локальным минимумам и обучение модели на данных, описывающих поведение реальных толп. Структура предлагаемой модели показана на рисунке 1.

Подходы

И

Локальные поля

Мультиагентный --------------------

_метод__Предлагаемая

подход

Устойчивость к локальным минимумам

Область видимости

\ Подбор параметров системы

Рис. 1. Структура предлагаемой модели

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

Правило 1. Каждый агент пытается достичь определенной географической

цели.

Правило 2. Агенты двигаются на максимально возможной в текущих условиях скорости. Данное утверждение может быть выражено в виде поля максимальной скорости/ в соответствии с которым агент в точке х, двигающийся в направлении 0, имеет скорость X.

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

Правило 4. Каждое используемое правило имеет смысл лишь в рамках видимости конкретного агента. Другими словами, существует видимая область V, на которой могут быть определены все используемые поля.

Правило 5. Пусть П - совокупность всех возможных путей из точки х к заданной цели. С учетом заданных поля скорости У7, поля плотности окружающей толпы Р, поля окружающих препятствий И7 и цели С, агент в точке * выберет такой путь Р из множества Я, чтобы следующая величина была минимальна:

представляющая собой взвешенную сумму полей цели и дискомфорта. В данном случае a,ß,y- веса для отдельных факторов, G(x), Р(х), W(x) - скалярные поля цели, плотности окружающей толпы и препятствий.

Ф,. (.v) = aG,(х) + ffi(x) + yfV,.(x),

(1)

Рис. 2. Визуализация меры стоимости движения

Данная сумма представляет собой индивидуальную для /-того агента меру стоимости движения через точку х. Визуализация данной величины показана на рисунке 2а в трехмерной форме и на рисунке 26 в виде линий уровня (без учета области видимости).

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

Все подходящие классы функций являются функциями нескольких ! переменных:

6 «.с е Я) -> Я, (2)

где, для двухмерного случая, ■гт,п,^11В1>лп41,дстт - точки, ограничивающие как I аргумент х: х,щп<х<хтах , так и значения самой функции: 5,„„,<$<.5,„о, . Функция л-может быть представлена в виде разных семейств функций: линейная, экспоненциальная и сигмоидальная. | Также на функцию 5 наложен ряд ограничений:

= Ущ,< "Р11 Х г Х«ш (3)

У подхода, использующего градиентный спуск, предложенного в работе А. Трюи, есть важный недостаток - попадание системы в локальные минимумы.

Пример такой ситуации изображен на рисунке 3.

Для избегания локальных минимумов в данной работе предлагается использовать роевый алгоритм (PSO, англ. Particle Swarm Optimization) для решения задачи нелинейной условной оптимизации. Выбор именно данного метода был обусловлен отсутствием необходимости в вычислении градиента целевой функции, а также необходимости применения условной нелинейной оптимизации. Применительно к описываемой модели, задача оптимизации выглядит следующим образом: (х):Х, X, =V, пВ, (4)

Ф, (х) —> mm

хеХ.[

причем допустимое множество X, представляет собой пересечение множества V, (область видимости i'-того участника толпы) и 5/ (ближайшие окрестности точки х„ \х-х.\<с1). Таким образом, вектор движения отдельного участника толпы выглядит следующим образом:

x = f{x,ff)xdrso{x,0{x)) (5)

где Ор5о ~ функция поиска минимума функции Ф в окрестностях Хг

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

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

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

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

Ж ■

- ■■: ■ Зчv \ i " Ь t-7 к а \ в \ ; V

Рис. 3.

Ф,

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

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

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

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

1. Глобально заданной цели для агента (или для всей толпы), определенной еще до этапа симуляции.

2. Препятствий, расположенных на окружающем ландшафте.

Пусть для /'-того агента толпы определена цель g¡. Тогда без учета препятствий скалярное поле, отображающее положение агента на текущее значение поля цели, выглядит следующим образом:

где х-, - положение /-ого агента.

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

при О,(х в,(х,) = -8,||.«я-™„...*8.т>х.)

при в,(х )й V,, в,(х,) = 0, (7)

где V,- - видимая г-тым агентом область пространства, g¡ - точка глобальной цели для /-ого агента, х,- - координата агента.

Поле дискомфорта. Поле дискомфорта описывает влияние на агента всех внешних факторов, в числе которых:

• плотность окружающей толпы;

• препятствия и стены.

В данной работе предлагается перейти к локальному представлению данного поля и рассчитывать поле дискомфорта индивидуально для каждого участника толпы.

11

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

к

где ■^'ц1,ни'!' $н'.тах> хктиъ хп.тсш, с\и — константы.

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

Р,(*,)=£-**||,, ^,хрг1ап,хргшх ,ср). (9)

к,кп

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

• от параметров рельефа (характера возвышенностей);

• от плотности окружающей толпы.

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

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

/(*, 0)=^Р(х+гп11), Ртю ,Мх,в), Раа, /и (х, 0), с,). (10)

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

/г (х. в) = /„ + (Щ{Х)По~5т-М1т - /„„ ) при Р < Ртт

/и(х,в) = и(х + гп1))п„ при р> р11ая . (11)

Дх,в) = х(р(х + гпв Л (х, в), />,„„ , /у (х,в),Сг) при рт„<р< ртл

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

На основании

рассмотренных выше

алгоритмов расчета полей и модели поведения толпы становится возможным

предложить структурную схему алгоритма расчета вектора движения для каждого участника толпы. Данная структурная схема представлена на рисунке 4.

В четвертой главе

описана программная

реализация предложенного ранее метода моделирования поведения толпы,

позволяющая экспериментально оценить его эффективность на различных модельных

ситуациях, а также р рассмотрен процесс обучения модели на

статистических данных о поведении реальных толп. Приводится описание натурного эксперимента с использованием предлагаемой модели.

Разработанное программное обеспечение имеет следующую структуру:

1. Конструктор внешней среды и начальных параметров для тестирования модели.

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

3. Пользовательский интерфейс визуализации полученных результатов.

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

Расчет компонешев меры стоимо ти движения

Поле«ели1 дискомфорта] I Ск°Р°сть

Расчет меры стоимости движения

I Расчет

' вектора движения

^ Остались ли ' \ < необработанные агенты?"

¡Следующий: агент

Следующий| шаг I

да

Последний ли это шаг моделирования? ;

да

конец

Реализация алгоритма проводилась на ПК под управлением операционной системы Gentoo Linux 2.0.1 -г 1 со следующей конфигурацией: Intel Celeron CULV 723 1.3GHz, 2Gb ОЗУ.

Для реализации требования о возможности расширения функционала было принято решение о проектировании предложенного программного комплекса с использованием объектно-ориентированного и паттерна модель-представление-контроллер.

Для разработки предложенного программного обеспечения был выбран язык программирования С++ и набор библиотек Nokia Qt. На рисунке 5 показана покадровая визуализация движения толпы в простейшем окружении.

«0 й» Ц tri , ! * в f ' ti ,♦(» а 1 Щ*9ГЗ 1 m^fV 1 8 ; s ер 1 * 1 . S, а Г* « ij ¡1 «VJ Ä I " h

[ . | ! [ J_____^______________J 1 * j р.........J

у;. 1 I 'ft? 1ф"13 : 1 .1 . «, f ■ —-t*~V „ j 1 ¿?Г i» 1 1....... ^ ® a j , 1

| ^ 1......^................: I * *• <

(г 1 'j : iy'' i!; | ; i - ; '" : £3| I у j 1 'O-*, ... f

- Е 1 ^ * \ I ^ * \

Рис. 5. Покадровая визуализация движения толпы

Также в четвертой главе описан процесс обучения и апробации модели. На первом этапе был проведен процесс обучения предложенного алгоритма моделирования поведения толпы путем подбора внутренних параметров системы на экспериментальных данных с использованием классического генетического алгоритма (длина гена п=7 7, размер популяции 500 генов, 100 поколений, доля мутаций - 15%, доля выживших - 85%).

Задача обучения модели представляет собой задачу условной нелинейной оптимизации:

/(Р, -Р„) п™.

р, е* = {р |/>,,„„ <р, <Л„./ = 1..л}сЛ,,где/(д...Л):^»-»Л (12)

где /- функция фитнеса, />,;,„,„ и ришх - ограничения, накладываемые на выбор параметра р¡.

Алгоритм процесса обучения выглядит следующим образом:

1. Для каждого из окружений, изображенных на рисунке 6, был выделен набор измерительных зон. ] 2. Формировался начальный вектор внутренних параметров системы.

3. В коридор запускалась виртуальная толпа, и на каждой зоне производились замеры пар значений плотность-скорость толпы.

4. Из полученных данных для каждого диапазона плотностей и для каждой модели был построен набор гистограмм, произведено сравнение с эталонными распределениями, представленными в работе Предтеченского. Один из вариантов набора подобных промежуточных гистограмм показан на рисунке 7.

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

6. Шаги 2-5 повторялись до наступления условия останова.

Рис. 6.

--Эксперимен!

........... НуЬпс!

---Тгеш11е

------ ЧеугоЮБ......

р=0.1...0.2 ч/мг

--Эксперимент

—..............НуЬгИ

----ТгеиМе

----КвупоНэ

р-0.5...0.6 Ч/Мг

Рис. 7. Гистограммы распределения скоростей для каждого диапазона плотности толпы Для подтверждения адекватности разработанной модели был проведен эксперимент с реальной толпой. Суть эксперимента состояла в следующем: толпа проходила через дверные проемы различной ширины, в процессе замерялась скорость каждого участника толпы, а также плотность некоторой области толпы, находящейся внутри дверного проема. Задача эксперимента состояла в измерении времени покидания помещения толпой. В дальнейшем было проведено моделирование данной ситуации с использованием предложной модели поведения толпы, модели Трюи, Рейнолдса и сравнение смоделированных и реальных результатов.

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

Таблица 1. Время выхода из помещения, сек., Р=0.5м

Реапьн. Гибрид. Рейнолдс Трюи

Среднее 38,5142 36,7757 46,1855 46,5781

Стандартное отклонение 2,6939 2,7166 1,7973 1,5669

Доверит, интервал (95,0%) 0,9253 0,9332 0,6174 0,5382

Таблица 2. Время выхода из помещения, сек., Р=0,7м

Реальн. Гибрид. Рейнолдс Трюи

Среднее 33,7428 32,1777 39,0034 38,4340

Стандартное отклонение 1,0666 2,1417 2,1676 2,3930

Доверит, интервал (95,0%) 0,3664 0,7357 0,7446 0,8220

Таблица 3. Время выхода из помещения, сек., Р=1,4м

Реальн. Гибрид. Рейнолдс Трюи

Среднее 18,0857 21,2225 21,4712 20,7588

Стандартное отклонение 2,4539 1,4569 2,7074 2,0747

Доверит, интервал (95,0%) 0,8429 0,5004 0,9300 0,7127

Как видно из таблиц 1-3, предложенная в данной работе гибридная модель поведения толпы показала результат, наиболее близкий к реальным данным.

В заключении делаются выводы, излагаются основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В диссертации получены следующие результаты:

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

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

3. Проведен сравнительный анализ различных алгоритмов, описывающих поведение толпы, даны рекомендации по их использованию.

4. Произведено экспериментальное подтверждение адекватности представленной модели.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

По теме диссертации автором опубликовано 10 научных работ, из них работы [3], [4], [10] - в изданиях, рекомендованных ВАК РФ. В работе [5], выполненной в соавторстве, доля автора - 90%. Общий объем публикаций - 2,75 п. л. Основные положения диссертационного исследования опубликованы, список публикаций включает:

1. Гребенников Р.В. Разработка индивидуальных характеров поведения при моделировании толпы // Вестник ВГУ, Системный Анализ и информационные технологии. - Воронеж: ВГУ, 2008. -№2. - с. 41-44.

2. Гребенников Р.В. Модель поведения толпы на основе локальных потенциальных полей // Вестник ВГУ, Системный Анализ и информационные технологии. - Воронеж: ВГУ, 2009. - №1- с. 46-50.

3. Гребенников Р.В. Модель поведения толпы на основе локального планирования пути // Вестник ВГТУ. - Воронеж: ВГТУ, 2009. - №9, т.5.-с. 77-81.

4. Гребенников Р.В. Решение задачи об оптимальном управлении толпы с использованием метода оптимизации роя частиц // Вестник ВГУ, Системный Анализ и информационные технологии - Воронеж: ВГУ, 2009.-е. 87-91.

5. Гребенников Р.В. Апробация различных методов поведения толпы. / Р.В. Гребенников, H.A. Тюкачев // Сборник работ участников конференции «ИТ-2010». - Н.Новгород: 2010. - с. 10-12.

6. Гребенников Р.В. Метод имитационного моделирования групповой динамики толпы // Материалы Международного молодежного научного форума «JIOMOHOCOB-2010», Вычислительная математика и кибернетика. - М.: МГУ, 2010. - с. 47-48.

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

Р.В. Гребенников // Сборник работ участников конференции «Гибридный Интеллект 2010». - Воронеж: МИКТ 2010. - с. 13-19.

8. Гребенников Р.В. Обзор классических методов моделирования поведения толпы // Межвузовский сборник научных трудов. Серия: Оптимизация и моделирование в автоматизированных системах. -Воронеж: ВГТУ, 2010.-е. 50-53.

9. Гребенников Р.В. Обзор АБРЬУ и графоаналитических методов моделирования толпы // Межвузовский сборник научных трудов. Серия: Оптимизация и моделирование в автоматизированных системах. - Воронеж: ВГТУ, 2010. - с. 210-214.

10.Гребенников Р.В. Гибридная модель поведения толпы // Прикладная Информатика. - М.: МАРКЕТ ДС, 2011. - №2. - с. 14-22.

Подписано в печать 18.04.11. Формат 60x84 716. Усл. псч. л. 1. Тираж 80 экз. Заказ 516.

Отпечатано с готового оригинал-макета в типографии Издатсльско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Введение.

Глава 1. Проблема поведения толпы.

1.1. Задача моделирования толпы.

1.2. Подходы к созданию моделей поведения толпы.

1.2.1. Клеточные автоматы.

1.2.2. Непрерывные модели.

1.2.3. Броуновское движение.

1.2.4. Ньютоновская механика.

1.2.5. Мультиагентные методы.

1.2.6. Гибридные методы.

1.2.7. Графоаналитический метод.

1.2.8. Модель АБРЬУ.

1.3. Исследования о поведении реальных толп.

1.4. Выводы.

1.5. Постановка задачи.

Глава 2. Моделирование поведения толпы.

2.1. Структура предлагаемой модели.

2.2. Правила поведения людей в толпе.

2.3. Типы функций описания полей.

2.4. Поиск оптимального пути.

2.5. Оценка эффективности работы моделей поведения толпы.

2.5.1. Мера средней дистанции пути.

2.5.2. Мера средней кривизны пути.

2.5.3. Мера затраченного на путь времени.

2.5.4. Мера доли агентов, дошедших до финиша.

2.6. Выводы.

Глава 3. Алгоритмизация процедуры построения набора полей.

3.1. Алгоритмы полей.

3.1.1. Предыдущие работы.

3.1.2. Расчет дискретных полей.

3.1.3. Расчет непрерывных полей.

3.2. Алгоритм построения набора полей.

3.2.1. Расчет поля цели.

3.2.2. Расчет поля дискомфорта.

3.2.3. Расчет функции максимальной скорости.

3.3. Обучение системы.

3.4. Оценка вычислительной трудоемкости.

3.5. Алгоритм расчета вектора движения для участника толпы.

3.6. Сравнение с существующими моделями поведения толпы.

3.7. Выводы.

Глава 4. Программная реализация модели поведения толпы.

4.1. Структура программного обеспечения.

4.2. Программная платформа.

4.3. Программная реализация.

4.3.1. Модуль «Конструктор».

4.3.2. Модуль «Рендерер».

4.3.3. Модуль «Визуализатор».

4.3.4. Формат обмена данными между модулями.

4.4. Графический интерфейс.

4.4.1. Окно «Визуализатор».

4.4.2. Пример визуализации процесса моделирования.

4.5 Обучение модели.

4.6. Натурный эксперимент.

4.7. Выводы.

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

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

• Толпа как часть транспортной системы. Оптимизация пропускной способности транспортных систем. [50]

• Культурно-массовые и спортивные мероприятия. Действия толпы в экстремальных ситуациях (пожар, террористический акт). [101]

• Паломничества. Проверка маршрутов массового движения людей на предмет критических областей для избегания давки. [44]

• Политические демонстрации. Управление поведением толп.[94]

• Пожарная эвакуация. Анализ зданий на предмет соответствия нормам безопасности. [7]

• Визуализация в компьютерной графике. Моделирование реалистичных толп с поведенческой точки зрения. [43]

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

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

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

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

Для достижения цели работы необходимо решить следующие задачи:

1. Проведение анализа существующих моделей поведения толпы.

2. Определение системы показателей эффективности поведения толпы.

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

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

5. Разработка структуры программного обеспечения, реализующего предложенные алгоритмы моделирования поведения толпы.

6. Проведение экспериментальных исследований для оценки практической применимости полученных результатов, проведение натурного эксперимента.

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

Основные результаты, выносимые на защиту и их научная новизна.

В результате диссертационного исследования получены новые результаты, касающиеся изучения поведения толпы:

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

2. Роевый алгоритм оптимизации подходящего пути для каждого объекта.

3. Система показателей эффективности, позволяющая сравнивать оптимальность поведения толп.

4. Процедура проверки адекватности предложенной модели на основании данных, полученных в результате проведения эксперимента.

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

Научная новизна. В диссертации получены следующие результаты, обладающие научной новизной

• предложена модель поведения толпы, основанная на локальных скалярных полях, отличающаяся высоким уровнем соответствия поведению реальной толпы;

• впервые сформулирована система показателей эффективности для сравнения различных моделей поведения толпы;

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

Экспериментально подтверждена адекватность предложенной модели в рамках проведенного эксперимента.

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

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

Теоретические и практические результаты работы внедрены в деятельность ООО «МарКо» и реализованы в виде программной системы, о чем свидетельствует соответствующий акт внедрения. Данная программная система также зарегистрирована в отраслевом фонде алгоритмов и программ СФАП.

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

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

Апробация работы. Основные результаты диссертационного исследования докладывались на IX международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2009), международной научной конференции студентов, аспирантов и молодых учёных "Ломоносов-2010" (Москва, 2010), XXIX научно-технической конференции «Информационные технологии в науке, проектировании и производстве» (Нижний Новгород, 2010), международной научно-практической конференции «Гибридный Интеллект 2010» (Воронеж, 2010) а также на научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов ГУП ВПО «Воронежский государственный университет»

Область исследования. Содержание диссертации соответствует специальности 05.13.17 «Теоретические основы информатики» по следующим областям исследований: исследование и когнитивное моделирование интеллекта, включая моделирование поведения, рассуждений различных типов, моделирование образного мышления (п.8 паспорта специальности), разработка и анализ моделей информационных процессов и структур (п.2 паспорта специальности).

Публикации. По материалам диссертации опубликовано 10 научных работ, в том числе 3 в изданиях, рекомендованных ВАК РФ.

Структура и объем диссертации. Диссертационная работа изложена на 113 страницах и состоит из введения, четырех глав, разбитых на параграфы, заключения, приложений и библиографического списка из 101 пункта. Данная работа также включает в себя 38 рисунков и 10 таблиц.

4.7. Выводы

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

Была проведена серия экспериментов по сравнению полученной модели как с уже существующими моделями поведения толпы, так и с реальными толпами.

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

Заключение

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

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

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

3. Проведен сравнительный анализ различных алгоритмов, описывающих поведение толпы, даны рекомендации по их использованию.

4. Произведено экспериментальное подтверждение адекватности представленной модели.

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

1. Андреев А.О. Экспресс-оценка возможностей первичных средств пожаротушения в управленческих решениях при осуществлении государственного пожарного надзора // Дис. канд. техн. наук. — М.,2000.

2. Айбуев З.С. Формирование людских потоков на предзаводских территориях крупных промышленных узлов машиностроительного профиля // Дис. канд. техн. наук. -М., 1989.

3. Аптуков A.M., Моделирование групповой динамики толпы, паникующей в ограниченном пространстве / Аптуков A.M., Брацун Д.А. // Вестник Пермского университета. Серия: Математика. Механика. Информатика, 2009. №3. - с. 18-23.

4. Беляев C.B. Эвакуация зданий общего назначения // М.: 1938.

5. Богданов К.Ю. Динамика паникующей толпы // М.: Квант, 2005. — №5.-с. 2-7.

6. Вайдлих В. Социодинамика: системный подход к математическому моделированию в социальных науках // М: Едиториал УРСС, 2005. 480с.

7. ГОСТ 12.1.033-81. ПОЖАРНАЯ БЕЗОПАСНОСТЬ. Термины и определения.

8. Гребенников Р.В. Модель поведения толпы на основе локальных потенциальных полей // Вестник ВГУ, Системный Анализ и информационные технологии. Воронеж: 2009. - Т.1. - с. 46-50.

9. Гребенников Р.В. Модель поведения толпы на основе локального планирования пути // Вестник ВГТУ Часть 9, Т.5. - Воронеж: ВГТУ, 2009-с. 77-81.

10. Ю.Гребенников Р.В. Решение задачи об оптимальном управлении толпы с использованием метода оптимизации роя частиц //

11. Вестник ВГУ, Системный Анализ и информационные технологии.- Т.2. Воронеж: ВГУ, 2009. - с. 87-91.

12. П.Гребенников Р.В. Разработка индивидуальных характеров поведения при моделировании толпы // Вестник ВГУ, Системный Анализ и информационные технологии. — Т.2. — Воронеж: ВГУ, 2008.-с. 41-44.

13. Гребенников Р.В. Апробация различных методов поведения толпы / Гребенников Р.В., Тюкачев Н.А. // Сборник работ участников конференции «ИТ-2010». Н.Новгород: 2010. - с. 10-12.

14. Гребенников Р.В., Метод имитационного моделирования групповой динамики толпы // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2010», Вычислительная математика и кибернетика. Москва: МГУ, 2010.- с. 47-48.

15. Гребенников Р.В. Гибридная модель поведения толпы // Прикладная Информатика. Москва: Маркет ДС, 2010. — Т.4. - с. 14-22.

16. Гребенников Р.В. Обзор и анализ существующих математических моделей поведения толпы с точки зрения социальной психологии // Сборник работ участников конференции «Гибридный Интеллект 2010». Воронеж: МИКТ, 2010. - с. 13-19.

17. Гребенников Р.В. Обзор классических методов моделирования поведения толпы // Межвузовский сборник научных трудов. Серия: Оптимизация и моделирование в автоматизированных системах. Воронеж: ВГТУ, 2010. - с. 50-53.

18. Гребенников Р.В. Обзор АЕ)РЬУ и графоаналитических методов моделирования толпы // Межвузовский сборник научных трудов. Серия: Оптимизация и моделирование в автоматизированных системах. Воронеж: ВГТУ, 2010. - с. 210-214.

19. Дмитриченко A.C. Новый подход к расчету вынужденной эвакуации людей при пожарах / Дмитриченко A.C., Соболевский С.А., Татарников С.А. // Пожаровзрывобезопасность. 2002. -№6.

20. Иванов И.П. Физика сложных систем — динамика паникующей толпы // Научная сеть, 2009. URL: http://nature.web.ru/db/msg.html?mid=l 181350&uri=page2.html (дата обращения: 01.04.2011).

21. Исаевич И.И. Разработка основ многовариантного анализа планировочных решений станций и пересадочных узлов метрополитена на основе моделирования закономерностей движения людских потоков // Дис. канд. техн. наук. — М., 1990.

22. Капица С., Модель роста населения земли и экономического развития человечества // Вопросы экономики. — 2000. №12.

23. Копылов В.А. Исследование параметров движения людей при вынужденной эвакуации // Дис. канд. техн. наук. — М., 1974.

24. Лебон Г. Психология народов и масс. / Пер. с фр.; Предисл. И. Владимирова. М.: ТЕРРА - Книжный клуб, 2008. - 272с.

25. Литвак Б. Групповая динамика. Общая характеристика толпы // Клуб Кросс, 2009. URL: http://www.cross-club.m/harakteristika tolpy.html (дата обращения: 01.04.2010).

26. Манилов Е.А. Автоматизированная система прогнозирования поведения паникующей толпы // Обозрение прикладной и промышленной математики. М: 2008. - №15(3). - с. 500-501.

27. Мокшанцев Р.И. Социальная психология. / Мокшанцев Р.И., Мокшанцева A.B. // Учебное пособие. Серия «Высшее образование». Новосибирск: 2001. -408с.

28. Назаретян А.П. Психология стихийного массового поведения // Лекции.-М.:ПЕРСЭ, 2001.-е 101-112.

29. Письмиченко Д.В. Мультиагентная модель поведения толпы / Письмиченко Д.В., Божич В.И. // Известия II РТУ. Таганрог: 2002.-№26(3).-с 19-22.

30. Овсянников А.Н. Закономерности формирования структуры коммуникационных путей в крытых зрелищных сооружениях // Дис. канд. техн. наук. — М., 1983.

31. Овсянников А.Н. Закономерности маршрутизации людских потоков в зрелищных сооружениях / Овсянников А.Н., Холщевников В.В. // Исследования по функциональным физико-техническим и эстетическим проблемам архитектуры. — Томский госуниверситет, 1988.

32. Предтеченский В.М. Проектирование зданий с учетом организации движения людских потоков. / Предтеченский В.М., Милинский А.И. // Учеб. пособие для вузов. 2-е изд., доп. и перераб. - М: Стройиздат, 1979. — 376 с.

33. Ройтман М.Я. Вынужденная эвакуация людей из зданий // М: Стройиздат, 1965. 111с.

34. Степанцов М.Е. Математическая модель направленного движения группы людей // Математическое моделирование, 2004. — т. 16(3). с. 43-49.

35. Таранцев A.A. Моделирование параметров людских потоков при эвакуации с использованием теории массового обслуживания.// Пожаровзрывобезопасность. — М: Пожнаука, 2002. №6.

36. Таранцев A.A. Об одной задаче моделирования эвакуации с использованием теории массового обслуживания.// Пожаровзрывобезопасность. М: Пожнаука, 2002. -№3.

37. Тростянский С.Н. Имитационное моделирование формирования эффекта толпы / Тростянский С.Н., Панов A.B. // Системыуправления и информационные технологии. 2007. - №3.2(29). -с. 299-302.

38. Холщевников В.В. Эвакуация и поведение людей при пожарах / Холщевников В.В., Самошин Д.А. // Учеб. пособие. М.: Академия ГПС МЧС России, 2009. - 212с.

39. Холщевников В.В. Рекомендации по расчету путей эвакуации из зальных помещений и из зданий спортивных сооружений / Холщевников В.В., Овсянников А.Н., Голубинский А.П., Швейцер И.С. // Справочное пособие к СНиП. — М: Стройиздат, 1991.

40. Холщевников В. В. Обзор компьютерных программ моделирования эвакуации зданий и сооружений / Холщевников В. В., Самошин Д.А., Галушка H.H. //Пожаровзвывобезопасность. М: Пожнаука, 2002. - №5.

41. Холщевников В.В. Расчет оптимальных вариантов пешеходных путей в городских узлах // На стройках России. — 1983. — №3.

42. Холщевников В.В. Моделирование и анализ движения людских потоков в зданиях различного назначения / Холщевников В.В., Никонов С.А., Шамгунов Р.Н. // М: МИСИ, 1986.

43. A1-Gadhi S.A. Simulation of crowd behavior and movement: fundamental relations and application / Al-Gadhi S.A., Mahmassani

44. H.S. // Transportation Research Record number 1320, 260. 1991. - c. 268

45. Aoki I. A simulation study on the schooling mechanism in fish // Bulletin of the Japanese Society of Scientific Fisheries, 48. 1982. - c. 1081-1088.

46. Ball P. The physical modeling of human social systems // Complexus,1.-2003.- 190-206.

47. Barraquand J. A random Sampling Scheme for Path Planning / Barraquand J., Kavraki L., Latombe J.C. // International Journal of Robotics Research, 16(6). 1997. - 759-774.

48. Blue V.J. Cellular automata microsimulation for modeling bidirectional pedestrian walkways / Blue V.J., Adler J.L. // Transp. Res. B 35.-2001.-293-312.

49. Blue V.J. Emergent fundamental pedestrian flows from cellular automata microsimulation / Blue V.J., Adler J.L. // Transportation research board, 1644. 1998. - 29-36.

50. Braun A. Modeling Individual Behaviors in Crowd Simulation / Braun A., Musse S.R., de Oliveira Bardo L.P.L., Bodmann E. J. // Av. Unisinos, 950. Sao Leopoldo.

51. Capin T.K. Integration of Avatars and Autonomous Virtual Humans in Networked Virtual Environments / Capin T.K., Pandzic I.S., Thallmann D. // Proceedings of ICSI89. IOS Press, Amsterdam Netherlands, 1998.-c. 326-333.

52. Daly P.N. Pedestrian speed/flow relationships for underground stations / Daly P.N, McGarth F., Annesley T.J. // Traffic Eng. Control 32, 1998. -c. 75-78.

53. Dogbe N.O. Modeling crowds by the mean-field limit approach // Mathematical and Computer modeling, 2010. Volume 52, Issues 910. -c. 1506-1520.

54. Dorigo M. Particle swarm optimization // Scholarpedia, 2008, 3(11). — c. 1486.

55. Erdmann M. On multiple Moving Objects / Erdmann M., Lozano-Perez T. // AI Memo 883. Boston: AIL MIT, 1986.

56. Fowler M. Patterns of Enterprise Application Architecture // Addison-Wesley, 2003. -c. 200-214.

57. Fruinn J.J. Designing for pedestrians: a level of service concept // Highw. Res. Rec. 355, 1971. c.1-15.

58. Funge J. Cognitive modeling: knowledge, reasoning and planning for intelligent characters / Funge J., Tu X., Terzopoulos D. // Proceedings of SIGGRAPH99, Computer Graphics Proceedings, Annual Conference series. 1999. - c. 29-38.

59. Greenshields B.D. A study of traffic capacity. // Proc. Highw. Res. Board 14. 1934. - c. 448-77.

60. Helbing D. Simulating dynamical features of escape panic / Helbing D., Farkas I., Vicsek T. // Nature 407. 2000. - c. 487.

61. Helbing D. Social force model for pedestrian dynamics / Helbing D., Molnar P. // Phys. Rev. E., 51. 1995. - c. 42-82.

62. Helbing D. Self-organizing pedestrian movement / Helbing D., Molnar P., Farkas I.J., Bolay K. // Environment and Planning B, 28. 2001. -c. 261-384.

63. Henderson L.F., The statistics of crowd fluids // Nature 229. 2001. -c. 381-384.

64. Hughes R.L. A continuum theoiy for the flow of pedestrians. Transp. Res. B 36.-2002.-507-35

65. Kennedy J. Particle Swarm Optimization / Kennedy J., Eberhart R.C. // In Proceeding of the IEEE International Conference on Neural Networks. Perth: IEEE Service Center, 1995. - c. 12-13.

66. Kirchner A. Simulation of competitive egress behavior: comparison with aircraft evacuation data / Kirchner A, Klupfel H, Nishinari K, Schadschneider A, Schreckenberg M. // Physica A 324. 2003. - c. 689-97.

67. Koga Y. Planning motions with intentions / Koga Y., Kondo K., Kuffer J., Latombe J.C. // Proceedings of ACM SIGGRAPH'94. New York: ACM, 1994.-c. 395-408.

68. Lamarche F. Crowd of virtual humans: a new approach for real-time navigation in complex and structuder environments / Lamarche F., Donikan S. // Computer graphics forum 51(3). 2004. - c. 509-518.

69. Latombe J.C. Robot Motion Planning // Boston: Kluwer, 1991.

70. Lerner A. Crowds by example / Lerner A., Chrysanthou Y., Dani L. // Computer Graphics Froum 26(3). 2007. - c. 655-664.

71. Li T.Y. Simulating Virtual Human Crowds with a Leader-Follower Model / Li T.Y., Jeng Y.J., Chang S.I. // Proceedings of IEEE Computer Animation Conference 2001. Seoul: IEEE, 2001.

72. Li T.Y. Interactively directing virtual crowds in a virtual environment. / Li T.Y., Lin J.W., Liu Y.L., Hsu C.M. // Proceedings of the tenth International Conference on Artificial Reality and Tele-existance. -Taipei, 2000.

73. Lighthill M.J. On kinematic waves: I. Flood movement in long ricers; II. Theory of traffic flow on long crowded roads / Lighthill M.J, Whitham G.B. // Proc. R. Soc. London Ser. A 229. 1955. - 281-345.

74. McFarland D. Problems of Animal Behavior // New York: Longman Sci. Technol., 1989.-c. 158.

75. Mendzic I.S. Autonomous actors in networked collaborative virtual environments. / Mendzic I.S., Capin Т.К., Lee E., Magnenat-Thallmann N., Thallmann D. // Proceedings of IEEE Multimedia Modeling'98. 1998. - c. 138-145.

76. Moroshita S. Evacuation of billboards based on pedestrian flow in the concourse of the station / Moroshita S, Shiraishi T. // Lecture notes in computer science. Berlin, Heidelberg: Springer, 2006. — №4173. - c. 716-719.

77. Musse, S. R. Hierarchical Model for Real Time Simulation of Virtual Human Crowds / Musse, S. R., Thalmann, D. // IEEE Transactions on Visualization and Computer Graphics. 2001. - №7 (2). - c. 152-164.

78. Musse S.R. Guiding and Interaction with virtual crowds in real-time / Musse S.R., Garant F., Thallmann D. // Proceedings of Eurographics Workshop on animation and simulation'99. Milan: Springer, 1999. — c. 23-34.

79. Nalluri C. Civil Engineering Hydraylics (4-е изд.) / Nalluri C., Featherstone R.E. Oxford:Blackwell, 2001. - c. 194-53.

80. Navin F. Pedestrian flow characteristics / Navin F., Weeler. R.J. // Traffic Engineering 69(6). — 1969.

81. Neumann J. The general and logic theory of automata // Cerebral Mechanics in Behavior. ~ New York: Wiley, 1951. — c. 1-31.

82. Partridge B. L. The Structure and Function of Fish Schools // Scientific American, June 1982. 1982. - c. 114-123.

83. Perez G.J. Streaming, disruptive interference and power-law behavior in the exit dynamics of confined pedestrians / Perez G.J, Tapang G., LimM., Saloma С.//Physica A 312. -2002,- c. 609-618.

84. Potts, W. K. The Chorus-Line Hypothesis of Maneuver Coordination in Avian flocks // Letter in Nature 309. 1984. - c. 344-345.

85. Pushkarev B. Capacity of walkways / Pushkarev В., Zupan J.M. // Transp. Res. Board. 1975. -№538. - c. 1-15.104

86. Reynolds C.W. Flocks, herds and Schools: A distributed behavioral model // Computer Graphics 21(4) SIGGRAPH'87 conference proceedings. 1987. - c. 25-34.

87. Reynolds C.W. Steering Behaviors for autonomous characters // Proceedings of game developers conference'99. — 1999.

88. Roozemond D.A. Using intelligent agents for pro-active, real-time urban intersection control // European Journal of Operational Research. -2001.

89. Shao, W. Autonomous pedestrians / Shao W., Terzopoulos D. // In SCA'05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer Animation. — New York: ACM Press, 2005. — c. 19-28.

90. Schelling T. Dynamic Models of Segregation // Journal of Mathematical Sociology. -№1. 1971.

91. Smith R.A. Engineering for crowd safety // Amsterdam: Elsevier, 1993.- 442c.

92. Surti H. Investigation of the capacity of the white house sidewalk for orderly demonstrations // Highway Res. Rec. 355. — c. 1625. 1

93. Terzopoulos D. Artificial Fishes: Autonomous Locomotion, Perception, Behavior, and Learning in a Simulated Physical World / Terzopoulos D., Tu X., Grzeszczuk R. // Artificial Life. 1994. - V.l. №4. - c. 327-351.

94. Thallmann D. Virtual humans behavior: individuals, groups and crowds / Thallmann D., Musse S.R., Kallmann M. // Proceedings of digital media futures. 1999. - c. 13-15.

95. Toshiyuki A. Prediction systems of passenger flow // Smith&Dickie, 1993.-c. 249-58.

96. Treuille, A. Continuum crowds / Treuille, A., Cooper, S., Popovic, Z. // In ACM SIGGRAPH 2006 Papers. SIGGRAPH '06. -New York: ACM, 2006.-c. 1160-1168.

97. Trygve M. H. Reenskaug/MVC // XEROX PARC. 1978-79.

98. Varas A. Cellular automata model for evacuation process with obstacles / Varas A, Cornejo MD, Mainemer D, Toledo B, Rogan J, Muñoz V. // Physica A 382. 2007. - c. 631-642.

99. Zhao D.L. Exit dynamics of occupant evacuation in an emergency / Zhao D.L, Yang L.Z, Li J. // Physica A 363. 2006. - c. 501-512.