# Comments on “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rul

968

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 52, NO. 5, MAY 2007

Comments on “Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules”

Dimitri P. Bertsekas and John N. Tsitsiklis

closely related to our work in [1], [5], and [6]. Finally, let us note that [3] contains some additional contributions (a continuous-time variant, a discussion of graph Laplacians, and a discussion of whether convergence can be established using a quadratic Lyapunov function). However, these topics are outside the scope of this note.

Abstract—We clarify the relation between the model and the convergence results of Jadbabaie et al. to those of Bertsekas et al. We show that the update equations in Jadbabaie et al. are a special case of those in Bertsekas et al. Furthermore, the main convergence results in Sections II and III of Jadbabaie et al. are essentially the same as those derived earlier in Bertsekas et al. Index Terms—Agreement algorithm, consensus, distributed systems.

II. THE MODEL OF BERTSEKAS ET AL. Consider a set N = f1; . . . ; ng of agents that try to reach agreement on a common scalar value by exchanging tentative values, and combining them by forming convex combinations. In particular, each agent i starts with a scalar value xi (0). The vector x(t) = (x1 (t); . . . ; xn (t)), with the values held by the agents at time t, is updated according to the equation x(t + 1) = A(t)x(t), where A(t) is a stochastic matrix with entries aij (t). In more detail, let Tij be the set of times at which agent i receives a message from agent j , containing the value of xj (t), which is used by i to update the value of xi (t). We use the convention that t 2 Tii for every i and t. The update equation is of the form

n j =1

I. INTRODUCTION In the 1980s, [1], [5], and [6] studied various models of distributed asynchronous iterations, motivated by the contexts of parallel computation, distributed optimization, and distributed signal processing. An important “subroutine” in that context was the “agreement algorithm” (see [1, Secs. 7.3 and 7.7]), whereby a set of agents reach consensus on a common value by forming convex combinations of their current values and possibly outdated values possessed by their neighbors. A convergence analysis was provided at the time, including examples delineating how convergence to consensus might fail in the absence of certain assumptions on the communication delays, or on the time between consecutive processor communications (see, e.g., [1, Ex. 1.2, p. 485], and [1, Exer. 3.1, p. 517]). Historically, the idea of reaching consensus through repeated averaging was introduced earlier by De Groot [2], for a structured, time-invariant, and synchronous environment. In the absence of communication delays, convergence conditions for the time-varying case were provided by Chatterjee and Seneta [4], although without making a connection between their conditions and more primitive assumptions on the agents’ behavior (e.g., on the frequency of interagent communications, or on the connectivity properties of various graphs describing these communications). From a technical point of view, [2] and [4], as well as subsequent works in this area, were building on a large body of work on Markov chains, ergodicity, and the convergence of products of stochastic matrices. In recent years, several papers have appeared that propose and analyze various consensus algorithms of a similar ?avor. The motivation for these works has come from diverse contexts, such as multiagent coordination and ?ocking. For example, [3] aimed at providing a theoretical explanation for the observed convergence behavior in an earlier simulation study [7] of autonomous agent behavior. Interestingly, however, the resulting mathematical models and questions turned out to be closely related to those in earlier works. As the relation of the more recent works with [1], [5], and [6] has not been suf?ciently elucidated in the recent literature, we think it is important to clarify it. Rather than attempting a survey paper, aimed at covering the quickly growing recent literature, we will limit ourselves to a discussion of the paper [3], which has received considerable attention and is also most

xi (t + 1) =

aij (t)xj (t);

(1)

Manuscript received June 16, 2006; revised October 25, 2006 and January 9, 2007. This work was supported by the National Science Foundation under Contract ECS-0312921. The authors are with the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139 USA (e-mail: dimitrib@mit.edu; jnt@mit.edu). Digital Object Identi?er 10.1109/TAC.2007.895885

