Abstract
This paper investigates consensus of flocks consisting of n autonomous agents in the plane, where each agent has the same constant moving speed v n and updates its heading by the average value of the k n nearest agents from it, with v n and k n being two prescribed parameters depending on n. Such a topological interaction rule is referred to as k n -nearest-neighbors rule, which has been validated for a class of birds by biologists and verified to be robust with respect to disturbances. A theoretical analysis will be presented for this flocking model under a random framework with large population, but without imposing any a priori connectivity assumptions. We will show that the minimum number of k n needed for consensus is of the order O(log n) in a certain sense. To be precise, there exist two constants C1 > C2 > 0 such that, if k n > C1 log n, then the flocking model will achieve consensus for any initial headings with high probability, provided that the speed v n is suitably small. On the other hand, if k n < C2 log n, then for large n, with probability 1, there exist some initial headings such that consensus cannot be achieved, regardless of the value of v n .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C. W. Reynolds. Flocks, herds and schools: A distributed behavioral model. ACM SIGGRAPH Computer Graphics, 1987, 21(4): 25–34.
I. D. Couzin, J. Krause, R. James, et al. Collective memory and spatial sorting in animal groups. Journal of Theoretical Biology, 2002, 218(1): 1–11.
R. Olfati-Saber. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on Automatic Control, 2006, 51(3): 401–420.
H. G. Tanner, A. Jadbabaie, G. J. Pappas. Flocking in fixed and switching networks. IEEE Transactions on Automatic Control, 2007, 52(5): 863–868.
C. Viragh, G. Vasarhelyi, N. Tarcai, et al. Flocking algorithm for autonomous flying robots. Bioinspiration and Biomimetics, 2014, 9(2): DOI 10.1088/1748-3182/9/2/025012.
T. Vicsek, A. Czirók, E. Ben-Jacob, et al. Novel type of phase transition in a system of self-driven particles. Physical Review Letters, 1995, 75(6): 1226–1229.
P. Szabó, M. Nagy, T. Vicsek. Transitions in a self-propelledparticles model with coupling of accelerations. Physical Review E, 2009, 79(2): DOI 10.1103/PhysRevE.79.021908.
I. D. Couzin, J. Krause, N. R. Franks, et al. Effective leadership and decision-making in animal groups on the move. Nature, 2005, 433(7025): 513–516.
A. Jadbabaie, J. Lin, A. S. Morse. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 2003, 48(6): 988–1001.
L. Moreau. Stability of multi-agent systems with time-dependent communication links. IEEE Transactions on Automatic Control, 2005, 50(2): 169–182.
W. Ren, R. W. Beard, E. M. Atkins. A survey of consensus problems in multi-agent coordination. Proceedings of the American Control Conference, Portland: IEEE, 2005: 1859–1864.
F. Cucker, S Smale. Emergent behavior in flocks. IEEE Transactions on Automatic Control, 2007, 52(5): 852–862.
J. A. Carrillo, M. Fornasier, J. Rosado, et al. Asymptotic flocking dynamics for the kinetic Cucker-Smale model. SIAM Journal on Mathematical Analysis, 2010, 42(1): 218–236.
B. Chazelle. The geometry of flocking. Proceedings Of the 26th Annual Symposium on Computational Geometry, New York: ACM, 2010: 19–28.
A. Okubo. Dynamical aspects of animal grouping: swarms, schools, flocks, and herds. Advances in Biophysics, 1986, 22: 1–94.
D. Grünbaum, A. Okubo. Modeling social animal aggregations. Frontiers in Mathematical Biology. Berlin: Springer, 1994: 296–325.
A. Mogilner, L. Edelstein-Keshet, L. Bent, et al. Mutual interactions, potentials, and individual distance in a social aggregation. Journal of Mathematical Biology, 2003, 47(4): 353–389.
Z. Liu, J. Han, X. M. Hu. The proportion of leaders needed for the expected consensus. Automatica, 2009, 47(12): 2697–2703.
G. Tang, L. Guo. Convergence of a class of multi-agent systems in probabilistic framework. Journal of Systems Science and Complexity, 2007, 20(2): 173–197.
Z. Liu, L. Guo. Synchronization of multi-agent systems without connectivity assumptions. Automatica, 2009, 45(12): 2744–2753.
G. Chen, Z. Liu, L. Guo. The smallest possible interaction radius for synchronization of self-propelled paricles. SIAM Review, 2014, 56(3): 499–521.
C. Chen, G. Chen, L. Guo. Synchronization of mobile autonomous agents with M-nearest-neighbor rule. Journal of Systems Science and Complexity, 2015, 28(1): 1–15.
C. Chen, G. Chen, L. Guo. The number of neighbors needed for consensus of flocks. Proceedings of the 32nd Chinese Control Conference, Xi’an: IEEE, 2013: 7060–7065.
L. Wang, X. Wang, X. Hu. Synchronization of multi-agent systems with topological interaction. Proceedings of the 18th IFAC World Congress, Milano, Italy, 2011.
M. Ballerini, N. Calbibbo, R. Candeleir, et al. Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study. Proceedings of the National Academy of Sciences, 2008, 105(4): 1232–1237.
W. Bialek, A. Cavagna, I. Giardina, et al. Statistical mechanics for natural flocks of birds. Proceedings of the National Academy of Sciences, 2012, 109(13): 4786–4791.
J. Emmerton, J. D. Delius. Beyond sensation: Visual cognition in pigeons. Vision, Brain, and Behavior in Birds. Cambridge: MIT Press, 1993: 377–390.
R. W. Tegeder, J. Krause. Density dependence and numerosity in fright stimulated aggregation behaviour of shoaling fish. Philosophical Transactions of the Royal Society of London, 1995, 350(1334): 381–390.
G. F. Young, L. Scardovi, A. Cavagna, et al. Starling flock networks manage uncertainty in consensus at low cost. PLOS Computational Biology, 2013, 9(1): DOI 10.1371/journal.pcbi.1002894.
F. Xue, P. R. Kumar. The number of neighbors needed for connectivity of wireless networks. Wireless Networks, 2004, 10(2): 169–181.
P. Balister, B. Bollobás, A. Sarkar, et al. Connectivity of random knearest-neighbour graphs. Advances in Applied Probability, 2005, 37(1): 1–24.
M. Penrose. Random Geometric Graphs. Oxford: Oxford University Press, 2003.
P. Gupta, P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. Stochastic Analysis, Control, Optimization and Applications. Boston: Birkhäuser, 1999: 547–566.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is dedicated to Professor T. J. Tarn on the occasion of his 80th birthday.
This work was supported by the National Natural Science Foundation of China (No. 91427304, 61673373, 11688101), the National Key Basic Research Program of China (973 program) (No. 2014CB845301/2/3), and the Leading Research Projects of Chinese Academy of Sciences (No. QYZDJ-SSW-JSC003).
Chen CHEN was born in Shannxi, China, in 1987. She received the B.Sc. degree in Mathematics from Beihang University in 2009, and the Ph.D. degree in Control Theory from the Academy of Mathematics and Systems Science, Chinese Academy of Sciences, in 2014. She is currently a researcher at Huawei Technologies Co. Ltd. Her research interests include complex systems, distributed filters, reinforcement learning and deep learning.
Ge CHEN received the B.Sc. degree in Mathematics from the University of Science and Technology of China in 2004, and the Ph.D. degree in Mathematics from the University of Chinese Academy of Sciences, China, in 2009. He jointed the National Center for Mathematics and Interdisciplinary Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences in 2011, and is currently an Associate Professor. His current research interest is the collective behavior of multi-agent systems. Dr. Chen received the First Prize of the Application Award from the Operations Research Society of China (2010). One of his papers was selected as a SIGEST paper by the SIAM Review (2014). He was also a finalist for the OR in Development prize from the International Federation of Operations Research Societies (2011), and for the best theoretical paper award at the 10th World Congress on Intelligent Control and Automation (2012).
Lei GUO was born in China in 1961. He received the B.Sc. degree in Mathematics from Shandong University in 1982, and the Ph.D. degree in Control Theory from the Chinese Academy of Sciences (CAS) in 1987. He is currently a professor at the Academy of Mathematics and Systems Science, CAS, and Director of National Center for Mathematics and Interdisciplinary Sciences (NCMIS), CAS. He is a Fellow of both IEEE and IFAC, Member of CAS, Foreign Member of the Royal Swedish Academy of Engineering Sciences. His current research interests include feedback capability, nonlinear and adaptive control, multi-agent systems, distributed adaptive filtering, and game-based control systems, among others.
Rights and permissions
About this article
Cite this article
Chen, C., Chen, G. & Guo, L. On the minimum number of neighbors needed for consensus of flocks. Control Theory Technol. 15, 327–339 (2017). https://doi.org/10.1007/s11768-017-7097-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11768-017-7097-7