Natural algorithms

ABSTRACT

We provide further evidence that the study of complex self-organizing systems can benefit from an algorithmic perspective. The subject has been traditionally viewed through the lens of physics and control theory. Using tools typically associated with theoretical computer science, we settle an old question in theoretical ecology: bounding the convergence of bird flocks. We bound the time to reach steady state by a tower-of-twos of height linear in the number of birds. We prove that, surprisingly, the tower-of-twos growth is intrinsic to the model. This unexpected result demonstrates the merits of approaching biological dynamical systems as "natural algorithms" and applying algorithmic techniques to them.

REFERENCES

• 1: Ballerini, M., Cabibbo, N., Candelier, R., Cavagna, A., Cisbani, E., Giardina, I., Lecomte, V., Orlandi, A., Parisi, G., Procaccini, A., Viale, M., Zdravkovic, V. Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study, Proc. National Academy of Sciences 105 (2008), 1232--1237.
• 2: Chung, F. Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, Vol. 92, Amer. Math. Soc., Providence, 1997.
• 3: Cucker, F., Smale, S. Emergent behavior in flocks, IEEE Trans. Automatic Control 52 (2007), 852--862.
• 4: Hendrickx, J. M., Blondel, V. D. Convergence of different linear and non-linear Vicsek models, Proc. 17th International Symposium on Mathematical Theory of Networks and Systems (MTNS2006), Kyoto (Japan), July 2006, 1229--1240.
• 5: Jadbabaie, A., Lin, J., Morse, A. S. Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. Automatic Control 48 (2003), 988--1001.
• 6: Ji, M., Egerstedt, M. Distributed coordination control of multi-agent systems while preserving connectedness, IEEE Transactions on Robotics 23 (2007), 693--703.
• 7: Landau, H. J., Odlyzko, A. M. Bounds for eigenvalues of certain stochastic matrices, Linear algebra and Its Applications 38 (1981), 5--15.
• 8: Li, S., Wang, H. Multi-agent coordination using nearest neighbor rules: revisiting the Vicsek model, 2004, arXiv:cs/0407021v2
• 9: Lorenz, J. A stabilization theorem for dynamics of continuous opinions, Physica A: Statistical Mechanics and its Applications 355 (2005), 217--223.
• 10: Moreau, L. Stability of multiagent systems with time-dependent communication links, IEEE Transactions on Automatic Control 50 (2005), 169--182.
• 11: Moshtagh, N., Jadbabaie, A., Daniilidis, K. Distributed geodesic control laws for flocking of nonholonomic agents, Proc. ECC-CDC 2005, Seville, Spain.
• 12: Olfati-Saber, R. Flocking for multi-agent dynamic systems: algorithms and theory, IEEE Transactions on Automatic Control 51 (2006), 401--420.
• 13: Olshevsky, A., Tsitsiklis, J. N. Convergence speed in distributed consensus and averaging, arXiv:math/0612682, 2006.
• 14: Olshevsky, A., Tsitsiklis, J. N. On the nonexistence of quadratic Lyapunov functions for consensus algorithms, IEEE Transactions on Automatic Control, to appear, 2008.
• 15: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.25-34, July 1987
• 16: Seneta, E. Non-Negative Matrices and Markov Chains, Springer, 2nd ed., 2006.
• 17: Shi, H., Wang, L., Chu, T. Coordination of multiple dynamic agents with asymmetric interactions, Proc. 2005 IEEE International Symposium on Intelligent Control, Cyprus, June 27--29, 2005.
• 18: Tahbaz-Salehi, A., Jadbabaie, A. On recurrence of graph connectivity in Vicsek's model of motion coordination for mobile autonomous agents, American Control Conference, ACC 2007.
• 19: Tanner, H. G., Jadbabaie, A., Pappas, G. J. Stable flocking of mobile agents, Part I: fixed topology, Proc. IEEE Conference on Decision and Control, Maui, Hawaii (2003), 2010--2015.
• 20: Tanner, H. G., Jadbabaie, A., Pappas, G. J. Stable flocking of mobile agents, Part II: dynamic topology, Proc. IEEE Conference on Decision and Control, Maui, Hawaii (2003), 2016--2021.
• 21: Tanner, H. G., Jadbabaie, A., Pappas, G. J. Flocking in fixed and switching networks, IEEE Trans. Automatic Control 52, (2006), 8630--868.
• 22: Vicsek, T., Czirok, A., Ben-Jacob, E., Cohen, I., Shochet, O. Novel type of phase transition in a system of self-driven particles, Physical Review Letters 75 (1995), 1226--1229.
• 23: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms