Флокирование

Стая — это поведение, проявляющееся, когда группа птиц, называемая стаей , ищет пищу или летит. Овцы и козы также демонстрируют стадное поведение.

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

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

На природе

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

Поведение стайки было смоделировано на компьютере в 1987 году Крейгом Рейнольдсом с помощью его программы моделирования Boids . ^[2] Эта программа имитирует простых агентов (боидов), которым разрешено передвигаться в соответствии с набором основных правил. подобен стае птиц , косяку рыб или рою насекомых . Результат

Измерение

Проведены замеры стай птиц. ^[3] с использованием высокоскоростных камер и компьютерного анализа для проверки простых правил флокирования, упомянутых ниже. Установлено, что они в целом справедливы в случае стайки птиц, однако правило дальнего притяжения (сплоченности) применимо к ближайшим 5–10 соседям стайной птицы и не зависит от расстояния этих соседей от птицы. Кроме того, существует анизотропия в отношении этой тенденции к сплочению: большая сплоченность проявляется по отношению к соседям по бокам птицы, а не спереди или сзади. Вероятно, это связано с тем, что поле зрения летящей птицы направлено в стороны, а не прямо вперед или назад.

Другое недавнее исследование основано на анализе записей стад высокоскоростной камеры над Римом и использует компьютерную модель, предполагающую минимальные правила поведения. ^[4]^[5]^[6]^[7]

Алгоритм

Правила

Базовые модели стайного поведения контролируются тремя простыми правилами:

Разделение: Избегайте скопления соседей (отталкивание на близком расстоянии)
Выравнивание: Держитесь в сторону среднего направления соседей
Сплоченность: Держитесь ближе к среднему положению соседей (притяжение на большие расстояния)

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

Варианты правил

Базовая модель была расширена несколькими способами с тех пор, как ее предложил Рейнольдс. Например, Дельгадо-Мата и др. ^[8] расширил базовую модель, включив в нее эффекты страха. Обоняние использовалось для передачи эмоций между животными посредством феромонов, смоделированных как частицы в свободно расширяющемся газе.

Хартман и Бенеш ^[9] ввели дополнительную силу в расстановку сил, которую они называют сменой руководства. Этот поворот определяет шанс птицы стать лидером и попытаться убежать.

Хемельрейк и Хильденбрандт ^[10] использовали привлечение, выравнивание и избегание и расширили это за счет ряда черт настоящих скворцов:

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

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

Сложность

При моделировании флокирования нет централизованного управления; каждая птица ведет себя автономно. Другими словами, каждая птица должна сама решить, какие стаи считать ее средой обитания. Обычно среда определяется как круг (2D) или сфера (3D) с определенным радиусом (обозначающим охват). ^{[ нужна ссылка ]}

Базовая реализация алгоритма флокирования имеет сложность. $O(n^{2})$ – каждая птица перебирает всех других птиц, чтобы найти тех, которые попадают в ее среду обитания. ^{[ неправильный синтез? ]}

Возможные улучшения: ^{[ нужна ссылка ]}

бин- решеточное пространственное подразделение. Вся территория, по которой может перемещаться стадо, разделена на несколько бункеров. В каждой ячейке хранится информация о том, какие птицы в ней содержатся. Каждый раз, когда птица перемещается из одного контейнера в другой, решетку необходимо обновлять.
- Пример: 2D(3D) сетка в 2D(3D) моделировании флокирования.
- Сложность: $O(nk)$ , k — количество окружающих ячеек, которые следует учитывать; как раз тогда, когда находят птичий ящик $O(1)$

Ли Спектор, Джон Кляйн, Крис Перри и Марк Файнштейн изучали возникновение коллективного поведения в эволюционных вычислительных системах. ^[11]

Бернар Шазель доказал, что при предположении, что каждая птица подстраивает свою скорость и положение под других птиц в пределах фиксированного радиуса, время, необходимое для достижения устойчивого состояния, представляет собой итерированную экспоненту логарифмической высоты от количества птиц. Это означает, что если число птиц достаточно велико, время сближения будет настолько велико, что с таким же успехом могло бы быть бесконечным. ^[12] Этот результат применим только к сходимости к установившемуся состоянию. Например, стрелы, выпущенные в воздух на краю стаи, заставят всю стаю реагировать быстрее, чем можно объяснить взаимодействием с соседями, которое замедляется из-за временной задержки в центральной нервной системе птицы - от птицы к соседям. -птица-птица.

