鸟群算法

已由Dorr进行初步翻译

鸟群算法 Boids是模拟鸟类群集行为的人工生命项目，由克雷格·雷诺兹 Craig Reynolds于1986年开发。该模型基于常用于计算机动画或计算机辅助设计的计算机三维几何。他关于这个主题的论文发表在1987年的 ACM SIGGRAPH（美国计算机协会计算机图形专业组组织的计算机图形学顶级年度会议）会议记录上。^[1]“ boid”是“ bird-oid object”的缩写，指一个类鸟对象。^[2]恰巧，“boid”也是纽约都市方言中“bird”的发音。

算法介绍

分离

对齐

靠近

与大多数人工生命模拟一样，Boids 是涌现 Emergent行为的一个例子; 也就是说，Boids 的复杂性来自于遵循一系列简单规则的个体代理（这里是 Boids）的相互作用。在最简单的Bolds 世界中适用的规则如下，其描述了鸟群中的个体如何根据周边同伴的位置和速度移动:

分离 Separation: 移动以避开群体拥挤处

对齐 Alignment: 转向群体的平均航向

靠近 Cohesion: 朝群体的平均位置（质心）移动

每个 boid 个体都可以得知整体的几何参数，但群体要求其只对其周围某个小邻近范围作出反应。该邻近范围由一个距离（从该个体的中心算起）和一个角度（从其飞行方向算起）决定。此范围外的同伴不予考虑。该临近范围可以认为是一个有限知觉的模型（就像浑水中的鱼一样）；但更恰当的想法可能是，其定义了鸟群影响了个体转向的区域范围。

可以添加更复杂的规则，如避障和寻找目标。

该基本模型自雷诺兹提出以来，已用多种方法扩展。例如，Delgado-Mata ^[3]等人扩展基本模型以加入恐惧的影响。利过一种可用自由膨胀气体中的粒子模拟的信息素，动物间用嗅觉来传递情感。哈特曼 Hartman和贝内斯 Benes^[4]为定位过程引入了一种补充力量，他们称之为领导权的更迭。这条决定了某只鸟成为领导者及试图逃跑的机会。

Boids 的运动可以表现为混乱（分裂的群体和狂野的行为）或有序。意想不到的行为，比如群体分散和避开障碍后的团聚可以被认为是应急的。

Boids 框架通常用于计算机图形学，提供鸟群和其他生物（如鱼群）的逼真表现。例如，在1998年的电子游戏《半条命 Half-Life》中，游戏结束时Xen中出现的类似鸟类的飞行生物就使用了该框架（游戏文件中命名为“ boid”）。

Boids 模型可用于集群机器人 Swarm Robotics中简单的无人地面车辆（UGV）^[5] 或微型飞行器 Micro Aerial Vehicles（MAV）^[6]群体的直接控制和稳定。为了异质 UAV-UGV 群体的稳定性，Saska 等人将该模型用于板载相对定位。^[7]

在当时提出时，雷诺兹的方法相比于传统的计算机动画电影技术是一个巨大的进步。第一部利用了此模型的动画片是《史丹利和史黛拉: 破冰 Stanley and Stella in: Breaking The Ice》（1987），之后是蒂姆·伯顿 Tim Burton的故事片《蝙蝠侠归来 Batman Returns》（1992），电脑合成的蝙蝠群和成群的企鹅行进穿过哥谭市 Gotham City的街道。^[8]

Boids 模型已经被用于其他有趣应用。该系统已应用于互联网多频道广播电台的自动节目编排，.^[9]以及可视化信息^[10]和优化任务。^[11]

参见

群体智能 Swarm intelligence

集体细胞迁移 Collective cell migration

参考文献

↑ Reynolds, Craig (1987). Flocks, herds and schools: A distributed behavioral model.. Association for Computing Machinery. pp. 25–34. doi:10.1145/37401.37406. ISBN 978-0-89791-227-3.
↑ Banks, Alec; Vincent, Jonathan; Anyakoha, Chukwudi (July 2007). "A review of particle swarm optimization. Part I: background and development". Natural Computing. 6 (4): 467–484. CiteSeerX 10.1.1.605.5879. doi:10.1007/s11047-007-9049-5.
↑ Delgado-Mata, Carlos; Martinez, Jesus Ibanez; Bee, Simon; Ruiz-Rodarte, Rocio; Aylett, Ruth (2007). "On the use of Virtual Animals with Artificial Fear in Virtual Environments". New Generation Computing. 25 (2): 145–169. doi:10.1007/s00354-007-0009-5.
↑ Hartman, Christopher; Benes̆, Bedr̆ich (July 2006). "Autonomous boids". Computer Animation and Virtual Worlds. 17 (3–4): 199–206. doi:10.1002/cav.123.
↑ Min, Hongkyu; Wang, Zhidong (2011). Design and analysis of Group Escape Behavior for distributed autonomous mobile robots. IEEE International Conference on Robotics and Automation (ICRA). doi:10.1109/ICRA.2011.5980123.
↑ Saska, Martin; Jan, Vakula; Libor, Preucil (2014). Swarms of micro aerial vehicles stabilized under a visual relative localization. IEEE International Conference on Robotics and Automation (ICRA). doi:10.1109/ICRA.2014.6907374.
↑ Saska, Martin; Vojtech, Vonasek; Tomas, Krajnik; Libor, Preucil (2012). Coordination and Navigation of Heterogeneous UAVs-UGVs Teams Localized by a Hawk-Eye Approach (PDF). IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
↑ Lebar Bajec, Iztok; Heppner, Frank H. (2009). "Organized flight in birds" (PDF). Animal Behaviour. 78 (4): 777–789. doi:10.1016/j.anbehav.2009.07.007.
↑ Ibáñez, Jesús; Gómez-Skarmeta, Antonio F.; Blat, Josep (2003). DJ-boids: emergent collective behavior as multichannel radio station programming. pp. 248–250. doi:10.1145/604045.604089. {{cite conference}}: Unknown parameter |booktitle= ignored (help)
↑ Moere, A V (2004). Time-Varying Data Visualization Using Information Flocking Boids. pp. 97–104. doi:10.1109/INFVIS.2004.65. {{cite conference}}: Unknown parameter |booktitle= ignored (help)
↑ Cui, Zhihua; Shi, Zhongzhi (2009). "Boid particle swarm optimisation". International Journal of Innovative Computing and Applications. 2 (2): 77–85. doi:10.1504/IJICA.2009.031778.