where the coef?cients aij (t) satisfy i) aij (t) 0, 8 i, j , t; ii) n=1 aij (t) = 1, 8 i, t; j iii) aij (t) = 0, 8 i, j , t 62 Tij . The update (1) corresponds to a simpli?ed version of [5, eqs. (2.1)–(2.4), p. 804]. The model in [5] is more general along the following dimensions: it allows messages to incur delays before reaching their destination, and also allows for an additional exogenous input in the right-hand side of (1). Our formulation involves a subset D of the set of agents. Formally, this can be any subset that happens to satisfy Assumption 1 below. Intuitively, it is to be interpreted as a set of agents i for which xi (0) will have a long-term effect on the limit of every xj (t). (The elements of D are called “computing processors” in [5] and “distinguished processors” in [1].) We de?ne E (t) as the set of ordered pairs (j; i) such that aij (t) > 0. Thus, an “edge” (j; i) 2 E (t) indicates a communication from j to i at time t, that is taken into account when forming the updated value xi (t + 1). Accordingly, (N; E (t)) is a directed graph indicating the in?uences between agents at time t (the “communication graph”). Let E be the set of (i; j ) such that (i; j ) 2 E (t) for in?nitely many t. Assumption 1: a) The set D is nonempty. b) There is some > 0 with the following property: if (j; i) 2 E (t), then aij (t) . c) There exists some B such that for every t, we have E (t + 1) [ 1 1 1 [ E (t + B ) = E . d) The graph (N; E ) contains a directed path from every i 2 D to every j 2 N . (In particular, if D = N , then (N; E ) is strongly connected.) Assumption 1 is a special case of [5, Ass. 2.1, 2.2, and 2.4]. (The assumptions in [5] are weaker in that they allow for communication delays, and also allow aii (t) to be zero for certain processors.) Part (c) of Assumption 1 is a rephrasing of the connectivity assumptions made in [5], which had been stated therein as follows: i) for every i; j , the set Tij is empty or in?nite; and ii) if (j; i) 2 E , then the time between consecutive transmissions from j to i is upper bounded by some B . We now present a convergence result from [5].

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 52, NO. 5, MAY 2007

969

Theorem 1: There exist nonnegative coef?cients that

1 ; . . . ; n

such

tlim xi (t) = !1

n j =1

j xj (0)

8 i;

and convergence takes place at the rate of a geometric progression. Furthermore, if j 2 D , then j > 0. Theorem 1 shows that all xi (t) converge to a common limit, resulting in asymptotic consensus. It is a special case of [5, Lemma 2.1, pp. j 805–806]. (To see this, set all the exogenous driving terms sl (k) in j [5] to zero, and identify j with 8l (0).) The proof of Lemma 2.1 was omitted from [5] as rather straightforward, but can be found in [6]. The proof of a special case of Theorem 1 was included in Sec. 7.3 of [1]. The proof of Theorem 1 (see [6, pp. 248–255, App. A]) proceeds k+nB as follows. Consider the matrix 8(k) = i=k 01 A(i). Fix a “com3 2 D . Suppose that xi (0) = 1 and that xj (0) = puting processor” i 0 for every j 6= i3 . Let Sm = fjjxj (mB ) > 0g and note that S0 = fi3 g. Note that if a processor’s value is positive, it remains positive in the future, which implies that Sm is a subset of Sm+1 . If Sm 6= N , then, by Assumption 1, there is a communication from some j 2 Sm to some l 62 Sm , at some time in the interval fmB; . . . ; (m + 1)B 0 1g. It follows that the cardinality of Sm+1 exceeds that of Sm . This shows that Sn = N , i.e., xj (nB ) > 0 for all j 2 N . It follows that all entries in the i3 th column of 8(0) are positive. A more careful bookkeeping actually shows that all entries of 8(0) are bounded below by some > 0 that only depends on n and the constant in Assumption 1. More generally, this argument shows that for every k , the matrix 8(k) “is a stochastic matrix with the property that all entries in some column (corresponding to any computing processor) are positive and bounded away from zero by a constant > 0 that does not depend on k ” [6, p. 253]. Using this fact, it is not hard to show (this is a standard argument in Markov chain theory) that t =1 8(knB ) converges, as t ! 1, k to a matrix with equal rows. This readily implies the convergence of t A(k) to a matrix with equal rows, i.e., asymptotic consensus. k=1

