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

Стая птиц во время полета или поиска пищи

Две стаи серых журавлей

Стая скворцов, похожая на рой

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

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

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

В природе

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

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

Измерение

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

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

Алгоритм

Правила

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

Разделение

Избегайте скопления соседей (отталкивание на коротком расстоянии)

Выравнивание

Направляйтесь в сторону среднего направления движения соседей

Сплоченность

Направляйтесь к среднему положению соседей (притяжение на большом расстоянии)

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

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

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

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

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

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

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

Сложность

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

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

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

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

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

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

Приложения

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

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

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

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

Смотрите также

• Толпа
• Пелотон (шоссейные велогонки)

Ссылки

1. O'Loan, OJ; Evans, MR (1999). "Переменное устойчивое состояние в одномерном скоплении". Journal of Physics A: Mathematical and General . 32 (8). IOP Publishing: L99. arXiv : cond-mat/9811336 . Bibcode : 1999JPhA...32L..99O. doi : 10.1088/0305-4470/32/8/002. S2CID  7642063.
2. Рейнольдс, Крейг В. (1987). «Стада, стада и косяки: распределенная поведенческая модель». ACM SIGGRAPH Computer Graphics . Том 21. С. 25–34.
3. Федер, Тони (октябрь 2007 г.). «Статистическая физика — для птиц». Physics Today . 60 (10): 28–30. Bibcode : 2007PhT....60j..28F. doi : 10.1063/1.2800090 .
4. Hildenbrandt, H; Carere, C; Hemelrijk, CK (2010). «Самоорганизованные воздушные демонстрации тысяч скворцов: модель». Behavioral Ecology . 21 (6): 1349–1359. arXiv : 0908.2677 . doi : 10.1093/beheco/arq149 .
5. Хемелрик, CK; Хильденбрандт, H (2011). «Некоторые причины изменчивой формы стай птиц». PLOS ONE . 6 (8): e22479. Bibcode : 2011PLoSO...622479H. doi : 10.1371/journal.pone.0022479 . PMC 3150374. PMID  21829627 . 
6. Проект Звездный Флаг
7. Модель поведения роя, разработанная Университетом Гронингена
8. Delgado-Mata C, Ibanez J, Bee S, et al. (2007). «Об использовании виртуальных животных с искусственным страхом в виртуальных средах». New Generation Computing . 25 (2): 145–169. doi :10.1007/s00354-007-0009-5. S2CID  26078361.
9. Хартман С, Бенеш Б (2006). «Автономные боиды». Компьютерная анимация и виртуальные миры . 17 (3–4): 199–206. doi :10.1002/cav.123. S2CID  15720643.
10. Хемелрик, CK; Хильденбрандт, Х. (2011). «Некоторые причины изменчивой формы стай птиц». PLOS ONE . 6 (8): e22479. Bibcode : 2011PLoSO...622479H. doi : 10.1371/journal.pone.0022479 . PMC 3150374. PMID  21829627 . 
11. Спектор, Л.; Кляйн, Дж.; Перри, К.; Файнстайн, М. (2003). "Возникновение коллективного поведения в эволюционирующих популяциях летающих агентов". Труды конференции по генетическим и эволюционным вычислениям (GECCO-2003) . Springer-Verlag . Получено 01.05.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. Gabbai, JME (2005). Complexity and the Aerospace Industry: Understanding Emergence by Relating Structure to Performance using Multi-Agent Systems (Thesis). Манчестер: докторская диссертация Манчестерского университета. Архивировано из оригинала 19.12.2014 . Получено 21.02.2007 .
16. Ibanez J, Gomez-Skarmeta AF, Blat J (2003). "DJ-boids: эмерджентное коллективное поведение как программирование многоканальной радиостанции". Труды 8-й международной конференции по интеллектуальным пользовательским интерфейсам . С. 248–250. doi :10.1145/604045.604089.
17. Moere AV (2004). "Визуализация изменяющихся во времени данных с использованием информационных флокинговых объектов" (PDF) . Труды симпозиума IEEE по визуализации информации . стр. 97–104. doi :10.1109/INFVIS.2004.65. Архивировано (PDF) из оригинала 2022-10-09.
18. Cui Z, Shi Z (2009). «Оптимизация роя частиц Boid». Международный журнал инновационных вычислений и приложений . 2 (2): 77–85. doi :10.1504/IJICA.2009.031778.

Источники

• Буффанаис, Роланд (2016). Проектирование и управление динамикой роя. SpringerBriefs in Complexity. Springer Singapore. doi : 10.1007/978-981-287-751-2. ISBN 9789812877505.
• Cucker, Felipe; Steve Smale (2007). "The Mathematics of Emergence" (PDF) . Japanese Journal of Mathematics . 2 : 197–227. doi :10.1007/s11537-007-0647-x. S2CID  2637067 . Получено 09.06.2008 .
• Шен, Джеки (Цзяньхун) (2008). «Стая Какера–Смейла под иерархическим лидерством». SIAM J. Appl. Math . 68 (3): 694–719. arXiv : q-bio/0610048 . doi :10.1137/060673254. S2CID  14655317. Получено 09.06.2008 .
• Fine, BT; DA Shell (2013). «Унификация микроскопических моделей движения стаи для виртуальных, роботизированных и биологических членов стаи». Auton. Robots . 35 (2–3): 195–219. doi :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.

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

• Страница Boids Крейга Рейнольдса
• Публикации Изтока Лебара Бажеца по нечеткой логике, основанные на флокировании
• Бормотание скворцов (видео BBC)
• Полет дрона запечатлел бормотание скворцов Норфолка (видео BBC)