Моделюва́ння типу скупчення — це процес моделювання руху (або динаміки) великої кількості об'єктів або символів. Він широко використовується для створення віртуальних сцен для візуальних носіїв, таких як фільми та відеоігри, а також використовується в кризовій підготовці,http://cc.ist.psu.edu/BRIMS/archives/2007/papers/07-BRIMS-025.pdf Jérôme Comptdaer, Emmanuel Chiva, Stéphane Delorme, Henri Morlaye, Jérôme Volpoët, Multi-scale behavioral models for urban crisis training simulation. архітектурі та містобудуванні, для моделювання евакуації.
Моделювання натовпу може бути зосереджено на аспектах, призначених для різних додатків. Для реалістичного і швидкого зображення натовпу у візуальних медіа або віртуальному кінематографі використовуються зменшення складності 3D-сцени і рендеринг на основі зображень, в той час як зміни зовнішнього вигляду допомагають уявити реалістичну популяцію.
В іграх і додатках, призначених для відтворення реалістичного руху людського натовпу, як при моделюванні евакуації, імітовані агенти повинні переміщатися до мети, уникати зіткнень і демонструвати іншу людиноподібну поведінку. Багато алгоритмів управління натовпом були розроблені щоб привести імітований натовп до своєї мети реалістично. Досліджено деякі більш загальні системи, які можуть підтримувати різні типи агентів (наприклад, автомобілі та пішоходи), різні рівні абстракції (такі як індивідуальний і континуум), агенти взаємодіють зі смарт-об'єктами, а також більш складною фізичною та соціальною динамікою.http://dl.acm.org/citation.cfm?id=1272705 Pelechano, N. and Allbeck, J. M. and Badler, N. I. Controlling individual agents in high-density crowd simulation. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. ISBN 978-1-59593-624-0
Історія Завжди був глибокий інтерес до розуміння і отримання контролю за рухом і поведінкою натовпу людей. Багато великих досягнень відбулося з моменту початку досліджень в області моделювання натовпу. Очевидно, що після цього постійно публікуються і публікуються численні нові дані, які покращують масштабованість, гнучкість, можливість застосування і реалістичність моделювання:
У 1987 році, поведінкова анімація була введена і розроблена Крейгом Рейнольдсом. Він змоделював зграї птахів поруч косяків риб з метою вивчення групової інтуїції і руху. Всі агенти в рамках цих імітацій отримали прямий доступ до відповідних позицій і швидкостей оточуючих їх агентів. Теоретизування і вивчення спонукане Рейнольдсом було вдосконалено і побудовано в 1994 р. Ксяоюн Тю, Деметрою Терзопулос і Радеком Гжежчуком. Реалістична якість моделювання була пов'язана з тим, що окремі агенти були оснащені синтетичним баченням і загальним видом середовища, в якому вони проживали, дозволяючи сприймати інформацію в їх динамічних середовищах існування.
Початкові дослідження в області моделювання натовпу почалися в 1997 році під наглядом Даніеля Тальманна над дисертацією доктора Сорайя Рауппом Мусса. Ці двоє представляють нову модель поведінки натовпу, щоб створити симуляцію загальних популяцій. Тут робиться зв'язок між автономною поведінкою індивіда в натовпі і поведінкою, що виникає з цього.
У 1999 р. індивідуалістична навігація розпочала свій шлях в області моделювання натовпу за допомогою тривалого дослідження Крейга Рейнольдса. Кермова поведінка, як доводять, грає велику роль в процесі автоматизації агентів симуляції. Рейнольдс стверджує, що процеси низького рівня пересування залежать від середнього рівня кермової поведінки і цільових станів і шляхів пошуку стратегій вищого рівня. Споглядаючи передову роботу Рейнольдса, Сора Раупп Мусса і Даніель Тельманн почали вивчати моделювання імітацій в реальному часі цих натовпів та їх застосування до поведінки людини. Контроль натовпу людей визначався як ієрархічна організація з рівнем автономії серед агентів. Це знаменує початок моделювання індивідуальної поведінки в його елементарній формі на гуманоїдних агентах.
Збігаючись з публікаціями по моделях поведінки людини і симуляторах групової поведінки, пропозиція Метта Андерсона, Еріка МакДеніела і Стівена Ченні про обмеження поведінки набули популярності. Було показано, що позиціювання обмежень групової анімації можливо в будь-який час в рамках симуляції. Цей процес застосування обмежень до поведінкової моделі зазнає головним чином, спочатку визначаючи вихідний набір цільових траєкторій, які збігаються з обмеженнями, а потім застосовуючи до них ці правила поведінки, щоб вибрати ті, які їх не порушують.
Кореляція і побудова висновків, запропонованих в його роботі з Сорайя Раупп Муссом, Даніель Тальманн, який працював разом з Братиславою Уличною і Пабло де Херасом Цехомські, запропонували нову модель, яка дозволяла інтерактивно створювати агентів на рівні окремої людини, групи Агентів і всього натовпу. Метафора кисті вводиться для поширення, моделювання та управління учасниками натовпу в режимі реального часу з негайним зворотним зв'язком.
Динаміка натовпу Однією з основних цілей моделювання натовпу є реалістичне управління натовпами і відтворення динамічних моделей людської поведінки.
Існує кілька всеосяжних підходів до моделювання натовпу і штучного інтелекту, кожен з яких має переваги і недоліки, засновані на розмірі натовпу і масштабі часу. Шкала часу ставиться до того, щоб мета моделювання також впливала на тривалість моделювання. Наприклад, дослідження соціальних питань, таких як поширення ідеології серед населення, призведе до набагато більш тривалої симуляції, оскільки така подія може охоплювати місяці або роки. Використовуючи ці дві характеристики, дослідники спробували застосувати класифікації, щоб краще оцінити і організувати існуючі симулятори натовпу.
Потоковий підхід Моделювання натовпу на основі потоку орієнтоване на натовп в цілому, а не її компоненти. Оскільки такі індивідууми не мають будь-яких відмітних форм поведінки, які відбуваються через вклад їх оточення, а поведінкові фактори в значній мірі зменшуються. Ця модель в основному використовується для оцінки руху великого і щільного натовпу в даному середовищі. Найкраще використовувати у вивченні великого натовпу короткі цілі часу.
Сутнісний підхід Моделі, які реалізують набір фізичних, зумовлених і глобальних законів, призначених для імітації соціальних/психологічних факторів, які відбуваються у людей, які є частиною натовпу, підпадають під цю категорію. Суб'єкти в цьому випадку не здатні, в певному сенсі, думати самі за себе. Всі рухи визначаються глобальними законами, які нав'язуються їм. Симуляції, які використовують цю модель, часто роблять так, щоб дослідити динаміку натовпу, таку як глушіння і стікання. Мало-середні натовпу з короткостроковими цілями найкраще підходять для цього підходу.
Агентський підхід Характеризується автономними, взаємодіючими індивідуумами. Кожному агенту натовпу при такому підході дається певна ступінь інтелекту; Вони можуть реагувати на кожну ситуацію самостійно, ґрунтуючись на наборі правил прийняття рішень. Інформація, яка використовується для прийняття рішення про дію, виходить локально з середовища агента. Найчастіше цей підхід використовується для моделювання реалістичного поведінки натовпу, оскільки досліднику надається повна свобода для реалізації будь-якої поведінки.
Системи частинок Один із способів імітації віртуальної натовпу - використовувати систему частинок. Системи частинок вперше були введені в комп'ютерну графіку В. Т. Рівзом в 1983 році. Система частинок являє собою сукупність ряду окремих елементів або часток. Кожна частинка здатна діяти автономно і їй присвоюється набір фізичних атрибутів (таких як колір, розмір і швидкість).
Система частинок є динамічною, оскільки руху частинок змінюються з плином часу. Рух системи частинок - ось що робить його таким бажаним і легким у реалізації. Обчислення рухів цих частинок займає дуже мало часу. Він просто включає фізику:сума всіх сил, що діють на частку, визначає її рух. Сили, такі як гравітація, тертя і сила від зіткнення, і соціальні сили, такі як сила тяжіння мети.
Зазвичай кожна частка має вектор швидкості і вектор положення, що містить інформацію про поточну швидкість і положення частинки відповідно. Обчислення наступного положення частинок виробляється шляхом підсумовування вектора швидкості з його вектором положення. Дуже проста операція (знову ж таки, чому системи частинок так бажані). Його вектор швидкості змінюється з часом у відповідь на сили, що діють на частинку. Наприклад, зіткнення з іншого часткою призведе до зміни напрямку.
Системи частинок широко використовувалися у фільмах для таких ефектів, як вибухи, ефекти води у фільмі 2000 року «Ідеальний шторм» і імітація газу в фільмі «Маска» 1994 року.
Однак системи частинок мають деякі недоліки. Це може бути поганою ідеєю використовувати систему частинок, щоб імітувати агентів в натовпі, і директор рухатиметься по команді, визначаючи, які частки належать агенту, а які ні.
Алгоритм Патіла і Ван Ден Берга Цей алгоритм був розроблений для спрощених натовпів, де кожен агент в натовпі хоче тільки дістатися до своєї мети, а також уникати перешкод. Цей алгоритм може бути використаний для імітації натовпу на Таймс-сквер.
Найбільш важливою і відмітною особливістю алгоритму Патілса є те, що він використовує концепцію навігаційних полів для направлення агентів. Це відрізняється від області керівництва; Поле керівництва є область навколо агента, в якій агент здатний «бачити»/виявляти інформацію. Області інструкцій зазвичай використовуються для запобігання перешкод, динамічних перешкод (зокрема, перешкод). Кожен агент має власний полем для керівництва. З іншого боку, навігаційне поле являє собою векторне поле, яке обчислює шлях мінімальної вартості для кожного агента, щоб кожен агент прибув в свою власну цільову позицію.
Поле навігації можна використовувати тільки правильно, коли існує шлях від кожного вільного (не перешкоджає) положення в середовищі до однієї з позицій мети. Навігаційній обчислюється з використанням координат статичних об'єктів в середовищі, цільових позицій для кожного агента і поля керівництва для кожного агента. Щоб гарантувати, що кожен агент досягає своєї мети, навігаційній має бути позбавлене локальних мінімумів, за винятком наявності приймачів в зазначених цілях.
Час обчислення поля навігації , де m × n - розмір сітки (по аналогії з алгоритмом Дейкстра). Таким чином, алгоритм залежить тільки від дозволу сітки і не залежить від кількості агентів в середовищі. Однак цей алгоритм має високу вартість пам'яті.
Моделювання індивідуальної поведінки Один з методів моделювання імітації натовпу на основі II складається в моделюванні поведінки натовпу шляхом вдосконаленого моделювання індивідуальних чинників мотивації і прийняття рішень. Як правило, це означає, що кожному агенту присвоюється певний набір змінних, які вимірюють різні риси або стану, такі як стрес, особистість або різні цілі. Це призводить до більш реалістичного поведінки натовпу, хоча може бути більш обчислювальним, ніж більш прості методи.
Моделі, засновані на особистості Один із способів створення індивідуалістичного поведінки для агентів натовпу - це використання особистісних якостей. Кожен агент може мати певні аспекти їх особистості, налаштовані на основі формули, яка пов'язує такі аспекти, як агресивність або імпульсивність зі змінними, які визначають поведінку агентів.Одним із способів виявлення зв'язку з цим є суб'єктивне дослідження, при якому агентам випадковим чином присвоюються значення для цих змінних, і учасникам пропонується описати кожного агента з точки зору цих особистісних якостей. Потім може бути зроблена регресія для визначення кореляції між цими ознаками і змінними агента. Потім характеристики особистості можуть бути налаштовані і відповідним чином впливають на поведінку агентів.