Abstract
Flocking motions have been the subject of hundreds of studies over the past six decades. The vast majority of models have nearly identical aims: bottom-up demonstration of basic emergent flocking motions. Despite a significant fraction of the literature providing algorithmic descriptions of models, incompleteness and imprecision are also readily identifiable in flocking algorithms, algorithmic input, and validation of the models. To address this issue, this meta-study introduces a data-flow template, which unifies many of the existing approaches. Additionally, there are small differences and ambiguities in the flocking scenarios being studied by different researchers; unfortunately, these differences are of considerable significance. For example, much subtlety is needed to specify sensory requirements exactly and minor modifications may critically alter a flock’s exhibited motions. We introduce two taxonomies that minimize both incompleteness and imprecision, and enable us to highlight those publications that study flocking motions under comparable assumptions. Furthermore, we aggregate and translate the publications into a consolidated notation. The common notation along with the data-flow template and the two taxonomies constitute a collection of tools, that together, facilitates complete and precise flocking motion models, and enables much of the work to be unified. To conclude, we make recommendations for more diverse research directions and propose criteria for rigorous problem definitions and descriptions of future flocking motion models.
Similar content being viewed by others
Notes
Typically the sensor’s reference frame will be that of the flock member, but when the model uses global sensors (e.g., overhead camera) the two reference frames will differ.
In this paper, flock member \(X\) calls member \(Y\) a neighbor if and only if \(Y\) can be sensed by \(X\).
Phase shifts refer to the moments in time when a flock becomes or discontinues being a flock.
References
Albi, G., & Pareschi, L. (2012). Modeling self-organized systems interacting with few individuals: from microscopic to macroscopic dynamics. Ar**v e-prints.
Aoki, I. (1984). Internal dynamics of fish schools in relation to inter-fish distance. Bulletin of the Japanese Society of Scientific Fisheries, 48(3), 1081–1088.
Arkin, R. C., & Balch, T. (1999). Behavior-based formation control for multi-robot teams. IEEE Transactions on Robotics and Automation, 14(6), 926–939.
Babak, P., Magnsson, K. G., & Sigurdsson, S. (2004). Dynamics of group formation in collective motion of organisms. Mathematical Medicine and Biology, 21(4), 269–292.
Ballerini, M., Cabibbo, N., Candelier, R., Cavagna, A., Cisbani, E., Giardina, I., et al. (2008). Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study. Proceedings of the National Academy of Sciences, 105(4), 1232–1237.
Barbosa, A. (1995). Foraging strategies and their influence on scanning and flocking behaviour of waders. Journal of Avian Biology, 26(3), 182–186.
Bazazi, S., Buhl, J., Hale, J. J., Anstey, M. L., Sword, G. A., Simpson, S. J., et al. (2008). Collective motion and cannibalism in locust migratory bands. Current Biology, 18(10), 735–739.
Bender, J. G., & Fenton, R. E. (1970). On the flow capacity of automated highways. Transportation Science, 4(1), 52–63.
Blomqvist, O., Bremberg, S., & Zauer, R. (2012). Mathematical modeling of flocking behavior. Doctoral dissertation, KTH.
Bode, N. W. F., Franks, D. W., & Wood, A. J. (2011). Limited interactions in flocks: Relating model simulations to empirical data. Journal of The Royal Society Interface, 8(55), 301–304.
Camperi, M., Cavagna, A., Giardina, I., Parisi, G., & Silvestri, E. (2012). Spatially balanced topological interaction grants optimal cohesion in flocking models. Interface Focus, 2(6), 715–725.
Cavagna, A., Cimarelli, A., Giardina, I., Parisi, G., Santagati, R., Stefanini, F., et al. (2010). From empirical data to inter-individual interactions: Unveiling the rules of collective animal behavior. Mathematical Models and Methods in Applied Sciences, 20, 1491–1510.
Cavagna, A., Giardina, I., & Ginelli, F. (2012). Boundary information inflow enhances correlation in flocking. Ar**v e-prints.
Clark, P. J., & Evans, F. C. (1954). Distance to nearest neighbor as a measure of spatial relationships in populations. Ecology, 35(4), 445–453.
Codling, E. A., Pitchford, J. W., & Simpson, S. D. (2007). Group navigation and the “many-wrongs principle” in models of animal movement. Ecology, 88(7), 1864–1870.
Conradt, L., Krause, J., Couzin, I. D., & Roper, T. J. (2009). “Leading According to Need” in self-organizing groups. The American Naturalist, 173(3), 304–312.
Couzin, I. D., Krause, J., Franks, N. R., & Levin, S. A. (2005). Effective leadership and decision making in animal groups on the move. Nature, 433(3), 513–516.
Şamiloglu, A. T., Gazi, V., & Koku, A. B. (2006). Effects of asynchronism and neighborhood size on clustering in self-propelled particle systems. In Computer and Information Sciences ISCIS 2006, Lecture Notes in Computer Science (Vol. 4263, pp. 665–676). Berlin: Springer.
Czirók, A., Stanley, H. E., & Vicsek, T. (1997). Spontaneously ordered motion of self-propelled particles. Journal of Physics A: Mathematical and General, 30(5), 1375–1385.
Dingle, H., & Drake, A. V. (2007). What is migration? BioScience, 57(2), 113–121.
Dong, J. G. (2012). Flocking under hierarchical leadership with a free-will leader. International Journal of Robust and Nonlinear Control, n/a–n/a.
Edelstein-Keshet, L. (2001). Mathematical models of swarming and social aggregation. In International Symposium on Nonlinear Theory and its Applications, Miyagi, Japan.
Emlen, J. T, Jr. (1952). Flocking behavior in birds. The Auk, 69(2), 160–170.
Ferrante, E., Turgut, A. E., Huepe, C., Stranieri, A., Pinciroli, C., & Dorigo, M. (2012). Self-organized flocking with a mobile robot swarm: A novel motion control method. Adaptive Behavior, 20(6), 460–477.
Fine, B. T., & Shell, D. A. (2011). Flocking: don’t need no stink’n robot recoginition. In IEEE/RSJ International Conference on Robotics and Automation, San Francisco, CA, USA.
Fine, B. T., & Shell, D. A. (2012). Examining the information requirements for flocking motion. In 12th International Conference on Adaptive Behavior, Odense, Denmark.
Gazi, V., & Passino, K. M. (2003). Stability analysis of swarms. IEEE Transactions on Automatic Control, 48(4), 692–697.
Gazi, V., & Passino, K. M. (2005). Stability of a one-dimensional discrete-time asynchronous swarm. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 35(4), 834–841.
Giardina, I. (2008). Collective behavior in animal groups: Theoretical models and empirical studies. HFSP Journal, 2(4), 205–219.
Ginelli, F., & Chaté, H. (2010). Relevance of metric-free interactions in flocking phenomena. Physical Review Letters, 105(168), 103.
Gökçe, F. & Şahin, E. (2009). To flock or not to flock: the pros and cons of flocking in long-range “migration” of mobile robot swarms. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’09), Budapest, Hungary (pp 65–72).
Goldstone, R. L., & Janssen, M. A. (2005). Computational models of collective behavior. Trends in Cognitive Sciences, 9(9), 424– 430.
Grégoire, G., Chaté, H., & Tuj, Y. (2003). Moving and staying together without a leader. Physica D: Nonlinear Phenomena, 181(30–4), 157–170.
Gueron, S., Levin, S. A., & Rubenstein, D. I. (1996). The dynamics of herds: From individuals to aggregations. Journal of Theoretical Biology, 182(1), 85–98.
Hamilton, W. D. (1971). Geometry for the selfish herd. Journal of Theoretical Biology, 31(2), 295–311.
Hauert, S., Leven, S., Varga, M., Ruini, F., Cangelosi, A., Zufferey, J. C., & Floreano, D. (2011). Reynolds flocking in reality with fixed-wing robots: communication range vs. maximum turning rate. In IEEE/RSJ International Conference on Robotics and Automation, San Francisco, CA, USA.
Helbing, D., & Molnár, P. (1995). Social force model for pedestrian dynamics. Physical Review E, 51, 4282–4286.
Helbing, D., Farkas, I., & Vicsek, T. (2000). Simulating dynamical features of escape panic. Nature, 407, 487–490.
Helbing, D., Buzna, L., Johansson, A., & Werner, T. (2005). Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transportation Science, 39(1), 1–24.
Hildenbrandt, H., Carere, C., & Hemelrijk, C. (2010). Self-organized aerial displays of thousands of starlings: A model. Behavioral Ecology, 21(6), 1349–1359.
Huth, A., & Wissel, C. (1992). The simulation of the movement of fish schools. Journal of Theoretical Biology, 156(3), 365–385.
Hutto, R. L. (1988). Foraging behavior patterns suggest a possible cost associated with participation in mixed-species bird flocks. Oikos, 51(1), 79–83.
Ip, G. W., Chiu, Cy, & Wan, C. (2006). Birds of a feather and birds flocking together: hysical versus behavioral cues may lead to trait- versus goal-based group perception. Journal of personality and social psychology, 90(3), 368–381.
Jadbabaie, A., Lin, J., & Morse, A. S. (2002). Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6), 988–1001.
James, R., Bennett, P. G., & Krause, J. (2004). Geometry for mutualistic and selfish herds: The limited domain of danger. Journal of Theoretical Biology, 228(1), 107–113.
Kelly, I. D., & Keating, D. A. (1996). On flocking by the fusion of sonar and active infrared sensors. In Proceedings of the Conference on Mechatronics and Machine Vision in Practice. Guimarães, Portugal (Vol. 1, pp. 14–17).
Kline, C. (1996). C++ boids. Retrieved March 2012 from http://www.behaviorworks.com/people/ckline/cornellwww/boid/boids.html.
Levine, H., Rappel, W. J., & Cohen, I. (2000). Self-organization in systems of self-propelled particles. Physical Review E, 63(1), 017101–017104.
Lindhé, M., Ögren, P., & Johansson, K., H. (2005). Flocking with Obstacle Avoidance: A New Distributed Coordination Algorithm Based on Voronoi Partitions. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’05), Barcelona, Spain (pp 1785–1790).
Lopez, U., Gautrais, J., Couzin, I. D., & Theraulaz, G. (2012). From behavioural analyses to models of collective motion in fish schools. Interface Focus, 2(6), 693–707.
Lukeman, R., Li, Y. X., & Edelstein-Keshet, L. (2010). Inferring individual rules from collective behavior. Proceedings of the National Academy of Sciences USA, 107(28), 12576–12580.
Matarić, M. J. (1993). Designing Emergent Behaviors: From Local Interactions to Collective Intelligence. In Proceedings of the Second International Conference on Simulation of Adaptive Behavior (SAB ’93), Honolulu, Hawai, USA (pp. 432–441).
Mikhailov, A. S., & Zanette, D. H. (1999). Noise-induced breakdown of coherent collective motion in swarms. Physical Review E, 60(4), 4571–4575.
Miki, T., & Nakamura, T. (2006). An effective simple shepherding algorithm suitable for implementation to a multi-mmobile robot system. In First International Conference on Innovative Computing, Information and Control, 2006. ICICIC ’06 (Vol. 3, pp. 161–165).
Mogilner, A., & Edelstein-Keshet, L. (1999). A non-local model for a swarm. Journal of Mathematical Biology, 38, 534–570.
Moussaïd, M., Helbing, D., Simon Garnier, M. C., Johansson, A., & Theraulaz, G. (2009). Experimental study of the Behavioural mechanisms underlying self-organization in human crowds. Proceedings of the Royal Society B, 276, 2755–2762.
Niizato, T., & Gunji, Y. P. (2011). Metrictopological interaction model of collective behavior. Ecological Modelling, 222(17), 3041–3049.
Okubo, A. (1986). Dynamical aspects of animal grou**: Swarms, schools, flocks, and herds. Advances in Biophysics, 22, 1–94.
Olfati-Saber, R. (2006). Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on Automatic Control, 51(3), 401–420.
Parrish, J. K. (1989). Re-examining the selfish herd: Are central fish safer? Animal Behaviour, 38(6), 1048–1053.
Parrish, J. K., & Edelstein-Keshet, L. (1999). Complexity, pattern, and evolutionary trade-offs in animal aggregation. Science, 284(5411), 99–101.
Parrish, J. K., Viscido, S. V., & Grunbaum, D. (2002). Self-organized fish schools: An examination of emergent properties. Biological Bulletin, 202(3), 296–305.
Partridge, B. L. (1982). The structure and function of fish schools. Scientific American, 246(6), 114–123.
Pitcher, T. J., Partridge, B. L., & Wardle, C. S. (1976). A blind fish can school. Science, 194(4268), 963–965.
Rands, S. A., Pettifor, R. A., Rowcliffe, J. M., & Cowlishaw, G. (2004). State-dependent foraging rules for social animals in selfish herds. Proceedings of the Royal Society of London Series B: Biological Sciences, 271(1557), 2613–2620.
Rauch, E. M., Millonas, M. M., & Chialvo, D. R. (1995). Pattern formation and functionality in swarm models. Physics Letters A, 207(3–4), 185–193.
Reynolds, C. W. (1987). Flocks, herds and schools: A distributed behavioral model. Computer Graphics, 21(4), 25–34.
Reynolds, C. W. (2004). Opensteer: Steering behaviors for autonomous characters. http://opensteer.sourceforge.net/, Last viewed in March 2012.
Shimoyama, N., Sugawara, K., Mizuguchi, T., Hayakawa, Y., & Sano, M. (1996). Collective motion in a system of motile elements. Physical Review Letters, 76(20), 3870–3873.
Simons, A. M. (2004). Many wrongs: The advantage of group navigation. Trends in Ecology & Evolution, 19(9), 453–455.
Smith, J., & Martin, A. (2009). Comparison of hard-core and soft-core potentials for modelling flocking in free space. Ar**v e-prints.
Sugawara, K. (2012). Personal communications.
Szabó, P., Nagy, M., & Vicsek, T. (2008). Turning with the others: novel transitions in an SPP model with coupling of accelerations. In Proceedings of the IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO ’08), Venice, Italy (pp 463–464).
Szabó, P., Nagy, M., & Vicsek, T. (2009). Transitions in a self-propelled-particles model with coupling of accelerations. Physical Review E, 79(2), 021908–021913.
Tanner, H. G., Jadbabaie, A., & Pappas, G. J. (2003a). Stable flocking of mobile agents, part I: Fixed topology. In Proceedings of the IEEE Conference on Decision and Control (pp. 2010–2015).
Tanner, H. G., Jadbabaie, A., & Pappas, G. J. (2003b). Stable flocking of mobile agents, part II: Dynamic topology. In Proceedings of the IEEE Conference on Decision and Control (pp. 2016–2021).
Toner, J., & Tu, Y. (1998). Flocks, herds, and schools: A quantitative theory of flocking. Physical Review E, 58(4), 4828–4858.
Turgut, A., Çelikkanat, H., Gökçe, F., & Şahin, E. (2008). Self-organized flocking in mobile robot swarms. Swarm Intelligence, 2(2–4), 97–120.
Vaughan, R., Sumpter, N., Henderson, J., Frost, A., & Cameron, S. (2000). Experiments in automatic flock control. Robotics and Autonomous Systems, 31, 109–117.
Vicsek, T., & Zafeiris, A. (2012). Collective motion. Physics Reports, 517(3–4), 71–140.
Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., & Shochet, O. (1995). Novel type of phase transition in a system of self-driven particles. Physical Review Letters, 75(6), 1226–1229.
Vine, I. (1971). Risk of visual detection and pursuit by a predator and the selective advantage of flocking behaviour. Journal of Theoretical Biology, 30(2), 405–422.
Viscido, S. V., & Wethey, D. S. (2002). Quantitative analysis of fiddler crab flock movement: Evidence for ‘selfish herd’ behaviour. Animal Behaviour, 63(4), 735–741.
Viscido, S. V., Miller, M., & Wethey, D. S. (2002). The dilemma of the selfish herd: The search for a realistic movement rule. Journal of Theoretical Biology, 217(2), 183–194.
Warburton, K., & Lazarus, J. (1991). Tendency-distance models of social cohesion in animal groups. Journal of Theoretical Biology, 150(4), 473–488.
Whitfield, D. P. (2003). Redshank Tringa totanus flocking behaviour, distance from cover and vulnerability to sparrowhawk Accipiter nisus predation. Journal of Avian Biology, 34(7), 163– 169.
Wood, A. J., & Ackland, G. J. (2007). Evolving the selfish herd: Emergence of distinct aggregating strategies in an individual-based model. Proceedings of the Royal Society of London Series B: Biological Sciences, 274(1618), 1637–1642.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fine, B.T., Shell, D.A. Unifying microscopic flocking motion models for virtual, robotic, and biological flock members. Auton Robot 35, 195–219 (2013). https://doi.org/10.1007/s10514-013-9338-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-013-9338-z