On the cluster consensus of discrete-time multi-agent systems
Introduction
It is well known that multi-agent systems (MAS) are systems which consist of many interacting autonomous agents governed by some local rules [1], [2], [3], [4], [5], [6], [7], [8], [9], [10]. MAS are ubiquitous in the real world, such as group robots, self-organized sensor networks, bird flocks, and ant mills [11], [12], [13], [14], [15], [16], [17], [18], [19], [20]. To reveal the inherent mechanism of an MAS, various mathematical or physical models have been introduced, including the well-known Vicsek model [1], Boid model [2], Couzin–Levin model and its variants [18]. Over the past few decades, MAS have attracted increasing attention from many different disciplines, such as mathematics, physics, biology, sociology and engineering science [21], [22], [23], [24].
Consensus is a fundamental phenomenon in nature. Over the last decade, the consensus of MAS has been intensively investigated in the engineering sciences [4], [5], [6], [7], [8], [9]. Normally, consensus is defined as a general agreement among all members of a given group or community, each of which exercises some discretion in decision making and in its interactions with other agents. In 2003, Jadbabie and colleagues investigated the consensus of the linearized Vicsek model [4]. Following this line, there have been numerous results reported and several effective approaches proposed over the past few years, including reduction to absurdity [6], [11], matrix analysis [9], convex analysis [16], the construction of Lyapunov functions [13], and graph theory [14], [15].
Recently, the cluster synchronization of complex networks has aroused wide interest in various disciplines. For example, Wu et al. further explored the cluster synchronization of linearly coupled complex networks via pinning control in [21]. However, the study of cluster synchronization can be traced back at least to the cluster synchronization of coupled chaotic oscillators in [22]. Inspired by the cluster synchronization phenomenon in complex networks, this paper aims to further investigate the cluster consensus of discrete-time MAS. In the remainder of this paper, cluster consensus will mean that an MAS consists of multiple subgroups where the consensus can be achieved in each subgroup. In fact, cluster consensus is a more general concept in comparison with traditional consensus. Moreover, cluster consensus is also a fundamental phenomenon in nature and human society, such as the cluster formation of personal opinions, the pattern formation of bacteria colonies, and the emergence of subgroups in a flock of birds or a school of fish [25], [26], [27], [28].
Quite different from the traditional analysis approaches of MAS, this paper introduces the theory of Markov chains to deal with the cluster consensus of discrete-time MAS. Based on a simple discrete-time MAS model, it is very interesting to ask the following two challenging fundamental questions for the cluster consensus of a discrete-time MAS: (i) How to determine the clusters in such an MAS? (ii) What conditions can guarantee the cluster consensus of such an MAS? This paper gives a positive answer to the above two fundamental questions.
The rest of the paper is organized as follows. Section 2 briefly introduces several necessary preliminaries on graph theory and nonnegative matrices and formulates the fundamental problem. Based on the theory of nonnegative matrix analysis and the theory of Markov chains, several cluster consensus criteria are obtained in Section 3. In Section 4, numerical simulations are also given to validate the effectiveness of the proposed cluster consensus criteria. Finally, some concluding remarks are drawn in Section 5.
Section snippets
Preliminaries on graph theory and nonnegative matrices
Normally, a graph is defined by two sets and , where is the set of nodes and is the set of edges. For different nodes , if for each , then there exists a path from node to node with length . If , then there exists a self-loop at node . For graph , if there exists at least one path from any node to any node , then this graph is called strongly connected. Given graphs with the same set of vertices
Main results
To begin with, several necessary lemmas are given in the following.
Lemma 1 Consider a sequence of positive integers satisfying . If , then there exists some such that holds for any .
Proof Denote . Obviously, is monotonous decreasing with respect to . Since , there exists some integer satisfying . Moreover, there exist integers such that That is, one has
Numerical simulations
Consider the fixed topology in Fig. 1, the stochastic matrix is described by where are random variables with distribution , in which and are the uniform distribution defined in [1], [2].
According to the cluster factorization Algorithm 1, the above 6 agents can be classified into the following three clusters: .
Define
Concluding remarks
This paper has further investigated the cluster consensus of a discrete-time MAS with several different subgroups. Two cluster consensus criteria are deduced for the discrete-time MAS with fixed and switching topology by using Markov chains and nonnegative matrix analysis, respectively. Moreover, numerical simulations are also given to verify the effectiveness of the proposed criteria. It sheds some light on the potential engineering applications for the proposed theoretical analysis approaches
Acknowledgments
This work was supported by the National Natural Science Foundation of China under Grants 60821091, 60772158, 11072254 and 61025017, the National Basic Research (973) Program of China under Grant 2007CB310805, and the Australian Research Council Future Fellowships under Grant FT0992226 and Discovery Scheme under Grant DP0986376.
References (28)
- et al.
Structure identification of uncertain general complex dynamical networks with time delay
Automatica
(2009) - et al.
Consensus problems in discrete-time multiagent systems with fixed topology
Journal of Mathematical Analysis and Applications
(2006) - et al.
Pinning adaptive synchronization of a general complex dynamical network
Automatica
(2008) - et al.
Novel type of phase transition in a system of self-propelled particles
Physical Review Letters
(1995) Flocks, herds, and schools: a distributed behavior model
Computer Graphics
(1987)Products of indecomposable, aperiodic, stochastic matrices
Proceedings of the American Mathematical Society
(1963)- et al.
Coordination of groups of mobile autonomous agents using nearest neighbor rules
IEEE Transactions on Automatic Control
(2003) - et al.
Agreeing asynchronously
IEEE Transactions on Automatic Control
(2008) Coordination collective motion of groups of autonomous mobile robots: analysis of Vicsek’s model
IEEE Transactions on Automatic Control
(2004)- V.D. Blondel, J.M. Hendrickx, A. Olshevsky, J.N. Tsitsiklis, Convergence in multiagent coordination, consensus, and...