On the cluster consensus of discrete-time multi-agent systems

https://doi.org/10.1016/j.sysconle.2011.04.009Get rights and content

Abstract

Nowadays, multi-agent systems (MAS) are ubiquitous in the real world. Consensus is a fundamental natural phenomenon. Over the past decade, consensus of MAS has received increasing attention from various disciplines. This paper aims to further investigate a novel kind of cluster consensus of MAS with several different subgroups. Based on Markov chains and nonnegative matrix analysis, two novel cluster consensus criteria are obtained for MAS with fixed and switching topology, respectively. Furthermore, numerical simulations are also given to validate the effectiveness of these proposed criteria. The proposed cluster consensus criteria have some potential applications in real world engineering 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 G={V,E} is defined by two sets V and E, where V={1,2,,N} is the set of nodes and EV×V is the set of edges. For different nodes {is}s=1kV, if (is,is+1)E for each 1sk1, then there exists a path from node i1 to node ik with length k1. If (i,i)E, then there exists a self-loop at node i. For graph G, if there exists at least one path from any node iV to any node jV(ij), then this graph is called strongly connected. Given k graphs Gi={V,Ei} with the same set of vertices V

Main results

To begin with, several necessary lemmas are given in the following.

Lemma 1

Consider a sequence of positive integers {ki}i=1 satisfying kξ,kη{ki}i=1kξ+kη{ki}i=1 . If gcd{ki}i=1=1, then there exists some N such that k{ki}i=1 holds for any kN.

Proof

Denote dr=gcd{ki}i=1r. Obviously, dr is monotonous decreasing with respect to r. Since d=1, there exists some integer D satisfying gcd{ki}i=1D=1. Moreover, there exist integers {ci}i=1D such thati=1Dciki=1. That is, one has ci>0,iDciki+ci<0,iDciki=1

Numerical simulations

Consider the fixed topology in Fig. 1, the stochastic matrix A(t) is described by A(t)=(00a13(t)0a15(t)0a21(t)0000a26(t)0a32(t)0a34(t)001000000a52(t)0a54(t)00000010), where a13(t),a21(t),a32(t),a52(t) 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: V0={1,6},V1={2,4},V2={3,5}.

Define y1(t)=x1(t)x6(t),y2(t)=x2(t)

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)

  • H. Liu et al.

    Structure identification of uncertain general complex dynamical networks with time delay

    Automatica

    (2009)
  • F. Xiao et al.

    Consensus problems in discrete-time multiagent systems with fixed topology

    Journal of Mathematical Analysis and Applications

    (2006)
  • J. Zhou et al.

    Pinning adaptive synchronization of a general complex dynamical network

    Automatica

    (2008)
  • T. Vicsek et al.

    Novel type of phase transition in a system of self-propelled particles

    Physical Review Letters

    (1995)
  • C.W. Reynolds

    Flocks, herds, and schools: a distributed behavior model

    Computer Graphics

    (1987)
  • J. Wolfowitz

    Products of indecomposable, aperiodic, stochastic matrices

    Proceedings of the American Mathematical Society

    (1963)
  • A. Jadbabie et al.

    Coordination of groups of mobile autonomous agents using nearest neighbor rules

    IEEE Transactions on Automatic Control

    (2003)
  • M. Cao et al.

    Agreeing asynchronously

    IEEE Transactions on Automatic Control

    (2008)
  • A.V. Savkin

    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...
  • Y. Chen, J. Lü, Z. Lin, Consensus of discrete-time multi-agent systems with nonlinear local rules and time-varying...
  • W. Ren et al.

    Consensus seeking in multiagent systems under dynamically changing interaction topologies

    IEEE Transactions on Automatic Control

    (2005)
  • D. Angeli et al.

    Convergence speed of unsteady distributed consensus: decay estimate along the settling spanning-trees

    SIAM Journal on Control and Optimization

    (2009)
  • S. Li et al.

    Multi-agent coordination using nearest-neighbor rules: revisiting the Vicsek model

  • Cited by (0)

    View full text