Приложения

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

В Кёльне, Германия, два биолога из Университета Лидса продемонстрировали у людей стадное поведение. Группа людей демонстрировала модель поведения, очень похожую на модель поведения стаи: если 5% стаи изменят направление, остальные последуют ее примеру. Когда одного человека называли хищником, а все остальные должны были его избегать, стая вела себя очень похоже на косяк рыб. ^[13]

Флокирование также рассматривается как средство контроля поведения беспилотных летательных аппаратов (БПЛА). ^[14]

Флокирование — распространенная технология в заставках и нашла свое применение в анимации. Флокирование использовалось во многих фильмах. ^[15] для создания толп, которые двигаются более реалистично. В фильме Тима Бертона « Возвращение Бэтмена» (1992) были показаны стайки летучих мышей. ^{[ неправильный синтез? ]}

Поведение стекания использовалось и для других интересных приложений. Он был применен для автоматического программирования многоканальных интернет-радиостанций. ^[16]Его также использовали для визуализации информации. ^[17]и для задач оптимизации. ^[18]

См. также

Толпа
Пелотон (дорожные велосипедные гонки)

Ссылки

^ О'Лоан, О.Дж.; Эванс, MR (1999). «Переменное устойчивое состояние при одномерном флокинге». Журнал физики A: Математический и общий . 32 (8). Издательство ИОП: L99. arXiv : cond-mat/9811336 . Бибкод : 1999JPhA...32L..99O . дои : 10.1088/0305-4470/32/8/002 . S2CID 7642063 .
^ Рейнольдс, Крейг В. (1987). «Стада, стада и школы: распределенная поведенческая модель». ACM SIGGRAPH Компьютерная графика . Том. 21. С. 25–34.
^ Федер, Тони (октябрь 2007 г.). «Статистическая физика – для птиц» . Физика сегодня . 60 (10): 28–30. Бибкод : 2007PhT....60j..28F . дои : 10.1063/1.2800090 .
^ Хильденбрандт, Х; Карере, К; Хемельрейк, СК (2010). «Самоорганизованные воздушные демонстрации тысяч скворцов: модель» . Поведенческая экология . 21 (6): 1349–1359. arXiv : 0908.2677 . дои : 10.1093/beheco/arq149 .
^ Хемельрейк, СК; Хильденбрандт, Х (2011). «Некоторые причины изменчивой формы стай птиц» . ПЛОС ОДИН . 6 (8): e22479. Бибкод : 2011PLoSO...622479H . дои : 10.1371/journal.pone.0022479 . ПМК 3150374 . ПМИД 21829627 .
^ Проект Звездный флаг
^ Модель поведения роя, разработанная Гронингенским университетом.
^ Дельгадо-Мата С., Ибанез Дж., Би С. и др. (2007). «Об использовании виртуальных животных с искусственным страхом в виртуальной среде». Компьютеры нового поколения . 25 (2): 145–169. дои : 10.1007/s00354-007-0009-5 . S2CID 26078361 .
^ Хартман С., Бенеш Б. (2006). «Автономные боиды». Компьютерная анимация и виртуальные миры . 17 (3–4): 199–206. дои : 10.1002/cav.123 . S2CID 15720643 .
^ Хемельрейк, СК; Хильденбрандт, Х. (2011). «Некоторые причины изменчивой формы стай птиц» . ПЛОС ОДИН . 6 (8): e22479. Бибкод : 2011PLoSO...622479H . дои : 10.1371/journal.pone.0022479 . ПМК 3150374 . ПМИД 21829627 .
^ Спектор, Л.; Кляйн, Дж.; Перри, К.; Файнштейн, М. (2003). «Появление коллективного поведения в развивающихся популяциях летающих агентов» . Материалы конференции по генетическим и эволюционным вычислениям (GECCO-2003) . Спрингер-Верлаг . Проверено 1 мая 2007 г.
^ Бернар Шазель, Конвергенция птичьих стай , J. ACM 61 (2014)
^ " http://psychcentral.com/news/2008/02/15/herd-mentality-explained/1922.html. Архивировано 29 ноября 2014 г. в Wayback Machine ". Проверено 31 октября 2008 года.
^ Сенанаяке М., Сентуран И., Барка Дж. К., Чанг Х., Камруззаман Дж. и Муршед М. «Алгоритмы поиска и отслеживания стай роботов: обзор».
^ Габбай, JME (2005). Сложность и аэрокосмическая промышленность: понимание возникновения путем связи структуры с производительностью с использованием мультиагентных систем (Диссертация). Манчестер: Докторская диссертация Манчестерского университета. Архивировано из оригинала 19 декабря 2014 г. Проверено 21 февраля 2007 г.
^ Ибанез Дж., Гомес-Скармета А.Ф., Блат Дж. (2003). «Ди-джеи: возникающее коллективное поведение как программирование многоканальных радиостанций». Материалы 8-й международной конференции по интеллектуальным пользовательским интерфейсам . стр. 248–250. дои : 10.1145/604045.604089 .
^ Моере А.В. (2004). «Визуализация изменяющихся во времени данных с использованием механизмов скопления информации» (PDF) . Материалы симпозиума IEEE по визуализации информации . стр. 97–104. дои : 10.1109/INFVIS.2004.65 . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Цуй З, Ши З (2009). «Оптимизация роя частиц Boid». Международный журнал инновационных вычислений и приложений . 2 (2): 77–85. дои : 10.1504/IJICA.2009.031778 .