Reference [3] establishes convergence to consensus under Assumption 2 [3, Th. 2]. Given the previous discussion, this convergence result is a special case of the results in [5] (cf. Theorem 1 above), except for the difference between Assumptions 1(c)–(d) and Assumption 2. In particular, [5] requires (N; E (t + 1) [ 1 1 1 [ E (t + B )) to be the same strongly connected graph for all t, whereas [3] allows it to change with t. It turns out that this “same strongly connected graph” restriction is not used in the proof of Theorem 1 given in [6]. (This should also be clear from the proof outline given above, at the end of Section II.) The same comments apply to the generalization provided in [3, Sec. II-A], which corresponds to the choice aij (t) = 1=g , whenever (j; i) 2 E (t), j 6= i, and where g is a constant larger than n. Reference [3] then proceeds to consider a variant (“leader following”) in which one of the agents (say, agent 1) never updates its own variable, but indirectly in?uences all of the other agents. This {corresponds} to the model of [5], with D = f1g. Convergence to consensus on the initial value of agent 1 [3, Th. 4] is again covered by the results of [5] (Theorem 1). Once more, the connectivity assumption in [3] is slightly weaker (in [3], E (t + 1) [ 1 1 1 [ E (t + B ) is not required to be the same for all t), but the convergence proof (the proof of Theorem 1) goes through, unaffected by this weaker assumption.

IV. CONCLUSION In summary, the relation between the results in [1], [5], [6] and the convergence results in [3, Secs. II and III] are as follows. a) The update equations in [3] are a special case of the agreement algorithm in [5]; the latter allows a more general form of the coef?cients aij (t), and does not require symmetry in the communication pattern. b) The assumption on the intercommunication time intervals are less stringent in [3], but the proof of the result in [5] (as given in [6]) still applies.

REFERENCES

[1] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, NJ: Prentice-Hall, 1989 [Online]. Available: http://hdl.handle.net/1721.1/3719 [2] M. H. DeGroot, “Reaching a consensus,” J. Amer. Statist. Assoc., vol. 69, no. 345, pp. 118–121, 1974. [3] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Trans. Autom. Control, vol. 48, no. 6, pp. 988–1001, Jun. 2003. [4] S. Chatterjee and E. Seneta, “Towards consensus: Some convergence theorems on repeated averaging,” J. Appl. Probab., vol. 14, pp. 89–97, 1977. [5] J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE Trans. Autom. Control, vol. AC-31, no. 9, pp. 803–812, Sep. 1986. [6] J. N. Tsitsiklis, “Problems in decentralized decision making and computation” Ph.D. dissertation, Dept. Elect. Eng. Comput. Sci., Mass. Inst. Technol., Cambridge, MA, 1984 [Online]. Available: http://hdl. handle.net/1721.1/15254 [7] T. Vicsek, A. Czirok, E. Ben-Jacob, I. Cohen, and O. Schochet, “Novel type of phase transitions in a system of self-driven particles,” Phys. Rev. Lett., vol. 75, no. 6, pp. 1226–1229, Aug. 1995.

III. RELATION WITH THE MODEL OF JADBABAIE ET AL. The model in [3] is the following. At each time t, there is a set E (t) of edges (i; j ), and each agent i updates a scalar variable i (t) according to (cf. [3, eq. (2)]

i (t + 1) =

1 1 + ni (t) i (t) + j 2N (t) j (t)

(2)

where Ni (t) is the set fj 2 N jj 6= i; (j; i) 2 E (t)g of “neighbors” of i, and ni (t) is the cardinality of Ni (t). Reference [3] assumes an undirected graph, which translates to the following symmetry assumption: (i; j ) 2 E (t) if and only if (j; i) 2 E (t). Finally, [3] makes the following assumption. (The phrasing of this assumption, in [3, Th. 2], is somewhat different, but equivalent to what follows.) Assumption 2: There exists some B such that for every t, the graph with edge set E (t + 1) [ 1 1 1 [ E (t + B ) is strongly connected. Furthermore, (i; j ) 2 E (t) if and only if (j; i) 2 E (t). It can be seen that (2) is a special case of our iteration (1), with the correspondence D = f1; . . . ; ng, xi (t) = i (t) and, aij (t) = 1=(1 + ni (t)) for every j 6= i such that (j; i) 2 E (t). Note that our Assumption 1(b) is satis?ed with = 1=n.