Моделювання руху пішоходів на основі клітинних автоматів
Представлено клітинно-автоматний метод молелювання ситуацій, що виникають під час руху пішоходів, особливо під впливом непередбачуваних зовнішніх факторів. Розглянуто КА моделі, здатні відтворювати більшість явищ цього руху, обґрунтовано їхнє удосконалення шляхом введення ментальних особливостей. Пр...
Gespeichert in:
| Veröffentlicht in: | Системні дослідження та інформаційні технології |
|---|---|
| Datum: | 2010 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2010
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/49692 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Моделювання руху пішоходів на основі клітинних автоматів / О.С. Макаренко, Д.А. Крушинський // Систем. дослідж. та інформ. технології. — 2010. — № 1. — С. 100-109. — Бібліогр.: 14 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-49692 |
|---|---|
| record_format |
dspace |
| spelling |
Макаренко, О.С. Крушинський, Д.А. 2013-09-24T20:55:24Z 2013-09-24T20:55:24Z 2010 Моделювання руху пішоходів на основі клітинних автоматів / О.С. Макаренко, Д.А. Крушинський // Систем. дослідж. та інформ. технології. — 2010. — № 1. — С. 100-109. — Бібліогр.: 14 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/49692 519.7:517.9 Представлено клітинно-автоматний метод молелювання ситуацій, що виникають під час руху пішоходів, особливо під впливом непередбачуваних зовнішніх факторів. Розглянуто КА моделі, здатні відтворювати більшість явищ цього руху, обґрунтовано їхнє удосконалення шляхом введення ментальних особливостей. Представлен клеточно-автоматный (КА) метод моделирования ситуаций, возникающих во время движения пешеходов, особенно под воздействием непредсказуемых факторов. Рассмотрено КА модели, способные воспроизводить большинство явлений этого движения, обосновано их совершенствование путем введения ментальных свойств. A cellular automaton method for modeling of situations occurring during pedestrian circulation, in particular under the action of unpredictable factors, is presented. Cellular automaton models capable to reproduce most of events of this circulation are considered, and it is shown that they can be improved by introduction of mental factors. Роботу частково профінансовано грантом Ф25/210-2008 ДФФД України. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Системні дослідження та інформаційні технології Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Моделювання руху пішоходів на основі клітинних автоматів Моделирование движения пешеходов на основе клеточных автоматов Modeling of pedestrian circulation on the basis of cellular automatons Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Моделювання руху пішоходів на основі клітинних автоматів |
| spellingShingle |
Моделювання руху пішоходів на основі клітинних автоматів Макаренко, О.С. Крушинський, Д.А. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| title_short |
Моделювання руху пішоходів на основі клітинних автоматів |
| title_full |
Моделювання руху пішоходів на основі клітинних автоматів |
| title_fullStr |
Моделювання руху пішоходів на основі клітинних автоматів |
| title_full_unstemmed |
Моделювання руху пішоходів на основі клітинних автоматів |
| title_sort |
моделювання руху пішоходів на основі клітинних автоматів |
| author |
Макаренко, О.С. Крушинський, Д.А. |
| author_facet |
Макаренко, О.С. Крушинський, Д.А. |
| topic |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| topic_facet |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| publishDate |
2010 |
| language |
Ukrainian |
| container_title |
Системні дослідження та інформаційні технології |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
Моделирование движения пешеходов на основе клеточных автоматов Modeling of pedestrian circulation on the basis of cellular automatons |
| description |
Представлено клітинно-автоматний метод молелювання ситуацій, що виникають під час руху пішоходів, особливо під впливом непередбачуваних зовнішніх факторів. Розглянуто КА моделі, здатні відтворювати більшість явищ цього руху, обґрунтовано їхнє удосконалення шляхом введення ментальних особливостей.
Представлен клеточно-автоматный (КА) метод моделирования ситуаций, возникающих во время движения пешеходов, особенно под воздействием непредсказуемых факторов. Рассмотрено КА модели, способные воспроизводить большинство явлений этого движения, обосновано их совершенствование путем введения ментальных свойств.
A cellular automaton method for modeling of situations occurring during pedestrian circulation, in particular under the action of unpredictable factors, is presented. Cellular automaton models capable to reproduce most of events of this circulation are considered, and it is shown that they can be improved by introduction of mental factors.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/49692 |
| citation_txt |
Моделювання руху пішоходів на основі клітинних автоматів / О.С. Макаренко, Д.А. Крушинський // Систем. дослідж. та інформ. технології. — 2010. — № 1. — С. 100-109. — Бібліогр.: 14 назв. — укр. |
| work_keys_str_mv |
AT makarenkoos modelûvannâruhupíšohodívnaosnovíklítinnihavtomatív AT krušinsʹkiida modelûvannâruhupíšohodívnaosnovíklítinnihavtomatív AT makarenkoos modelirovaniedviženiâpešehodovnaosnovekletočnyhavtomatov AT krušinsʹkiida modelirovaniedviženiâpešehodovnaosnovekletočnyhavtomatov AT makarenkoos modelingofpedestriancirculationonthebasisofcellularautomatons AT krušinsʹkiida modelingofpedestriancirculationonthebasisofcellularautomatons |
| first_indexed |
2025-11-24T22:09:35Z |
| last_indexed |
2025-11-24T22:09:35Z |
| _version_ |
1850499734810132480 |
| fulltext |
© О.С Макаренко, Д.А Крушинський, 2010
100 ISSN 1681–6048 System Research & Information Technologies, 2010, № 1
УДК 519.7:517.9
МОДЕЛЮВАННЯ РУХУ ПІШОХОДІВ НА ОСНОВІ
КЛІТИННИХ АВТОМАТІВ
О.С МАКАРЕНКО, Д.А КРУШИНСЬКИЙ
Представлено клітинно-автоматний метод молелювання ситуацій, що виника-
ють під час руху пішоходів, особливо під впливом непередбачуваних зовніш-
ніх факторів. Розглянуто КА моделі, здатні відтворювати більшість явищ цьо-
го руху, обґрунтовано їхнє удосконалення шляхом введення ментальних
особливостей.
ВСТУП
Упорядкований рух пішоходів набуває великого значення в процесі розвит-
ку міст. Коли зростає кількість його учасників, стають першорядними роз-
робка інфраструктури й планування засобів та сценаріїв керування масовим
рухом людей навіть у повсякденному житті. З виникненням будь-яких над-
звичайних ситуацій, що зумовлені природними катаклізмами (пожежі, пове-
ні, урагани і т.ін.), техногенними аваріями або безпосередньо людською дія-
льністю (терористичні акти, заворушення під час масових подій), ці питання
актуалізуються. Отже, виникає проблема моделювання, яке дасть змогу, по-
перше, краще зрозуміти закономірності, притаманні натовпу; по-друге, ви-
явити «вразливі місця» в існуючій інфраструктурі та планах евакуації; по-
третє, — оптимально проектувати нові ситуациї. Все це потребує адекват-
них і, бажано, швидких в обчисленні моделей.
Першою спробою спрогнозувати рух пішоходів було застосування
відомих моделей фізичних явищ у соціальній сфері. Однак, хоча методи
фізики тривалий час використовувалися для дослідження руху транспорт-
них засобів [1], динаміка пішохідних потоків залишалася мало вивченою [2]
часто через те, що двовимірна природа робить неможливим її опис в межах
простих класичних моделей. Водночас було помічено такі явища, як син-
хронізація, блокування, формування смуг руху (зокрема, у випадку проти-
лежно спрямованих потоків), ударні хвилі, осцилляції тощо.
Особливість об’єкту дослідження — наявність різних режимів (тобто
явищ), що виникають під час паніки, вони суттєво відрізняються від тих, які
спостерігаються у «звичайних» ситуаціях. При цьому необхідно мати мо-
дель, що була б здатна викласти і увібрати весь спектр притаманних руху
натовпу явищ у деякий уніфікований спосіб. До певного часу досить попу-
лярною була модель соціальних сил [3], в межах якої можна досить точно
відтворити реальну поведінку [4]. В цій безперервній моделі пішоходи
взаємодіють через відштовхуючу (соціальну) силу, значення якої експо-
ненційно падає з відстанню між ними. Це означає, що на кожному кроці мо-
делі з N пішоходами потрібно оцінювати )( 2NO взаємодій. Тим паче, що
Моделювання руху пішоходів на основі клітинних автоматів
Системні дослідження та інформаційні технології, 2010, № 1 101
за складної геометрії середовища (розташуванні перешкод) спостерігається
ситуація, коли два пішоходи, що знаходяться поруч, не взаємодіють через
наявність між ними «стіни». Тому, загалом, необхідно додатково перевіряти
наявність взаємодії в кожній парі пішоходів. Для великих натовпів така про-
цедура стає неможливою через обмеженість часу, що зумовлює потребу в
нових підходах до моделювання та нових класах моделей.
Однією з найперспективниших методологій у моделюванні руху натов-
пу є так званий клітинно-автоматний підхід [5,6,7], відповідно до якого мо-
дель містить прості елементи, пов’язані локальною взаємодією з кількома
«сусідами», причому їхня кількість обмежена певною малою константою.
Це призводить до часової складності одного кроку моделі з N пішоходами
О(N) (на відміну від моделі соціальних сил з О(N2). Як правило, елементи
розподілені на решітці з простою геометрією. Деталі цього підходу до
характеристики натовпу пішоходів наведено нижче, але тут за приклад слід
згадати гру «Життя» Дж. Конвея [8]. Останні дослідження КА фізиці та
прикладній математиці засвідчили, що, незважаючи на простий опис елеме-
нтів та правил їх взаємодії, динаміка КА може містити будь-які природні
явища: самоорганізацію, хаос, складну поведінку всієї системи. Яскравими
тут прикладами є моделювання гідродинаміки [9]. Таким чином, істотною
перевагою застосування КА до моделювання руху натовпу є те, що прості (і,
зазвичай, очевидні) правила, які оцінюють поведінку окремого пішохода,
призводять до адекватного опису натовпу як складного об’єкта. При цьому
така модель має ряд особливостей, успадкованих від КА, — лінійну часову
складність, масштабність, стійкість до малих збурень (зокрема за ситуації і
видалення/додавання пішоходів).
КЛАСИФІКАЦІЯ ТА ОПИС ТИПОВОЇ КЛІТИННО-АВТОМАТНОЇ МОДЕЛІ
Поведінку в сучасних моделях можна проранжувати від її заперечення й до
використання штучного інтелекту. Адже класифікацію моделей можна зро-
бити відповідно до двох складових: об’єкта моделювання (які саме особли-
вості потоку пішоходів розглядаються) та засобів моделювання (які схва-
люються гіпотези про зв’язок поведінки натовпу та параметрів пішоходів).
Відповідно до першої складової (об’єкта моделювання) самі моделі по-
діляють на імітаційні (макроскопічні), мікроскопічні (детерміновані моделі,
кінетичні моделі, клітинні автомати) та моделі для прогнозування.
Відповідно до другої складової (засобів моделювання) моделі по-
діляють на: детерміновані та стохастичні (залежно від наявності випадкових
величин у моделі); статичні та динамічні (залежно від організації моделі у
часі); безперервні, дискретні та аналогові (залежно від методів представлен-
ня даних у моделі).
Докладно схарактеризуємо мікроскопічні, стохастичні, дискретні мо-
делі, тотожні за особливостями до описаних у [4, 10]. Це означає, що прави-
ла поведінки висуваються для кожного пішохода окремо, правила переходу
містять випадкові величини, простір та час мають дискретне представлення
(через клітини та кроки відповідно). Основні припущення наступні:
• динаміка може бути представлена засобами КА, тобто моделі, дис-
кретної у просторі та часі;
• бажаний шлях (маршрут руху) є безпосередньо заданим;
О.С. Макаренко, Д.А. Крушинський
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 102
• ірраціональна поведінка є винятковою;
• пішоходи не є конкурентами: вони не травмують один одного;
• індивідуальні відмінності можна представити як параметри, що
впливають на поведінку при пересуванні.
Наведемо коротке визначення КА. Це — дискретна динамічна система,
що є множиною пов’язаних між собою ідентичних клітин, які утворюють
решітку автомата. Решітки бувають різних типів, відрізняючись як за
розміром, так і за «формою» клітин. Основні припущення у класичному клі-
тинно-автоматному підході наступні:
• регулярність — це дискретний простір, дискретний час, дискретні
стани клітин;
• динаміка — це локальний окіл, покрокові правила (детерміновані
або стохастичні).
Нижче наведено опис КА відповідно до [11].
Нехай Zd —d-вимірна решітка; S — скінчена множина станів окремо-
го елемента (клітини) решітки; is з S — стан i-клітини з Zd ( i — індекс
клітини). Конфігурацієя на решітці Zd — це сукупність станів всіх клітин в
певний момент часу. Всі можливі конфігурації утворюють простір
конфігурацій C на Zd . Нехай },2,1,0{ …=T — дискретний час, )(tC —
конфігурація системи у момент часу t ( …,2,1,0=t ). Локальне правило для
клітини k з Zd — перетворення kT , що переводить клітину зі стану )(tsk з
S в момент часу t у стан )1( +tsk з S в наступний момент часу )1( +t ;
))},(({)),(()1( RtsTRtNTts iii ==+ ,
де kN — певний окіл клітини k на решітці Zd ; { )(tsk } — множина станів
клітин з kN , результат перетворення kT залежить лише від станів клітин в
межах околу kN (локальність); R — певні параметри правил, що задають
перетворення. Набір локальних перетворень kT визначає глобальне пере-
творення G на просторі конфігурацій C :
))(()1( tCGtC =+ .
Початкові дані для конфігурації )0(C є заданими і відповідають момен-
ту часу 0=t . Множина всіх локальних перетворень { kT } або глобальне пе-
ретворення G визначають КА на решітці Zd з простором станів клітин S .
Кожна клітина — це завершений автомат, стан якого визначається
станами «сусідніх» клітин та його станом. За апаратної реалізації КА, зазви-
чай, — гомогенні структури, яким притаманні наступні особливості [5, 6, 7]:
• решітка є однорідною;
• час є дискретним, крок у часі — незмінним;
• множина станів клітини містить інформацію про доступність
останньої (є вона перешкодою чи ні);
• функція переміщення є детермінованою. Зміна значень всіх клітин
відбувається одночасно (паралельно).
Моделювання руху пішоходів на основі клітинних автоматів
Системні дослідження та інформаційні технології, 2010, № 1 103
• клітини, шо розташовані поблизу (навколо) заданої клітини, утво-
рюють її окіл. Отже, окіл утворений саме множиною «сусідів», а не довільно
обраних клітин (локальність). Але, в деяких моделях спостерігаються також
і нелокальні взаємодії.
Розглянемо рух пішоходів (частинок) на площині, яка має перешкоди.
Решітка є ортогональною з чотирма (окіл фон Неймана) або вісьмома (окіл
Мура) можливими напрямками руху. Стан клітини відповідає наявності або
відсутності частинки (пішохода) у заданій клітині. Наприклад, на рис. 1 на-
ведено решітку з клітинами різних типів.
Кожна частинка намагається рухатись у певному напрямку, якщо ж та-
кий рух неможливий (через наявність пе-
решкоди або іншої частинки), вона
змінює напрямок руху, продовжуючи
дотритримуватися глобального його на-
прямку. Кожна частинка рухається з пев-
ною швидкістю, що не перевищує задану
максимальну межу maxv .
Решітка КА — це набір двох прямо-
кутних матриць );( VF , F із елементами
ijf , де }1;0{∈ijf відповідає наявності (1)
або відсутності (0) пішохода в заданій
клітині. V — матриця з елементами ijv ,
де }1,0{∈ijv відповідає наявності (1) або
відсутності (0) перешкоди в заданій клітині.
Нижче описано модель для випадку
околу фон Неймана, коли зміна стану
клітини залежить від чотирьох її «сусідів», чиє відносне положення позна-
чається відповідно до чотирьох сторін світу: CESWN ,,,, . (Літери позна-
чають: «north», «west», «south», «east» та «centre»).
Введемо змінну a , що може набувати значень CESWN ,,,, та на-
ступних позначень для клітин в межах околу заданої клітини:
)()(
1
)(
1 ,,, C
ijij
E
ijij
N
ijji ffffff === ++ … .
Подібні позначення вводяться і для елементів матриці V (які є «сусіда-
ми» певної клітини).
Правила переміщення з поточної клітини в одну з «сусідніх» наведено
нижче (вони застосовуються тільки до тих клітин, для яких 1=ijf ). У мо-
делі аналізується оточення кожної частинки, і для кожного кроку кожної
частинки розраховуються ймовірності її зміщення в напрямку ближчих
клітин. Кожна така ймовірність дорівнює нулю, якщо відповідна клітина в
околі зайнята. Для «вільних» напрямків «проглядається» відстань r та
аналізується кількість зайнятих/доступних клітин.
Насамперед, заборонено переміщатися в зайняті клітини та ті, що мі-
стять перешкоди:
)1()1()4/1( )()( a
ij
a
ijij vfP −−=′ . (1)
Рис. 1. Простір моделі. Чорні кола
— це пішоходи, чорні клітини —
перешкоди; сірі клітини — пошук
у межах околу окремих пішоходів
О.С. Макаренко, Д.А. Крушинський
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 104
Тобто, якщо хоча б одна з величин ijf або
ijv дорівнює одиниці, що означає наявність
пішохода або перешкоди, відповідно, то
ймовірність переходу з клітини ij у напрямку a
дорівнює 0. Для інших напрямків «простежуєт-
ься» окіл на відстань r (параметр моделі):
підраховується кількість клітин, що лежать у
відповідному напрямку та є вільними (від пе-
решкод та інших частинок). Для реалізації цієї
схеми ймовірності ijP ′′ зміщення в напрямку з
багатьма перешкодами зменшують:
)()/1(1)(
*
1
* aPrrfraP ij
r
k
kijij ′
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−+−=′′ ∑
=
+ , (2)
де r — максимальна дальність огляду; *r — відстань від заданої клітини до
найближчої перешкоди в обраному напрямку; )(aPij′ — імовірності, розра-
ховані за формулою (1). Вираз (2) побудовано таким чином: що більша
кількість пішоходів в напрямку a , тобто й більше значення суми ∑
=
+
*
1
r
k
kijf ,
то інтенсивніше зменшується значення ймовірності переходу у цьому напрям-
ку; множник )/1( r забезпечує нормування. З іншого боку, що ближче зна-
чення *r до r (найближча перешкода знаходиться біля межі огляду), то
більш прийнятним є відповідний напрямок і множник при )(aPij′ прямує до 1.
Після цього зростає також імовірність руху в обраному напрямку, на-
приклад N (бажаний напрямок руху вважається попередньо обраним у
кожній клітині та відповідає найкоротшому шляху до певних цільових
клітин):
[ ];)(;)(;)(;)(1min)()( EPWPSPNPbNPNP ijijijijijij ′′′′′′′′−+′′=′
[ ];)(;)(1min)3/()()( SPNPbSPSP ijijijij ′′′′−−′′=
[ ];)(;)(1min)3/()()( EPNPbEPEP ijijijij ′′′′−−′′=
[ ];)(;)(1min)3/()()( WPNPbWPWP ijijijij ′′′′−−′′= (3)
де ]1;0[∈b — параметр, що визначає ступінь бажання дотримуватися
обраного напрямку та приймає значення від 0 (таке бажання відсутнє)
до 1 (обраний напрямок той самий за кожної нагоди). Легко зрозуміти,
що при 0=b вирази (3) тривіально перетворюються на )()( aPaP ijij ′′= , ∈a
},,,,{ CESWN∈ . Натомість ( ]1;0[∈b ) значення йімовірності переходу у
бажаному напрямку збільшується на вказану величину. Рівні частки цієї ж
величини віднімаються від усіх інших імовірностей, щоб забезпечити нор-
мування (∑ =1)(aPij .
N
W C E
S
Рис. 2. Окіл клітини
Моделювання руху пішоходів на основі клітинних автоматів
Системні дослідження та інформаційні технології, 2010, № 1 105
Імовірності (3) розраховуються для кожної клітини в стані 1 (присутня
частинка). Рух частинок із розрахованими для всіх напрямків імовірностями
відбувається одночасно, решітки всіх клітин оновлюються.
Але під час переміщення частинки до вільних позицій не слід ігнорува-
ти обставину, що на ці ж позиції може претендувати від двох до восьми
«кандидатів». У таких випадках виникає конфлікт. Існує тільки один
«чесний» спосіб його розв’язання: обрати одного з кандидатів із однакови-
ми ймовірностями. Якщо швидкість пішохода перевищує 1, для запобігання
складнішим конфліктам (перетин траєкторій руху) кожен часовий крок по-
ділено на півкроки, причому швидкість кожної частинки в межах півкроку
не перевищує 1. Цей метод розв’язання конфліктів є най простішим та най-
ефективнішим.
Той факт, що у випадку околу Мура діагональне переміщення клітини
(через кут клітини) відповідає довшому просторовому кроку, зумовлює
потребу у різній інтерпретації значення швидкості. Наприклад, маючи
найбільшу можливу швидкість 5max =v , пішохід за один крок може зробити
або 5 горизонтальних переміщень (через межу клітини), або 4 діагональні
(через кут клітини).
На цьому опис клітинно-автоматної моделі руху пішоходів завершено.
Таким чином, правила переміщення наступні:
• якщо є можливість, частинка рухається вперед (в іншому, дочасно
заданому напрямку);
• в іншому випадку — частинка зміщується вправо, вліво або по діа-
гоналі;
• наявність інших частинок та стін в будь-якому напрямку зменшує
ймовірність зміщення в цьому напрямку.
Такий набір елементраних правил дозволяє імітувати «розумну» поведінку
людей, що рухаються в групі.
ВРАХУВАННЯ МЕНТАЛЬНОСТІ
Врахування ментальності учасників соціальних процесів (рух пішоходів/
автомобілів) — основна з тенденцій у побудові адекватних моделей та їх
застосуванні. Є декілька шляхів до цього, зокрема, як прості статистичні
правила, так і спроби моделювання людської свідомості та процесів ухва-
лення рішень засобами штучного інтелекту.
Тому основні чинники такі:
• особливості, які бажано враховувати у методології (А);
• підходи до формалізації провідних ідей методологій (В);
• в які моделі вводити ментальність та яким чином? (С).
Передбачувані результати врахування ментальних особливостей — це
якісне розуміння систем та процесів, кількісне моделювання, прогнозуван-
ня, побудова сценаріїв поведінки системи, оптимізація та керування систе-
мами та процесами.
Деякі відповіді можуть бути наступні:
• для A: поведінка, вибір, психологія, досвід з навчання та пам’ять,
інтелект та ін.;
О.С. Макаренко, Д.А. Крушинський
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 106
• для B: формалізація даних, статистика, анкетування, сенсорні дані та
модельні концепції (економетрика, математичне моделювання, ігри та си-
муляції, штучний інтелект, теорія ігор, та ін.;
• для C: диференційні рівняння, статистичний аналіз, мультиагентний
підхід, клітинні автомати тощо.
Раніше, розглядаючи модель із ассоціативною пам’яттю, ми знайшли
чàстковий спосіб та нові перспективи у врахуванні та інтерпретації мента-
льності в моделях великих соціо-економічних систем [12]. Як перший крок
до цього ми пропонуємо застосувати нейромережу Хопфілда для моделю-
вання внутрішньої структури клітин (елементів).
Дещо такий підхід придатний для КА моделей трафіка. Слід також за-
значити, що певні ментальні особливості пішоходів можна реалізувати через
правила навчання у реальному часі шляхом постійного оновлення у нейро-
мережах [13].
Звісно, багато аспектів врахування ментальності потребує представ-
лення у дослідженнях трафіків: моніторинг та розпізнавання ситуацій,
процеси ухвалення рішень щодо напрямку руху, швидкості та цілей;
можливості реалізації руху, когнітивні аспекти, тощо. Сьогодні врахування
ментальності залишається достатньо складною проблемою. Наголосимо, що
такі завдання є також актуальними для інших підходів — мультиагентних
систем [6], master equation, нелінійних моделей.
Але однією з найцікавіших складових у соціальних системах є антиси-
пація. Це здатність людини прорахувати свою поведінку, зважаючи на май-
бутні (прогнозовані) ситуації [14]. Тому подальшу частину статті присвяче-
но запровадженню саме антисипації в рамках описаних вище КА моделей.
МОДЕЛЬ ПІШОХОДА З АНТИСИПАЦІЄЮ
На основі моделі, яку було описано вище, можна представити антисипуючо-
го пішохода, спроможного передбачати розвиток ситуації у своєму безпосе-
редньому околі та застосовувати ці знання для оптимізації певної характе-
ристики натовпу у розглянутих нижче прикладах — часу евакуації.
Як ми зазначили, на кожний крок пішохода розраховуються
ймовірності його зміщення ( kP , 4..1=k у випадку околу фон Неймана),
котрі залежать тільки від поточного розташування перешкод у його безпо-
середньому околі. Саме через ці величини можна ввести антисипацію в мо-
дель. Припустимо, що пішоходи намагаються уникати зіткнень між собою,
тобто пішохід прагне не потрапляти в певну клітину свого околу, якщо у
наступний момент часу вона буде зайнята (відповідно до його прогнозу)
іншим пішоходом. Відповідно до цієї схеми ймовірності можна виправити,
наприклад, наступним чином:
)1( з,kkk PPP ⋅−⋅→ α , (4)
де з,kP — імовірність того, що k -а клітина з околу буде зайнята на наступ-
ному кроці одним із «сусідів». Природно, що величини kP підлягають нор-
муванню, оскільки їхня сума повинна дорівнювати 1 (якщо хоча б одна з
цих імовірностей більше 0). Слід зазначити, що за такого способу реалізації
Моделювання руху пішоходів на основі клітинних автоматів
Системні дослідження та інформаційні технології, 2010, № 1 107
антисипації усі пішоходи є рівноправними і при 1=α може виникнути си-
туація, коли два пішоходи, намагаючись пропустити один одного, зали-
шаться нерухомими і будуть заважати руху всього натовпу. Уникнути цього
можливо, лише обираючи значення параметра меншими за 1, та кількість
таких блокувань можна зменшити через надання одним пішоходам переваг
перед іншими. Найефективніший шлях у цьому напрямку — надання пере-
ваги більш рухливим пішоходам. Тобто ймовірності зміщення будуть мати
наступний запис:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−−→ з,
max
11 kkk P
v
vPP α . (5)
За такої поправки найбільш рухливі учасники ( maxvv = ) нікого не про-
пускають, однак їх можна зробити більш «ввічливими», якщо підставити в
(5) замість maxv дещо більше значення.
Як було наголошено, антисипація залежить від спроможності прогно-
зувати стан системи. Тому залишається нез’ясованою проблема про методи
побудови пішоходами прогнозу, а саме — обчислення ймовірностей з,kP .
Було розглянуто два варіанти. Перший — прогнозування, що засноване на
спостереженнях, яке грунтується на гіпотезі про збереження пішоходами
напрямку свого руху: «іду, куди дивлюсь, дивлюсь, куди йду». При цьому
з,kP можна вважати пропорційною кількості пішоходів, що рухаються («ди-
вляться») в бік k-ї клітини:
M
mP зk =, , (6)
де m — кількість пішоходів, що прямують в k -у клітину; =M <кількість
клітин в околі> 1− , у даному випадку 3=M .
Цей метод є найпростішим і водночас найменш точним, оскільки прий-
нятність гіпотези про збереження напрямку руху суттєво залежить від гео-
метричних особливостей конкретної задачі (плану приміщення, тощо). Тому
було розглянуто другий метод — прогнозування, яке засноване на моделі
пішохода. В цьому випадку кожен учасник руху для кожної клітини зі свого
околу обчислює kP її «сусідів» (крім себе самого). Віднайдена ймовірність
має вигляд:
∏∑∑∑∑∑
=≠=≠≠≠=
+−=+−=
3
1
3
1,
3
1
,
i
ij
ji
i
i
i
kjji
kjij
ji
i
i
iзk PPPPPPPPPPP . (7)
Ця формула є реалізацією ймовірнісної схеми перебору варіантів по-
трапляння у клітину одного з трьох «сусідів»: 1-й або (не 1-й та (2-й або (не
2-й та 3-й))). Відповідно, після розкриття дужок утворюється вираз, подіб-
ний до (7). Отже, цей підхід забезпечує точніше визначення з,kP , хоча є де-
що штучним, оскільки для його реалізації кожен учасник руху повинен зна-
ти модель поведінки своїх «сусідів», що накладає певні обмеження на
гнучкість всієї КА моделі.
З усіма варіантами моделі пішохода, що були описані вище, проведено
багато експериментів, результати яких підводять до висновку про адек-
ватність запропонованих підходів. На рис. 3 наведено чотири криві, що
О.С. Макаренко, Д.А. Крушинський
ISSN 1681–6048 System Research & Information Technologies, 2010, № 1 108
відповідають можливим комбінаціям підходів до запровадження антисипації
та методів обчислення прогнозованих значень з,kP . Криві перетинаються в
точці 0=α , оскільки таке значення параметра відповідає простій неантиси-
паційній моделі.
Зокрема, наведений графік свідчить, що надання переваги швидким пі-
шоходам призводить до збільшення часу евакуації, тому не є прийнятним.
З іншого боку, що точніше розраховуються поправки у kP (нижня крива на
рис. 3), то швидше відбувається евакуація, а це підтверджує адекватність
самого підходу до запровадження антисипації у модель. Також нижня крива,
що стрімко зростає в околі 1=α , демонструє описаний ефект, коли пішохо-
ди, намагаючись пропустити один одного, залишаються нерухомими і галь-
мують рух усього натовпу.
ВИСНОВКИ
Клітинні автомати є потужним засобом моделювання систем із багатьма
складовими, зокрема натовпів пішоходів, що рухаються. Перевагою КА
підходу є його виняткова ефективність при реалізації (як програмній, так і
апаратній), що зумовлена локальністю усіх взаємодій. Таким чином, один
крок моделі має лінійну часову складність залежно від розміру системи
(кількості пішоходів).
Крім того, такий підхід є достатньо гнучким, бо дозволяє моделю-
вати рух невизначеної кількості пішоходів у середовищі з геометрією
довільної складності (будь-якому розташуванні перешкод). При цьому,
співвідношення, на які покладена динаміка пішохода, є достатньо простими
та інтуїтивно зрозумілими. Водночас простота базових правил переміщення
не обмежує здатність моделі відтворювати всі можливі явища.
Але, незважаючи на те, що навіть прості правила дають підстави якісно
моделювати практично усі явища, що виникають у реальних натовпах, існує
суттєвий розрив між кількісними даними моделі та результатими вимірів
показників реальних натовпів пішоходів. Тому є потреба в реалістичніших
правилах, що враховують ментальні особливості учасників руху. Вище було
Рис. 3. Результати експериментів (Е/Р — рівноправність/перевага швидких; О/М —
передбачення, що базується на спостереженнях/моделі)
Моделювання руху пішоходів на основі клітинних автоматів
Системні дослідження та інформаційні технології, 2010, № 1 109
зроблено спробу (як показали результати експериментів — вдалу) запрова-
дити антисипацію у КА модель. Проте, в цьому дослідженні антисипацію
було використано досить обмежено тому, що пішохід взяв до уваги інфор-
мацію лише про окіл радіуса в дві клітини і робив прогноз тільки на один
крок у часі. Отже, у подальшому доцільно залучати універсальніші методи
запровадження антисипації у КА моделі, які б дозволили відображати різ-
ний ступінь поінформованості пішоходів (наявність у них інформації про
окіл довільного радіуса) та висувати прогнози з довільним горизонтом (що
призведе до появи багатозначності і дасть змогу реальним чином ввести у
модель процеси ухвалення рішень). Також можливе запровадження антиси-
паційних механізмів у КА моделі інших систем.
Роботу частково профінансовано грантом Ф25/210-2008 ДФФД України.
ЛІТЕРАТУРА
1. Chowdhury D., Santen L., Schadschneider A. Statistical physics of vehicular traffic
and some related systems // Physics Reports Issues. — 2000. — 329, № 4–6. —
P. 199–329.
2. Shreckenberg M., Sharma S.D. (eds.) Pedestrian and Evacuation Dynamics. — Ber-
lin: Springer, 2001. — P. 123–154.
3. Helbing D., Molnar P. Social force model for pedestrian dynamics // Physical
Review. — 1995. — 51. — P. 4282–4286.
4. Helbing D., Farkas I.J., Vicsek T. Simulating Dynamical Features of Escape Panic //
Nature. — 2000. — 407. — P. 487–490.
5. Wolfram S. A new kind of science. — Champaign, IL, USA: Wolfram Media Inc.,
2002. — 1280 p.
6. Gilbert N. and Troitzsch K. Simulation for the social scientist. — Milton
Keynes, UK: Open University press. — 1999. — P. 130–169.
7. Тоффоли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. — М.:
Мир, 1991. — 278 с.
8. Gardner M. The fantastic combinatika of John Conway’s new solitaire game «Life»
// Scientific American. — 1970. — 223, № 4. — P. 120–123.
9. Chopard B., Droz M. Cellular Automata Modeling of Physical Systems. Cambridge
University Press. — 1998. — 341 p.
10. Nagel K., Schreckenberg M. A cellular automaton model for freeway traffic // Jour-
nal de Physique I. — 1992. — 2, № 12. — P. 2221–2229.
11. Goldengorin B., Makarenko A., Smilianec N. Some applications and prospects of cel-
lular automata in traffic problems / In: El Yacoubi S., Chopard B., Bandini S. (eds.)
ACRI 2006. LNCS. — Springer, Heidelberg. — 2006. — 4173. — P. 532–537.
12. Makarenko A. Anticipating in modeling of large social systems - neuronets with
internal structure and multivaluedness // International Journal of Computing
Anticipatory Systems. — 2002. — 13. — P. 77–92.
13. Krushinsky D., Makarenko A. Context-dependent Hopfield-like network / Second
International Scientific Conference «Intelligent Decision-Making Systems and
Applied Aspects of Information Technologies» (ISDMIT 2006). — 2006. —
2. — P. 229–232.
14. Макаренко А.С. Модели общественных явлений и сценарные подходы в при-
нятии решений // Системні дослідження та інформаційні технології. —
2003. — № 3. — С. 127–142.
Received 13.11.2008
|