Источники

Буффанае, Роланд (2016). Проектирование и управление динамикой роя . SpringerBriefs в сложности. Спрингер Сингапур. дои : 10.1007/978-981-287-751-2 . ISBN 9789812877505 .
Какер, Фелипе; Стив Смейл (2007). «Математика возникновения» (PDF) . Японский математический журнал . 2 : 197–227. дои : 10.1007/s11537-007-0647-x . S2CID 2637067 . Проверено 9 июня 2008 г.
Шен, Джеки (Цзяньхун) (2008). «Стая Кукера-Смейла под иерархическим руководством» . СИАМ J. Appl. Математика . 68 (3): 694–719. arXiv : q-bio/0610048 . дои : 10.1137/060673254 . S2CID 14655317 . Проверено 9 июня 2008 г.
Хорошо, БТ; Д.А. Шелл (2013). «Объединение микроскопических моделей стайного движения для виртуальных, роботизированных и биологических членов стаи». Автон. Роботы . 35 (2–3): 195–219. дои : 10.1007/s10514-013-9338-z . S2CID 14091388 .
Васархейи, Г.; К. Вираг; Г. Печали; Т. Непус; А.Э. Эйбен; Т. Вичек (2018). «Оптимизированное скопление автономных дронов в ограниченном пространстве» . Научная робототехника . 3 (20) (опубликовано 18 июля 2018): eaat3536. doi : 10.1126/scirobotics.aat3536 . hdl : 1871.1/87dd0889-cb66-4699-a27b-fc34f75e9b6d . ПМИД 33141727 .

Внешние ссылки

[1] О'Лоан, О.Дж.; Эванс, MR (1999). «Переменное устойчивое состояние при одномерном флокинге». Журнал физики A: Математический и общий . 32 (8). Издательство ИОП: L99. arXiv : cond-mat/9811336 . Бибкод : 1999JPhA...32L..99O . дои : 10.1088/0305-4470/32/8/002 . S2CID 7642063 .

[2] Рейнольдс, Крейг В. (1987). «Стада, стада и школы: распределенная поведенческая модель». ACM SIGGRAPH Компьютерная графика . Том. 21. С. 25–34.

[3] Федер, Тони (октябрь 2007 г.). «Статистическая физика – для птиц» . Физика сегодня . 60 (10): 28–30. Бибкод : 2007PhT....60j..28F . дои : 10.1063/1.2800090 .

[4] Хильденбрандт, Х; Карере, К; Хемельрейк, СК (2010). «Самоорганизованные воздушные демонстрации тысяч скворцов: модель» . Поведенческая экология . 21 (6): 1349–1359. arXiv : 0908.2677 . дои : 10.1093/beheco/arq149 .

[5] Хемельрейк, СК; Хильденбрандт, Х (2011). «Некоторые причины изменчивой формы стай птиц» . ПЛОС ОДИН . 6 (8): e22479. Бибкод : 2011PLoSO...622479H . дои : 10.1371/journal.pone.0022479 . ПМК 3150374 . ПМИД 21829627 .

[6] Проект Звездный флаг

[7] Модель поведения роя, разработанная Гронингенским университетом.

