Abstract
Multi-agent systems arise from diverse fields in natural and artificial systems, and a basic problem is to understand how locally interacting agents lead to collective behaviors (e.g., synchronization) of the overall system. In this paper, we will consider a basic class of multi-agent systems that are described by a simplification of the well-known Vicsek model. This model looks simple, but the rigorous theoretical analysis is quite complicated, because there are strong nonlinear interactions among the agents in the model. In fact, most of the existing results on synchronization need to impose a certain connectivity condition on the global behaviors of the agents’ trajectories (or on the closed-loop dynamic neighborhood graphs), which are quite hard to verify in general. In this paper, by introducing a probabilistic framework to this problem, we will provide a complete and rigorous proof for the fact that the overall multi-agent system will synchronize with large probability as long as the number of agents is large enough. The proof is based on a detailed analysis of both the dynamical properties of the nonlinear system evolution and the asymptotic properties of the spectrum of random geometric graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Shaw (1975) ArticleTitleFish in schools Natural History 84 IssueID8 40–46
B.L. Partridge (1982) ArticleTitleThe structure and function of fish schools Sci. Amer. 246 IssueID6 114–123 Occurrence Handle10.1038/scientificamerican0682-114
A. Okubo (1986) ArticleTitleDynamical aspects of animal grouping: Swarms, schools, flocks and herds Adv. Biophys. 22 1–94 Occurrence Handle10.1016/0065-227X(86)90003-1
J.K. Parrish S.V. Viscido D. Grunbaum (2002) ArticleTitleSelf-organized fish schools: An examination of emergent properties Biol. Bull. 202 296–305 Occurrence Handle10.2307/1543482
T. Vicsek A. Czirok E. Jacob I. Cohen O. Shochet (1995) ArticleTitleNovel type of phase transition in a system of self-deriven particles Phys. Rev. Lett. 75 IssueID6 1226–1229 Occurrence Handle10.1103/PhysRevLett.75.1226
A. Czirok A. Barabasi T. Vicsek (1999) ArticleTitleCollective motion of self propelled particles: Kinetic phase transition in one dimension Phys. Rev. Lett. 82 IssueID1 209–212 Occurrence Handle10.1103/PhysRevLett.82.209
C. W. Reynolds, Flocks, herds, and schools: A distributed behavioral model, in Comput. Graph. (ACM SIGGRAPHí87 Conf. Proc.), 1987, 21 : 25–34.
A. Jadbabaie J. Lin A.S. Morse (2003) ArticleTitleCoordination of groups of mobile agents using nearest neighbor rules IEEE Trans. Autom. Control 48 IssueID6 988–1001 Occurrence Handle10.1109/TAC.2003.812781
W. Ren R.W. Beard (2005) ArticleTitleConsensus seeking in multiagent systems under dynamically changing interaction topologies IEEE Trans. Autom. Control 50 IssueID5 655–661 Occurrence Handle10.1109/TAC.2005.846556
A. Jadbabaie, On distributed coordination of mobile agents with changing nearest neighbors, Technical Report, University of Pennsylvania, Philadelphia, PA, 2003.
F. Cucker and S. Smale, Emergent behavior in flocks, IEEE Trans. Autom. Control, 2006, to appear.
J. Tsitsiklis D. Bertsekas M. Athans (1986) ArticleTitleDistributed asynchronous deterministic and stochastic gradient optimization algorithms IEEE Trans. Autom. Control 31 IssueID9 803–812 Occurrence Handle10.1109/TAC.1986.1104412
Z. X. Liu and L. Guo, Connectivity and synchronization of multi-agent systems, in Proc. 25th Chinese Control Conference August 7–11, Harbin, China, 2006.
L. Guo (1993) Stochastic Systems-Stability, Estimation and Control Jilin Science and Technology Press Changchun, China
R.A. Horn C.R. Johnson (1985) Matrix Analysis Cambridge Univercity Press Cambridge
F. Xue P.R. Kumar (2004) ArticleTitleThe number of neighbors needed for connectivity of wireless networks Wirel. Netw. 10 IssueID2 169–181 Occurrence Handle10.1023/B:WINE.0000013081.09837.c0
J. Diaz, J. Petit, and M. Serna, A guide to concentration bounds, in Handbook on Randomized Computing (Ed. by S. Rajasekaran, P. Pardalos, J. Reif, and J.Rolim), Vol. II, Chapter 12, Kluwer Press, New York, 2001, 457–507.
F.R.K. Chung (1997) Spectral Graph Theory American Mathematical Society Providence, RI
G. G. Tang and L. Guo, Convergence analysis of linearized Vicsek’s model, in Proc. 25th Chinese Control Conference, August 7–11, Harbin, China, 2006.
D. Reinhar, Graph Theory (Second Edition), GTM 173, Springer-Verlag, New York, 2000.
B. Bollobas, Modern Graph Theory, GTM 184, Springer-Verlag, New York, 1998.
D. B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, Upper Saddle River, NJ, 2001.
B. Bollobas, Random Graph (Second Edition), Cambridge University Press, Cambridge, UK, 2001.
N. Biggs. (1993) Algebraic Graph Theory Cambridge University Press Cambridge, UK
C. Godsil and G. Royle, Algebraic Graph Theory, GTM 207, Springer-Verlag, New York, 2001.
M. Penrose (2003) Random Geometric Graphs Oxford University Press Oxford, UK
P. Gupta and P. R. Kumar, Critical power for asymptotic connectivity in wireless networks, in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming (Ed. by W. M. McEneany, G. Yin, and Q. Zhang), Birkhauser, Boston, MA, 1998, 547–566.
Z. S. Yang. Combinitorial Mathematics and Its Algorithms, University of Science and Technology of China Press, Hefei, China, 1997.
W.D. Wallis (1988) Combinatorial Designs Marcel Dekker New York
D. Huang L. Guo (1990) ArticleTitleEstimation of Nonstationary ARMAX Models Based on the Hannan-Rissanen Method The Annals of Statistics 18 IssueID4 1729–1756
Author information
Authors and Affiliations
Corresponding author
Additional information
The research is supported by National Natural Science Foundation of China under the Grants No. 60221301 and No. 60334040.
Rights and permissions
About this article
Cite this article
Tang, G., Guo, L. Convergence of a Class of Multi-Agent Systems In Probabilistic Framework. Jrl Syst Sci & Complex 20, 173–197 (2007). https://doi.org/10.1007/s11424-007-9016-3
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11424-007-9016-3