[8] Дельгадо-Мата С., Ибанез Дж., Би С. и др. (2007). «Об использовании виртуальных животных с искусственным страхом в виртуальной среде». Компьютеры нового поколения . 25 (2): 145–169. дои : 10.1007/s00354-007-0009-5 . S2CID 26078361 .

[9] Хартман С., Бенеш Б. (2006). «Автономные боиды». Компьютерная анимация и виртуальные миры . 17 (3–4): 199–206. дои : 10.1002/cav.123 . S2CID 15720643 .

[10] Хемельрейк, СК; Хильденбрандт, Х. (2011). «Некоторые причины изменчивой формы стай птиц» . ПЛОС ОДИН . 6 (8): e22479. Бибкод : 2011PLoSO...622479H . дои : 10.1371/journal.pone.0022479 . ПМК 3150374 . ПМИД 21829627 .

[11] Спектор, Л.; Кляйн, Дж.; Перри, К.; Файнштейн, М. (2003). «Появление коллективного поведения в развивающихся популяциях летающих агентов» . Материалы конференции по генетическим и эволюционным вычислениям (GECCO-2003) . Спрингер-Верлаг . Проверено 1 мая 2007 г.

[12] Бернар Шазель, Конвергенция птичьих стай , J. ACM 61 (2014)

[13] " http://psychcentral.com/news/2008/02/15/herd-mentality-explained/1922.html. Архивировано 29 ноября 2014 г. в Wayback Machine ". Проверено 31 октября 2008 года.

[14] Сенанаяке М., Сентуран И., Барка Дж. К., Чанг Х., Камруззаман Дж. и Муршед М. «Алгоритмы поиска и отслеживания стай роботов: обзор».

[15] Габбай, JME (2005). Сложность и аэрокосмическая промышленность: понимание возникновения путем связи структуры с производительностью с использованием мультиагентных систем (Диссертация). Манчестер: Докторская диссертация Манчестерского университета. Архивировано из оригинала 19 декабря 2014 г. Проверено 21 февраля 2007 г.

[16] Ибанез Дж., Гомес-Скармета А.Ф., Блат Дж. (2003). «Ди-джеи: возникающее коллективное поведение как программирование многоканальных радиостанций». Материалы 8-й международной конференции по интеллектуальным пользовательским интерфейсам . стр. 248–250. дои : 10.1145/604045.604089 .

[17] Моере А.В. (2004). «Визуализация изменяющихся во времени данных с использованием механизмов скопления информации» (PDF) . Материалы симпозиума IEEE по визуализации информации . стр. 97–104. дои : 10.1109/INFVIS.2004.65 . Архивировано (PDF) из оригинала 9 октября 2022 г.

[18] Цуй З, Ши З (2009). «Оптимизация роя частиц Boid». Международный журнал инновационных вычислений и приложений . 2 (2): 77–85. дои : 10.1504/IJICA.2009.031778 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v т и Роение
Биологическое роение	Агентная модель в биологии Коллективное поведение животных Вождение Стадо стекание сортировать солнце Стадо стадное поведение Саранча Смешанное кормовое стадо Моббинговое поведение кормление безумия Пакет вьючный охотник Закономерности самоорганизации у муравьев муравейник нарушение симметрии убегающих муравьев Мелководье и школьное обучение приманка мяч Роевое поведение Роение (медоносная пчела) Роящаяся подвижность
Миграция животных	Миграция животных высотный отслеживание история кодированная бирка на проводе Миграция птиц пролетные пути обратная миграция Миграция клеток Миграция рыб вертикальный диель Лессепсианский лосось сардины Возвращение домой рождение филопатрия Миграция насекомых бабочки монарх Миграция морских черепах
Роевые алгоритмы	Агентные модели Оптимизация колонии муравьев Боиды Моделирование толпы Оптимизация роя частиц Роевой интеллект Рой (симуляция)
Коллективное движение	Активная материя Коллективное движение Самодвижущиеся частицы кластеризация Модель шуток БИО-LGCA
Роевая робототехника	Муравьиная робототехника Микроботика Наноробототехника Роевая робототехника Симбрион
Связанные темы	Эффект Аллеи Навигация по животным Коллективный разум Децентрализованная система Эусоциальность Меры размера группы Микробный интеллект мутуализм Пресыщение хищника Определение кворума Пространственная организация Стигмергия Военное скопление Распределение задач и разделение социальных насекомых