# Coordination of groups of mobile autonomous agents using nearest neighbor rules

Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules?

A. Jadbabaie, J. Lin and A. S. Morse Center for Computational Vision and Control Department of Electrical Engineering Yale University, New Haven, CT 06520 USA March 4, 2002 Revised July 15, 2002

Abstract In a recent Physical Review Letters article, Vicsek et. al. propose a simple but compelling discrete-time model of n autonomous agents {i.e., points or particles} all moving in the plane with the same speed but with di?erent headings. Each agent’s heading is updated using a local rule based on the average of its own heading plus the headings of its “neighbors.” In their paper, Vicsek et. al. provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent’s set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function.

1

Introduction

In a recent paper [1], Vicsek et. al. propose a simple but compelling discrete-time model of n autonomous agents {i.e., points or particles} all moving in the plane with the same speed but with di?erent headings. Each agent’s heading is updated using a local rule based on the average of its own heading plus the headings of its “neighbors.” Agent i’s neighbors at time t, are those agents which are either in or on a circle of pre-speci?ed radius r centered at agent i’s current position. The Vicsek model turns out to be a special version of a model introducted previously by Reynolds [2] for simulating visually satisfying ?ocking and schooling behaviors for the animation industry. In their paper, Vicsek et. al. provide a variety of interesting simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent’s set

?

This research was supported by DARPA under its SEC program and by the NSF under its KDI/LIS initiative.

of nearest neighbors change with time as the system evolves. In this paper we provide a theoretical explanation for this observed behavior. There is a large and growing literature concerned with the coordination of groups of mobile autonomous agents. Included here is the work of Czirok et al. [3] who propose one-dimensional models which exhibit the same type of behavior as Vicsek’s. In [4, 5], Toner and Tu construct a continuous ”hydrodynamic” model of the group of agents, while other authors such as Mikhailov and Zanette [6] consider the behavior of populations of self propelled particles with long range interactions. Schenk et al. determined interactions between individual self-propelled spots from underlying reaction-di?usion equation [7]. Meanwhile in modeling biological systems, Gr¨ unbaum and Okubo use statistical methods to analyze group behavior in animal aggregations. In addition to these modelling and simulation studies, research papers focusing on the detailed mathematical analysis of emergent behaviors are beginning to appear. For example, Lui et al. [8] use Lyapunov methods and Leonard et al. [9] and Olfati and Murray [10] use potential function theory to understand ?ocking behavior while Fax and Murray [11] and Desai et. al. [12] employ graph theoretic techniques for the same purpose. The one feature which sharply distinguishes previously analyses from that undertaken here is that the latter explicitly takes into account possible changes in nearest neighbors over time, whereas the former do not. Changing nearest neighbor sets is an inherent property of the Vicsek model and in the other models we consider. To analyze such models, it proves useful to appeal to well-known results [13, 14] characterizing the convergence of in?nite products of certain types of non-negative matrices. The study of in?nite matrix products is ongoing [15, 16, 17, 18, 19, 20] and is undoubtedly producing results which will ?nd application in the theoretical study of emergent behaviors. Vicsek’s model is set up in Section 2 as a system of n simultaneous, one-dimensional recursion equations, one for each agent. A family of simple graphs on n vertices is then introduced to characterize all possible neighbor relationships. Doing this makes it possible to represent the Vicsek model as an n-dimensional switched linear system whose switching signal takes values in the set of indices which parameterize the family of graphs. The matrices which are switched within the system turn out to be non-negative with special structural properties. By exploiting these properties and making use of a classical convergence result due to Wolfowitz [13], we prove that all n agents’ headings converge to a common steady state heading provided the n agents are all “linked together” via their neighbors with su?cient frequency as the system evolves. The model under consideration turns out to provide a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function. In Section 2.2 we de?ne the notion of an average heading vector in terms of graph Laplacians [21] and we show how this idea leads naturally to the Vicsek model as well as to other decentralized control models which might be used for the same purposes. We propose one such model which assumes each agent knows an upper bound on the number of agents in the group, and we explain why this model has the convergence properties similar to Vicsek’s. In Section 3 we consider a modi?ed version of Vicsek’s discrete-time system consisting of the same group of n agents, plus one additional agent, labelled 0, which acts as the group’s leader. Agent 0 moves at the same constant speed as its n followers but with a ?xed heading θ0 . The ith follower updates its heading just as in the Vicsek model, using the average of its own heading plus the headings of its neighbors. For this system, each follower’s set of neighbors can also include 2

the leader and does so whenever the leader is within the follower’s neighborhood de?ning circle of radius r. We prove that the headings of all n agents must converge to the leader’s provided all n agents are “ linked to their leader” together via their neighbors frequently enough as the system evolves. Finally we develop a continuous-time analog of this system and prove under condition more mild than imposed in the discrete-time case, that the headings of all n agents again converge to the heading of the group’s leader.

2

Leaderless Coordination

The system studied by Vicsek et. al. in [1] consists of n autonomous agents {e.g., points or particles}, labelled 1 through n, all moving in the plane with the same speed but with di?erent headings1 . Each agent’s heading is updated using a simple local rule based on the average of its own heading plus the headings of its “neighbors.” Agent i’s neighbors at time t, are those agents which are either in or on a circle of pre-speci?ed radius r centered at agent i’s current position. In the sequel Ni (t) denotes the set of labels of those agents which are neighbors of agent i at time t. Agent i’s heading, written θi , evolves in discrete-time in accordance with a model of the form θi (t + 1) =< θi (t) >r where t is a discrete-time index taking values in the non-negative integers {0, 1, 2, . . .}, and < θi (t) >r is the average of the headings of agent i and agent i’s neighbors at time t; that is ? ? 1 ?θi (t) + < θi (t) >r = θj (t)? 1 + ni (t)

j ∈Ni (t)

(1)

(2)

where ni (t) is the number of neighbors of agent i at time t. Here and elsewhere in this paper, headings are represented as real numbers between ?∞ and ∞. We could also represent headings as numbers between 0 and 2π without changing any of the results which follow; this is a consequence of the fact that if all headings are between 0 and 2π before an averaging step, they will all be between 0 and 2π after averaging. The explicit form of the update equations determined by (1) and (2) depends on the relationships between neighbors which exist at time t. These relationships can be conveniently described by a simple, undirected graph2 with vertex set {1, 2, . . . , n} which is de?ned so that (i, j ) is one of the graph’s edges just in case agents i and j are neighbors. Since the relationships between neighbors can change over time, so can the graph which describes them. To account for this we will need to consider all possible such graphs. In the sequel we use the symbol P to denote a suitably de?ned set, indexing the class of all simple graphs Gp de?ned on n vertices.

The Vicsek system also includes noise input signals which we ignore in this paper. By an undirected graph G on vertex set V = {1, 2, . . . n} is meant V together with a set of unordered pairs E = {(i, j ) : i, j ∈ V} which are called G’s edges. Such a graph is simple if it has no self-loops {i.e., (i, j ) ∈ E only if i = j } or repeated edges {i.e., E contains only distinct elements}. By the valence of a vertex v of G is meant the number of edges of G which are “incident” on v where by an indicent edge on v is meant an edge (i, j ) of G for which either i = v or j = v . The adjacency matrix of G is an n × n matrix of whose ij th entry is 1 if (i, j ) is one of G’s edges and 0 if it is not.

2 1

3

The set of agent heading update rules de?ned by (1) and (2), can be written in state form. Toward this end, for each p ∈ P , de?ne Fp = (I + Dp )?1 (Ap + I ) (3)

where Ap is the adjacency matrix of graph Gp and Dp the diagonal matrix whose ith diagonal element is the valence of vertex i within the graph. Then θ(t + 1) = Fσ(t) θ(t), t ∈ {0, 1, 2, . . .} (4)

where θ is the heading vector θ = [ θ1 θ2 . . . θn ] and σ : {0, 1, . . .} → P is a switching signal whose value at time t, is the index of the graph representing the agents’ neighbor relationships at time t. A complete description of this system would have to include a model which explains how σ changes over time as a function of the positions of the n agents in the plane. While such a model is easy to derive and is essential for simulation purposes, it would be di?cult to take into account in a convergence analysis. To avoid this di?culty, we shall adopt a more conservative approach which ignores how σ depends on the agent positions in the plane and assumes instead that σ might be any switching signal in some suitably de?ned set of interest. Our goal is to show for a large class of switching signals and for any initial set of agent headings that the headings of all n agents will converge to the same steady state value θss . Convergence of the θi to θss is equivalent to the state vector θ converging to a vector of the form θss 1 where ? 1 = [ 1 1 . . . 1 ]n×1 . Naturally there are situations where convergence to a common heading cannot occur. The most obvious of these is when one agent - say the ith - starts so far away from the rest that it never acquires any neighbors. Mathematically this would mean not only that Gσ(t) is never connected3 at any time t, but also that vertex i remains an isolated vertex of Gσ(t) for all t. This situation is likely to be encountered if r is very small. At the other extreme, which is likely if r is very large, all agents might remain neighbors of all others for all time. In this case, σ would remain ?xed along such a trajectory at that value in p ∈ P for which Gp is a complete graph. Convergence of θ to θss 1 can easily be established in this special case because with σ so ?xed, (4) is a linear, time-invariant, discrete-time system. The situation of perhaps the greatest interest is between these two extremes when Gσ(t) is not necessarily complete or even connected for any t ≥ 0, but when no strictly proper subset of Gσ(t) ’s vertices is isolated from the rest for all time. Establishing convergence in this case is challenging because σ changes with time and (4) is not time-invariant. It is this case which we intend to study. Towards this end, we denote by Q the subset of P consisting of the indices of the connected graphs in {Gp : p ∈ P}. Our ?rst result establishes the convergence of θ for the case when σ takes values only in Q. Theorem 1 Let θ(0) be ?xed and let σ : {0, 1, 2, . . .} → P be a switching signal satisfying σ (t) ∈ Q, t ∈ {0, 1, . . .}. Then lim θ(t) = θss 1 (5)

t→∞

where θss is a number depending only on θ(0) and σ .

3 A simple graph G with vertex set V = {1, 2, . . . , n} and edge set E is connected if has a “path” between each distinct pair of its vertices i and j where by a path {of length m} between vertices i and j is meant a sequence of distinct edges of G of the form (i, k1 ), (k1 , k2 ), . . . (km , j ). G is complete if has a path of length one {i.e., an edge} between each distinct pair of its vertices.

4

It is possible to establish convergence to a common heading under conditions which are significantly less stringent that those assumed in Theorem 1. To do this we need to introduce several concepts. By the union of a collection of simple graphs, {Gp1 , Gp2 , . . . , Gpm }, each with vertex set V , is meant the simple graph G with vertex set V and edge set equaling the union of the edge sets of all of the graphs in the collection. We say that such a collection is jointly connected if the union of its members is a connected graph. Note that if such a collection contains at least one graph which is connected, then the collection must be jointly connected. On the other hand, a collection can be jointly connected even if none of its members are connected. It is natural to say that the n agents under consideration are linked together across a time interval [t, τ ] if the collection of graph {Gσ(t) , Gσ(t+1) , . . . , Gσ(τ ) } encounted along the interval, is jointly connected. Theorem 1 says, in essence, that convergence of all agent’s headings to a common heading is for certain provided all n agents are linked together across each successive interval of length one {i.e., all of the time}. Of course there is no guarantee that along a speci?c trajectory the n agents will be so linked. Perhaps a more likely situation, at least when r is not too small, is when the agents are linked together across contiguous intervals of arbitrary but ?nite length. If the lengths of such intervals are uniformly bounded, then in this case too convergence to a common heading proves to be for certain. Theorem 2 Let θ(0) be ?xed and let σ : {0, 1, 2, . . .} → P be a switching signal for which there exists an in?nite sequence of contiguous, non-empty, bounded, time-intervals [ti , ti+1 ), i ≥ 0, starting at t0 = 0, with the property that across each such interval, the n agents are linked together. Then

t→∞

lim θ(t) = θss 1

(6)

where θss is a number depending only on θ(0) and σ . The hypotheses of Theorem 2 require each of the collections {Gσ(ti ) , Gσ(ti +1) , . . . , Gσ(ti+1 ?1) }, i ≥ 0, to be jointly connected. Although no constraints are placed on the intervals [ti , ti+1 ), i ≥ 0, other than that they be of ?nite length, the constraint on σ is more restrictive than one might hope for. What one would prefer instead is to show that (6) holds for every switching signal σ for which there is an in?nite sequence of bounded, non-overlapping {but not necessarily contiguous} intervals across which the n agents are linked together. Whether or not this is true remains to be seen. A su?cient but not necessary condition for σ to satisfy the hypotheses of Theorem 2 is that on each successive interval [ti , ti+1 ), σ take on at least one value in Q. Theorem 1 is thus an obviously a consequence of Theorem 2 for the case when all intervals are of length 1. For this reason we need only develop a proof for Theorem 2. To do this we will make use of certain structural properties of the Fp . As de?ned, each Fp is square and non-negative, where by a non-negative matrix is meant a matrix whose entries are all non-negative. Each Fp also has the property that its row sums all equal 1 {i.e., Fp 1 = 1}. Matrices with these two properties are called stochastic [22]. The Fp have the additional property that their diagonal elements are all non-zero. For the case when p ∈ Q {i.e., when Gp is connected}, it is known that (I + Ap )m becomes a matrix with all positive entries for m su?ciently large [22]. It is easy to see that if (I + Ap )m has all positive m . Such (I + A ) and F are examples of “primitive matrices” where by entries, then so does Fp p p a primitive matrix is meant any square, non-negative matrix M for which M m is a matrix with 5

all positive entries for m su?ciently large [22]. It is known [22] that among the n eigenvalues of a primitive matrix, there is exactly one with largest magnitude, that this eigenvalue is the only one possessing an eigenvector with all positive entries, and that the remaining n ? 1 eigenvalues are all strictly smaller in magnitude than the largest one. This means that for p ∈ Q, 1 must be Fp ’s largest eigenvalue and all remaining eigenvalues must lie within the open unit circle. As i = 1c for some row vector a consequence, each such Fp must have the property that limi→∞ Fp p cp . Any stochastic matrices M for which limi→∞ M i is a matrix of rank 1 is called ergodic [22]. Primitive stochastic matrices are thus ergodic matrices. To summarize, each Fp is a stochastic matrix with positive diagonal elements and if p ∈ Q then Fp is also primitive and hence ergodic. The crucial convergence result upon which the proof of Theorem 2 depends is classical [13] and is as follows. Theorem 3 (Wolfowitz) Let M1 , M2 , . . . , Mm be a ?nite set of ergodic matrices with the property that for each sequence Mi1 , Mi2 , . . . , Mij of positive length, the matrix product Mij Mij ?1 · · · Mi1 is ergodic. Then for each in?nite sequence , Mi1 , Mi2 , . . . there exists a row vector c such that

j →∞

lim Mij Mij ?1 · · · Mi1 = 1c

The ?niteness of the set M1 , M2 , . . . , Mm is crucial to Wolfowitz’s proof. This ?niteness requirement is also the reason why we’ve needed to assume contiguous, bounded intervals in the statement of Theorem 2. In order to make use of Theorem 3, we need a few facts concerning products of the types of matrices we are considering. First we point out that the class of n × n stochastic matrices with positive diagonal elements is closed under matrix multiplication. This is because the product of two non-negative matrices with positive diagonals is a matrix with the same properties and because the product of two stochastic matrices is stochastic. Second we will use the following key result4 . Lemma 1 Let {p1 , p2 , . . . , pm } be a set of indices in P for which {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection of graphs. Then the matrix product Fp1 Fp2 · · · Fpm is ergodic. Proof of Theorem 25 : Let T denote the least upper bound on the lengths of the intervals [ti , ti+1 ), i ≥ 0. By assumption T < ∞. Let Φ(t, t) = I, t ≥ 0, and Φ(t, τ ) = Fσ(t?1) · · · Fσ(1) Fσ(τ ) , t > τ ≥ 0. Clearly θ(t) = Φ(t, 0)θ(0). To complete the theorem’s proof, it is therefore enough to show that

t→∞ ?

lim Φ(t, 0) = 1c

?

(7)

for some row vector c since this would imply (6) with θss = cθ(0). In view of Lemma 1, the constraints on σ imply that each such matrix product Φ(tj +1 , tj ), j ≥ 0, is ergodic. Moreover the

We are indebted to Marc Artzrouni, University of Pau, France for his help with the proof of an earlier version of this lemma. 5 The authors thank Daniel Liberzon for pointing out a ?aw in the original version of this proof, and Sean Meyn for suggesting how to ?x it.

4

6

set of possible Φ(tj +1 , tj ), j ≥ 0, must be ?nite because each Φ(tj +1 , tj ) is a product of at most T matrices from {Fp : p ∈ P} which is a ?nite set. But Φ(tj , 0) = Φ(tj , tj ?1 Φ(tj ?1 , tj ?2 ) · · · Φ(t1 , t0 ). Therefore by Theorem 3, lim Φ(tj , 0) = 1c (8)

j →∞

For each t ≥ 0, let jt be the largest non-negative integer such that tjt ≤ t. Then Φ(t, 0) = Φ(t, tjt )Φ(tjt , 0) and Φ(t, tjt )1 = 1 so Φ(t, 0) ? 1c = Φ(t, tjt )(Φ(tjt , 0) ? 1c) (9)

Note that t ?→ Φ(t, tjt ) is a bounded function because Φ(t, tjt ) is the product of at most T ? 1 matrices Fp which come from a bounded set. Moreover (Φ(tjt , 0) ? 1c) → 0 as t → ∞ because of (8). From this and (9) it follows that (Φ(t, 0) ? 1c) → 0 as t → ∞. Therefore (7) holds. To prove Lemma 1 we shall make use of the standard partial ordering ≥ on n × n non-negative matrices by writing B ≥ A whenever B ? A is a non-negative. Let us note that if A is a primitive matrix and if B ≥ A, then B is primitive as well. Lemma 1 is a simple consequence of the following result. Lemma 2 Let m ≥ 2 be a positive integer and let A1 , A2 , . . . Am be non-negative n × n matrices. Suppose that the diagonal elements of all of the Ai are positive and let ? and ρ denote the smallest and largest of these respectively. Then A1 A2 · · · Am ≥ ?2 2ρ

(m?1)

(A1 + A2 + · · · + Am )

(10)

Proof: Set δ =

?2 2ρ .

It will be shown by induction that A1 A2 · · · Ai ≥ δ (i?1) (A1 + A2 + · · · + Ai ) (11)

holds for i ∈ {2, 3, . . . , m}. Towards this end note that it is possible to write each Ai as Ai = ?I + Bi where Bi is non-negative. Then for any j, k ∈ {1, 2, . . . , m}, Aj Ak = (?I + Bj )(?I + Bk ) = ?2 I + ?(Bj + Bk ) + Bj Bk Hence Aj Ak ≥ ?2 I + ?(Bj + Bk ) ≥ ?2 I + ?2 (Bj + Bk ) = δ ((ρI + Bj ) + (ρI + Bk )) 2ρ

Since (ρI + Bj ) ≥ Aj and (ρI + Bk ) ≥ Ak it follows that Aj Ak ≥ δ (Aj + Ak ), ?j, k ∈ {1, 2, . . . , m} Setting j = 1 and k = 2 proves that (11) holds for i = 2. If m = 2, the proof is complete. Now suppose that m > 2 and that (11) holds for i ∈ {2, 3, . . . l} where l is some integer in {2, 3, . . . , m ? 1}. Then A1 A2 · · · Al+1 = (A1 · · · Al )Al+1 so by the inductive hypothesis, A1 A2 · · · Al+1 ≥ δ (l?1) (A1 + A2 + · · · + Al )Al+1 7 (13) (12)

But using (12) l times we can write (A1 + A2 + · · · + Al )Al+1 ≥ δ {(A1 + Al+1 ) + (A2 + Al+1 ) + · · · + (Al + Al+1 )} Thus (A1 + A2 + · · · + Al )Al+1 ≥ δ (A1 + A2 + · · · + Al+1 ) This and (13) imply that (11) holds for i = l + 1. Therefore, by induction (11) is true for all i ∈ { 2, 3, . . . , m }. Proof of Lemma 1: Set F = (I + D)?1 (I + A) where A and D are respectively is the adjacency matrix and diagonal valence matrix of the union of the collection of graphs {Gp1 , Gp2 , . . . , Gpm }. Since the collection is jointly connected, its union is connected which means that F is primitive. By Lemma 2 Fp1 Fp2 · · · Fpm ≥ γ (Fp1 + Fp2 + · · · + Fpm ) (14) where γ is a positive constant depending on the matrices in the product. Since for i ∈ {1, 2, . . . , m}, Fpi = (I + Dpi )?1 (I + Api ) and D ≥ Dpi , it must be true that Fpi ≥ (I + D)?1 (I + Api ), i ∈ {1, 2, . . . , m}. From this and (14) it follows that Fp1 Fp2 · · · Fpm ≥ γ (I + D)?1 (mI + Ap1 + Ap2 + · · · + Apm ) But Ap1 + Ap2 + · · · + Apm ≥ A and mI ≥ I so Fp1 Fp2 · · · Fpm ≥ γF Since the product Fp1 Fp2 · · · Fpm is bounded below by a primitive matrix, namely γF , the product must be primitive as well. Since Fp1 Fp2 · · · Fpm is also a stochastic matrix, it must therefore be ergodic. (15)

2.1

Quadratic Lyapunov Functions

As we’ve already noted, Fp 1 = 1, p ∈ P . Thus span {1} is an Fp -invariant subspace. From this and standard existance conditions for solutions to linear algebraic equations, it follows that for any (n ? 1) × n matrix P with kernel spanned by 1, the equations ?p P, p ∈ P P Fp = F ?p , p ∈ P , and moreover that have unique solutions F ?p , spectrum Fp = {1} ∪ spectrum F p∈P (17) (16)

As a consequence of (16) it can easily be seen that for any sequence of indices p0 , p1 , . . . pi in P , ?p F ? ? F i pi?1 · · · Fp0 P = P Fpi Fpi?1 · · · Fp0 (18)

Since P has full row rank and P 1 = 0, the convergence of a product of the form Fpi Fpi?1 · · · Fp0 to ?p F ? ? 1c for some row vector c, is equivalent to convergence of the corresponding product F i pi?1 · · · Fp0 to the zero matrix. Thus, for example, if p0 , p1 , . . . is an in?nite sequence of indices in Q, then, in view of Theorem 3, ?p F ? ? lim F (19) i pi?1 · · · Fp0 = 0

i→∞

8

Some readers might be tempted to think, as we ?rst did, that the validity of (19) could be established ?p in the product share a common quadratic Lyapunov function. More directly by showing that the F precisely, (19) would be true if there were a single positive de?nite matrix M such that all of the ?p M F ?p ? M, p ∈ Q were negative de?nite. Although each F ?p , p ∈ Q can easily be shown matrices F to be discrete-time stable, there are classes of Fp for which that no such common Lyapunov matrix M exists. While we’ve not been able to construct a simple analytical example which demonstrates this, we have been able to determine, for example, that no common quadratic Lyapunov function exists for the class of all Fp whose associated graphs have 10 vertices and are connected. One can verify that this is so by using semide?nite programming and restricting the check to just those connected graphs on 10 vertices with either 9 or 10 edges. It is worth noting that existence of a common quadratic Lyapunov function for all discrete time stable m × m matrices M1 , M2 , . . . in some given ?nite set M, is a much stronger condition than is typically needed to guarantee that all in?nite products of the Mi converge to zero. It is known [23] that convergence to zero of all such in?nite products is in fact equivalent to the “joint spectral radius” of M being strictly less than 1 where by joint spectral radius of M is meant

1 k

ρM := lim sup

k→∞

Mi1 ∈M Mi2 ∈M

max

max · · · max ||Mi1 Mi2 · · · Mik ||

Mik ∈M

Here || · || is any norm on the space of real m × m matrices. It turns out that ρM does not depend on the choice of norm because all norms on a ?nite-dimensional space are equivalent. On the other hand, a “tight” su?cient condition for the existence of a common quadratic Lyapunov function for the matrices in M, is ρM ∈ [0, √1 ) [24]. This condition is tight in the sense that one can ?nd a m ?nite set of m × m matrices with joint spectral radius ρ = √1 , whose in?nite products converge m to zero despite the fact that there does not exist common quadratic Lyapunov function for the set. From this one can draw the conclusion that sets of matrices with “large” m are not likely to possess a common quadratic, even though all in?nite products of such matrices converge to zero. This can in turn help explain why it has proved to be necessary to go as high as n = 10 to ?nd a case where a common quadratic Lyapunov function for a family of Fp does not exist.

2.2

Generalization

It is possible to interpret the Vicsek model analyzed in the last section as the closed-loop system which results when a suitably de?ned decentralized feedback law is applied to the n-agent heading model θ(t + 1) = θ(t) + u(t) (20) with open-loop control u. To end up with the Vicsek model, u would have to be de?ned as u(t) = ?(I + Dσ(t) )?1 e(t) where e is the average heading error vector e(t) = Lσ(t) θ(t) and, for each p ∈ P , Lp is the symmetric matrix Lp = Dp ? Ap 9 (23)

?

(21)

(22)

known in graph theory as the Laplacian of Gp [21, 25]. It is easily veri?ed that equations (20) to (23) do indeed de?ne the Vicsek model. We’ve elected to call e the average heading error because if e(t) = 0 at some time t, then the heading of each agent with neighbors at that time will equal the average of the headings of its neighbors. In the present context, Vicsek’s control (21) can be viewed as a special case of a more general decentralized feedback control of the form

1 u(t) = ?G? σ (t) Lσ (t) θ (t)

(24)

where for each p ∈ P , Gp is a suitably de?ned, nonsingular diagonal matrix with ith diagonal i . This, in turn, is an abbreviated description of a system of n individual agent control element gp laws of the form ? ? 1 ? ui (t) = ? ni (t)θi (t) + θj (t)? , i ∈ {1, 2, . . . , n} (25) gi (t)

j ∈Ni (t) i where for i ∈ {1, 2, . . . , n}, ui (t) is the ith entry of u(t) and gi (t) = gσ (t) . Application of this control to (20) would result in the closed-loop system 1 θ(t + 1) = θ(t) ? G? σ (t) Lσ (t) θ (t) ?

(26)

?, Note that the form of (26) implies that if θ and σ were to converge to a constant values θ ? ? and σ ? respectively, then θ would automatically satisfy Lσ ? θ = 0. This means that control (24) automatically forces each agent’s heading to converge to the average of its neighbors, if agent headings were to converge at all. In other words, the choice of the Gp does not e?ect the requirement that each agent’s heading equal the average of the headings of its neighbors, if there is convergence at all. The preceding suggests that there might be useful choices for the Gp alternative to those considered by Vicsek, which also lead to convergence. One such choice turns out to be Gp = gI, p ∈ P (27)

where g is any number greater than n. Our aim is to show that with the Gp so de?ned, Theorem 2 continues to be valid. In sharp contrast with the proof technique used in the last section, convergence will be established here using a common quadratic Lyapunov function. As before, we will use the model θ(t + 1) = Fσ(t) θ(t) (28)

where, in view of the de?nition of the Gp in (27), the Fp are now symmetric matrices of the form 1 Fp = I ? Lp , g p∈P (29)

To proceed we need to review a number of well known and easily veri?ed properties of graph Laplacians relevant to the problem at hand. For this, let G be any given simple graph with n 10

vertices. Let D be a diagonal matrix whose diagonal elements are the valences of G’s vertices and write A for G’s adjacency matrix. Then, as noted before, the Laplacian of G is the symmetric matrix L = D ? A. The de?nition of L clearly implies that L1 = 0. Thus L must have an eigenvalue at zero and 1 must be an eigenvector for this eigenvalue. Surprisingly L is always a positive semide?nite matrix [25]. Thus L must have a real spectrum consisting of non-negative numbers and at least one of these numbers must be 0. It turns out that the number of connected components of G is exactly the same as the multiplicity of L’s eigenvalue at 0 [25]. Thus G is a connected graph just in case L has exactly one eigenvalue at 0. Note that the trace of L is the sum of the valences of all vertices of G. This number can never exceed (n ? 1)n and can attain this high value only for a complete graph. In any event, this property implies that the maximum eigenvalue of L is never larger that n(n ? 1). Actually the largest eigenvalue of L can never be larger than 1 n [25]. This means that the eigenvalues of g L must be smaller than 1 since g > n . From these 1 L) must all be between 0 and 1, and that properties it clearly follows that the eigenvalues of (I ? g if G is connected, then all will be strictly less than 1 except for one eigenvalue at 1 with eigenvector 1 1. Since each Fp is of the form (I ? g L), each Fp possesses all of these properties. Let σ be a ?xed switching signal with value pt ∈ Q at time t ≥ 0. What we’d like to do is to prove that as i → ∞, the matrix product Fpi Fpi?1 · · · Fp0 converges to 1c for some row vector c. As noted in the section 2.1, this matrix product will so converge just in case

i→∞

?p F ? ? lim F i pi?1 · · · Fp0 = 0

(30)

?p is the unique solution to P Fp = F ?p P, p ∈ P and P is any full rank where as in section 2.1, F (n ? 1) × n matrix satisfying P 1 = 0. For simplicity and without loss of generality we shall henceforth assume that the rows of P form a basis for the orthogonal complement of the span of e. ?, that F ?p = P Fp P , p ∈ P , and thus This means that P P equals the (n ? 1) × (n ? 1) identity I ? that each Fp is symmetric. Moreover, in view of (17) and the spectral properties of the Fp , p ∈ Q, ?p , p ∈ Q must have a real spectrum lying strictly inside of the unit circle. it is clear that each F ?p ? I ? is negative de?nite, that F ?p F ?p ? I ? is negative This plus symmetry means that for each p ∈ Q, F ? is a common discrete-time Lyapunov matrix for all such F ?p . Using this fact de?nite and thus that I it is straight forward to prove that Theorem 1 holds for system (26) provided the Gp are de?ned as in (27) with g > n. ?p is a discrete-time stability matrix for which F ?F ? ? In general, each F p p ? I is negative de?nite only if p ∈ Q. To craft a proof of Theorem 2 for the system described by (26) and (27), one needs to show that for each interval [ti , ti+1 ) on which {Gσ(ti+1 ?1) , . . . Gσ(ti +1) , Gσ(ti ) } is a jointly connected ?σ(t ) is a discrete-time stability matrix and ?σ(t ?1) · · · F ?σ(t +1) F collection of graphs, the product F i+1 i i ?σ(t ?1) · · · F ?σ(t +1) F ?σ(t ) ) (F ?σ(t ?1) · · · F ?σ(t +1) F ?σ(t ) ) ? I ? is negative de?nite. This is a direct (F i+1 i i i+1 i i consequence of the following proposition. Proposition 1 If {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection of graphs, then ?p F ? ? ? ? ? ? (F 1 p2 · · · Fpm ) (Fp1 Fp2 · · · Fpm ) ? I is a negative de?nite matrix. In the light of Proposition 1, it is clear that the conclusion Theorem 2 is also valid for the system described by (26) and (27). A proof of this version of Theorem 2 will not be given. 11

To summarize, both the Vicsek control de?ned by u = ?(I + Dσ(t) )?1 e(t) and the simpli?ed 1 control given by u = ? g e(t) achieve the same emergent behavior. While latter is much easier to analyze than the former, it has the disadvantage of not being a true decentralized control because each agent must know an upper bound {i.e., g } on the total number of agents within the group. Whether or not this is really a disadvantage, of course depends on what the models are to be used for. The proof of Proposition 1 depends on two lemmas. In the sequel, we state the lemmas, use them to prove Proposition 1, and then conclude this section with proofs of the lemmas themselves. Lemma 3 If {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection of graphs with Laplacians Lp1 , Lp2 , . . . , Lpm , then

m

kernel Lpi = span {1}

i=1

(31)

Lemma 4 Let M1 , M2 , . . . , Mm be a set of n × n real symmetric, matrices whose induced 2-norms are all less than or equal to 1. If

m

kernel (I ? Mi ) = 0

i=1

(32)

then the induced 2-norm of M1 M2 · · · Mm is less than 1.

1 Proof of Proposition 1: The de?nition of the Fp in (29) implies that I ? Fp = g Lp . Hence by Lemma 3 and the hypothesis that {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection, m

kernel (I ? Fpi ) = span {1}

i=1

(33)

We claim that

m

?? F ?p ) = 0 kernel (I i

i=1

(34)

?? F ?p )? To establish this fact, let x ? be any vector such that (I i x = 0, i ∈ {1, 2, . . . , m}. Since P ?? F ?p )P , so has independent rows, there is a vector x such that x ? = P x. But P (I ? Fpi ) = (I i 1 P (I ? Fpi )x = 0. Hence (I ? Fpi )x = ai 1 for some number ai . But 1 (I ? Fpi ) = g 1 Lpi = 0, so ai 1 1 = 0. This implies that ai = 0 and thus that (I ? Fpi )x = 0. But this must be true for all i ∈ {1, 2, . . . , m}. It follows from (33) that x ∈ span {1} and, since x ? = P x, that x ? = 0. Therefore (34) is true. ?p are all symmetric, positive semi-de?nite matrices with induced 2 - norms As de?ned, the F ?pm satisfy the ?p , F ?p , . . . , F not exceeding 1. This and (34) imply that the family of matrices F 1 2 hypotheses of Lemma 4. It follows that Proposition 1 is true. Proof of Lemma 3: In the sequel we write L(G) for the Laplacian of a simple graph G. By the intersection of a collection of simple graphs, {Gp1 , Gp2 , . . . , Gpm }, each with vertex set V , is meant 12

the simple graph G with vertex set V and edge set equaling the intersection of the edge sets of all of the graphs in the collection. It follows at once from the de?nition of a Laplacian that L(Gp ) + L(Gq ) = L(Gp ∩ Gq ) + L(Gp ∪ Gq ) for all p, q ∈ P . Repeated application of this identity to the set {Gp1 , Gp2 , . . . , Gpm } yields the relation ? ?? ? m m m?1 ? i ? Gpi + L ?Gpi+1 Gpj ? L(Gpi ) = L (35) ? ?

i=1 i=1 i=1 j =1

which is valid for m > 1. Since all matrices in (35) are positive semi-de?nite, any vector x which makes the quadratic form x {L(Gp1 )+ L(Gp2 )+ · · · + L(Gpm )}x vanish, must also make the quadratic form x L(Gp1 ∪ Gp2 ∪ · · · ∪ Gpm )x vanish. Since any vector in the kernel of each matrix L(Gpi ) has this property, we can draw the following conclusion.

m m

kernel L(Gpi ) ? kernel L

i=1 i=1

Gpi

Suppose now that {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection. Then the union Gp1 ∪ Gp2 ∪ · · · ∪ Gpm is connected so its Laplacian must have exactly span {1} for its kernel. Hence the intersection of the kernels of the L(Gpi ) must be contained in span {1}. But span {1} is contained in the kernel of each matrix L(Gpi ) in the intersection and therefore in the intersection of the kernels of these matrices as well. It follows that (31) is true. Proof of Lemma 4: In the sequel we write |x| for the 2-norm of a real n-vector x and |M | for the induced 2-norm of a real n × n matrix. Let x ∈ IRn be any real, non-zero n-vector. It is enough to show that |M1 M2 · · · Mm x| < |x| (36) In view of (32) and the assumption that x = 0, there must be a largest integer k ∈ {1, 2, . . . , m} such that x ∈ kernel (Mk ? I ). We claim that |Mk x| < |x| (37)

To show that this is so we exploit the symmetry of Mk to write x as x = α1 y1 +α2 y2 +· · ·+αn yn where α1 , α2 , . . . , αn are real numbers and {y1 , y2 , . . . , yn } is an orthonormal set of eigenvectors of Mk with real eigenvalues λ1 , λ2 , . . . λn . Note that |λi | ≤ 1, i ∈ {1, 2, . . . , n}, because |Mk | ≤ 1. Next observe that since Mk x = α1 λ1 y1 + α2 λ2 y2 + · · · + αn λn yn and Mk x = x, there must be at least one integer j such that αj λj = αj . Hence |αj λj yj | < |αj yj |. But |Mk x| = |α1 λ1 y1 | + · · · + |αj λj yj | + · · · + |αn λn yn | so |Mk x| < |α1 λ1 y1 | + · · · + |αj yj | + · · · + |αn λn yn | Moreover |α1 λ1 y1 | + · · · + |αj yj | + · · · + |αn λn yn | ≤ |α1 y1 | + · · · + |αj yj | + · · · + |αn yn | = |x| so (37) is true. In view of the de?nition of k , Mj x = x, j ∈ {k + 1, . . . , m}. From this and (37) it follows that |M1 · · · Mm x| = |M1 · · · Mk x| ≤ |M1 · · · Mk?1 ||Mk x| < |M1 · · · Mk?1 ||x|. But |M1 · · · Mk?1 | ≤ 1 because each Mi has an induced 2 norm not exceeding 1. Therefore (36) is true. 13

3

Leader Following

In this section we consider a modi?ed version of Vicsek’s discrete-time system consisting of the same group of n agents as before, plus one additional agent, labeled 0, which acts as the group’s leader. Agent 0 moves at the same constant speed as its n followers but with a ?xed heading θ0 . The ith follower updates its heading just as before, using the average of its own heading plus the headings of its neighbors. The di?erence now is that each follower’s set of neighbors can include the leader and does so whenever the leader is within the follower’s neighborhood de?ning circle of radius r. Agent i’s update rule thus is of the form ? ? 1 ?θi (t) + θj (t) + bi (t)θ0 ? (38) θi (t + 1) = 1 + ni (t) + bi (t)

j ∈Ni (t)

where as before, Ni (t) is the set of labels of agent i’s neighbors from the original group of n followers, and ni (t) is the number of labels within Ni (t). Agent 0’s heading is accounted for in the ith average by de?ning bi (t) to be 1 whenever agent 0 is a neighbor of agent i and 0 otherwise. The explicit form of the n update equations exempli?ed by (38), depends on the relationships between neighbors which exist at time t. Like before, each of these relationships can be conveniently described by a simple undirected graph. In this case, each such graph has vertex set {0, 1, 2, . . . , n} and is de?ned so that (i, j ) is one of the graph’s edges just in case agents i and j are neighbors. For this purpose we consider an agent - say i - to be a neighbor of agent 0 whenever agent 0 is a neighbor of agent i. We will need to consider all possible such graphs. In the sequel we use the ? p de?ned on vertices 0, 1, 2, . . . , n. ? to denote a set indexing the class of all simple graphs G symbol P We will also continue to make reference to the set of all simple graphs on vertices 1, 2, . . . , n. Such ? p . Thus, for p ∈ P ? , Gp now denotes the subgraph graphs are now viewed as subgraphs of the G ? p by deleting vertex 0 and all edges incident on vertex 0. obtained from G The set of agent heading update rules de?ned by (38) can be written in state form. Toward ? , let Ap denote the n × n adjacency matrix of the n-agent graph Gp and let this end, for each p ∈ P Dp be the corresponding diagonal matrix of valences of Gp . Then in matrix terms, (38) becomes θ(t + 1) = (I + Dσ(t) + Bσ(t) )?1 ((I + Aσ(t) )θ(t) + Bσ(t) 1θ0 ), t ∈ { 0, 1, 2, . . . } (39)

? is now a switching signal whose value at time t, is the index of the graph where σ : {0, 1, . . .} → P ? ? , Bp is the n × n Gp representing the agent system’s neighbor relationships at time t and for p ∈ P ? p ’s edges and 0 otherwise. diagonal matrix whose ith diagonal element is 1 if (i, 0) is one of G Much like before, our goal here is to show for a large class of switching signals and for any initial set of follower agent headings, that the headings of all n followers converge to the heading of the leader. For convergence in the leaderless case we required all n-agents to be linked together across each interval within an in?nite sequence of contiguous, bounded interevals. We will need a similar requirement in the leader following case under consideration. Let us agree to say that the n agents ? σ(t) , G ? σ(t+1) , . . . , G ? σ (τ ) } are linked to the leader across an interval [t, τ ] if the collection of graphs {G encounted along the interval is jointly connected. In other words, the n agents are linked to their leader accross an interval I just when the n + 1-member group consisting of the n agents and their leader is linked together across I . Note that for the n-agent group to be linked to its leader across 14

I does not mean that the n-agent group must be linked together across I . Nor is the n-agent group necessarily linked its leader across I when it is linked together across I . Our main result on discrete-time leader following is next. ? be a switching signal for which Theorem 4 Let θ(0) and θ0 be ?xed and let σ : {0, 1, 2, . . .} → P there exists an in?nite sequence of contiguous, non-empty, bounded, time-intervals [ti , ti+1 ), i ≥ 0, starting at t0 = 0, with the property that across each such interval, the n-agent group of followers is linked to its leader. Then lim θ(t) = θ0 1 (40)

t→∞

The theorem says that the members of the n-agent group all eventually follow their leader provided there is a positive integer T which is large enough so that the n-agent group is linked to its leader across each contiguous, non-empty time- interval of length at most T . In the sequel we outline several preliminary ideas upon which the proof of Theorem 4 depends. To begin, let us note that to prove that (40) holds is equivalent to proving that limt→∞ (t) → 0 where is the heading error vector (t) = θ(t) ? θ0 1. From (39) it is easy to deduce that the equation (t + 1) = Fσ(t) (t) ? , Fp is where for p ∈ P Fp = (I + Dp + Bp )?1 (I + Ap )

?

satis?es (41) (42)

Note that the partitioned matrices

? Fp ?p = F 0

Hp 1 , 1

? p∈P

(43)

?, are stochastic where, for p ∈ P Hp = (I + Dp + Bp )?1 Bp

?

(44)

To proceed, we need a few more ideas concerned with non-negative matrices. In the sequel we write M > N whenever M ? N is a positive matrix, where by a positive matrix is meant a matrix with all positive entries. For any non-negative matrix R of any size, we write ||R|| for the largest of the row sums of R. Note that ||R|| is the induced in?nity norm of R and consequently is sub-multiplicative. We denote by R , the matrix obtained by replacing all of R’s non-zero entries with 1s. Note that R > 0 if and only if R > 0. It is also true for any pair of n × n non-negative matrices A and B with positive diagonal elements, that AB = A B . Moreover, in view of Lemma 2, any such pair of matrices must also satisfy AB ≥ B and BA ≥ B . ? . It is possible to relate the connectedness of Let p1 , p2 , . . . , pm be a given set of indices in P ? ? ? the collection {Gp1 , Gp2 , . . . , Gpm } to properties of the matrix pairs (Fpi , Hpi 1), i ∈ {1, 2, . . . , m}. ? , the indices of the non-zero rows of Bp 1 are precisely the Let us note ?rst that for any p ∈ P ? p which are connected to vertex 0 by paths of length 1. More generally, for labels of vertices in G any integer j > 0, the indices of the non-zero rows of (I + Ap )(j ?1) Bp 1 are the labels of vertices ? p connected to vertex 0 by paths of length less than or equal to j . Hence for such j , the in G 15

(j ?1) B 1 must be the labels of vertices in the union of non-zero rows of the sum m pk k=1 (I + Apk ) ?p ,G ?p ,...,G ? pm } which are connected to vertex 0 by paths of length less than the collection {G 1 2 ?p ,G ?p ,...,G ? pm } is jointly connected, there must be a value of or equal to j . It follows that if {G 1 2 m ( j ? 1) j su?ciently large so that k=1 (I + Apk ) Bpk 1 > 0. Since any vertex in a connected graph with n + 1 vertices is reachable from any other vertex along a path of length of at most n + 1, it ?p ,G ?p ,...,G ? pm } is jointly connected, then m (I + Ap )(i?1) Bp 1 > 0, ?i > n. follows that if {G 1 2 k k k=1 Now it is easy to see from the de?nitions of the Fp and Hp in (42) and (44) respectively, that j Fp Hp 1 = (I + Ap )j Bp 1 , j ≥ 0. We have proved the following lemma.

?p ,G ?p ,...,G ? pm } is a jointly ? for which {G Lemma 5 Let {p1 , p2 , . . . , pm } be any set of indices in P 1 2 connected collection of graphs. Then

m (i?1) Fp Hpk 1 > 0, k k=1

i>n

(45)

?p de?ned by (43). Since each of these matrices is Now consider the partitioned matrices F ? and each i ≥ 1, stochastic and products of stochastic matrices are also stochastic, for each p ∈ P i ?p is stochastic. But F ? i ? (j ?1) i Fp Hp 1 j =1 Fp i ?p ? ?, F =? p∈P 0 ? p is connected, then Moreover, if G

i (j ?1) Fp Hp 1 > 0, j =1

1

i>n

(46)

? p is connected and i > n, the row sums of F i must all be because of Lemma 5. It follows that if G p less that 1. In other words, i ? ||Fp || < 1, i > n, p ∈ Q (47) The following proposition generalizes (47) and is central to the proof of Theorem 4. Proposition 2 Let T be a ?nite positive integer. There exists a positive number λ < 1, depending only on T , for which ||Fpt (48) ?Fpt ??1 · · · Fp1 || < λ ? of at length at most T possessing values q1 , q2 , . . . , qm which each for every sequence p1 , p2 , . . . pt ?∈ P ?q ,G ?q ,...,G ? qm } is a jointly connected occur in the sequence at least n + 1 times and for which {G 1 2 collection of graphs. The proof of this proposition depends on the following basic property of non-negative matrices.

16

Lemma 6 Let M1 , M2 , . . . , Mk be a ?nite sequence of n × n non-negative matrices whose diagonal entries are all positive. Suppose that M is a matrix which occurs in the sequence at least m > 0 times. Then M 1 M2 · · · Mk ≥ M m (49)

Proof: We claim that for j ≥ 1 M1 M2 · · · Mk j ≥ M j (50) provided M1 M2 · · · Mkj is a product within which M occurs at least j times. Suppose M1 M2 · · · Mk1 is a product within which M occurs at least once. Then M1 M2 · · · Mk1 = AM B where A and B are non-negative matrices with positive diagonal elements. By Lemma 2, AM B ≥ M B and M B ≥ M . Thus AM B ≥ M which proves that (50) is true for j = 1. Now suppose that (50) holds for j ∈ {1, 2, . . . i} and let M1 M2 · · · Mki+1 be a product within which M occurs at least i + 1 times. We can write M1 M2 · · · Mki+1 = AM B where A and B are non-negative matrices with positive diagonal elements and A is a product within which M occurs at least i times. By the inductive hypothesis, A ≥ M i . By Lemma 2, AM B ≥ AM . It follows that AM = A M ≥ M i M = M i+1 and thus that (50) holds for j = i + 1. By induction, (50) therefore holds for all i ∈ {1, 2, . . . , m}. Hence the lemma is true. Proof of Proposition 2: It will be enough to prove that ||Fpt ?Fpt ??1 · · · Fp1 || < 1 (51)

for every sequence p1 , p2 , . . . pt ? of length at most T possessing values q1 , q2 , . . . , qm which each ?q ,G ?q ,...,G ? qm } is a jointly connected occur in the sequence at least n + 1 times and for which {G 1 2 collection of graphs. For if this is so, then one can de?ne the uniform bound λ = max ||Fpt ?Fpt ??1 · · · Fp1 ||

S ?

where S is the set of all such sequences. Note that λ < 1 if (51) holds, because S is a ?nite set. Let p1 , p2 , . . . pt ? be a sequence of at length at most T possessing values q1 , q2 , . . . , qm which each ?q ,G ?q ,...,G ? qm } is a jointly connected occur in the sequence at least n + 1 times and for which {G 1 2 ? collection of graphs. The de?nition of the Fp in (43) implies that ? ? ? t Fpt ?j Hpj 1 ?Fpt ??1 · · · Fp1 j =1 Φt ?p?F ? ? ···F ?p = ? ? F 1 t pt ?1 0 1 ? ? ?F ?p? · · · F ?p ? where Φt ?t ? = I and Φt ?j = Fpt ?Fpt ??1 · · · Fpj +1 for j < t. Since the Fp are all stochastic, Fpt 1 t?1 must be stochastic as well. Thus to establish (51) it is su?cient to prove that

? t

Φt ?j Hpj 1 > 0

j =1

(52)

By assumption, each member of {q1 , q2 , . . . , qm } occurs in the sequence p1 , p2 , . . . pt ? at least n +1 times. For k ∈ {1, 2, . . . m}, let ik be the smallest integer such that pik = qk . Since each qk occurs at 17

least n +1 times, each qk must occur at least n times in the subsequence pik +1 , pik +2 , . . . pt ?. It follows n n from Lemma 6 and the de?nition of Φt ?j that Φt ?ik ≥ Fqk . Thus Φt ?ik Hqk 1 ≥ Fqk Hpi 1 . Since k this hold for all k ∈ {1, 2, . . . , m},

m m

Φt ?ik Hqk 1 ≥

k=1 k=1 m ?ik Hqk 1 k=0 Φt

n Fq Hqk 1 k

From this and (45) it follows that (52) is true.

> 0. But

? t ?j Hpj 1 j =1 Φt

≥

m ?ik Hqk 1, k=1 Φt

so

Proposition 2 actually implies that any ?nite product Fp1 Fp2 · · · Fpj will be a discrete-time stability matrix provided there is a set of indices {q1 , q2 , . . . qm } for which (i) each qk occurs in the ?q ,G ?q ,...,G ? qm } is a jointly connected collection set {p1 , p2 , . . . pj } at least n + 1 times and (ii) {G 1 2 ?q F ? ? of graphs. From this it is not di?cult to see that any ?nite product F 1 q2 · · · Fqm will be ergodic 6 ?q ,G ?q ,...,G ? qm } is a jointly connected collection of graphs . It is possible to use this provided {G 1 2 fact together with Wolfowitz’s theorem {Theorem 3} to devise a proof of Theorem 4, much like the proof of Theorem 2 given earlier. On the other hand, it is also possible to give a simple direct proof of Theorem 4, without using Theorem 3, and this is the approach we take. ? with the property Proof of Theorem 4: Let J denote the set of all subsets {p1 , p2 , . . . , pm } of P that {Gp1 , Gp2 , . . . , Gpm } is a jointly connected collection. The constraints on σ imply that σ (t) takes on every value in one such subset on every interval [ti , ti+1 ), i ≥ 0. Let n ? be the number of elements in J . Then for any integer i > 0 there must be at least one subset in J whose elements are each values of σ at least i times on any sequence of in ? contiguous time - intervals. Set ?i = ti(n+1)? t n , i ≥ 0 and let T the least upper bound on the lengths of the intervals, [ti , ti+1 ), i ≥ 0. By assumption, T < ∞. Let Φ(t, s) denote the state transition matrix de?ned by Φ(t, t) = I, t ≥ 0 and Φ(t, s) = Fσ(t?1) Fσ(t?2) · · · Fσ(s) , t > s ≥ 0,. Then (t) = Φ(t, 0) (0). To complete the theorem’s proof, it is therefore enough to show that

j →∞ ?

?j , t ?0 ) = 0 lim Φ(t

(53)

?j , 0) = Φ(t ?j , t ?j ?1 ) · · · Φ(t ?2 , t ?1 )Φ(t ?1 , t ?0 ). Moreover, for i ≥ 0, [t ?i , t ?i+1 ) is an interval of Clearly Φ(t length at most (n + 1)? nT on which σ (t) takes on at least n + 1 times, every value pi in some subset ?j , t ?j ?1 )|| ≤ {p1 , p2 , · · · , pm } in J . It follows from Proposition 2 and the de?nition of Φ that ||Φ(t λ, j ≥ 1 where λ is a positive number depending only on (n + 1)? nT which satis?es λ < 1. Hence ?j , 0)|| ≤ λj , j ≥ 1 from which (53) follows at once. ||Φ(t

4

Leader Following in Continuous Time

Our aim here is to study the convergence properties of the continuous-time version of the leaderfollower model discussed in the last section. We begin by noting that the update rule for agent i’s

?p it is also not di?cult to show that any ?nite product Fp1 Fp2 · · · Fp Using this fact and the structure of the F j ? p1 , G ? p2 , . . . , G ? p } is a jointly connected collection of will be a discrete-time stability matrix provided only that {G j graphs.

6

18

heading, de?ned by (38), is what results when the local feedback law ? ? 1 ?(ni (t) + bi (t))θi (t) ? ui (t) = ? θj (t) ? bi (t)θ0 ? 1 + ni (t) + bi (t)

j ∈Ni (t)

(54)

is applied to the open-loop discrete-time heading model θi (t + 1) = θi (t) + ui (t) The continuous-time analog of (55) is the integrator equation ˙i = ui θ (56) (55)

where now t takes values in the real half interval [0, ∞). On the other hand, the continuous time analog of (54) has exactly the same form as (54), except in the continuous time case, ni (t), bi (t), and θi (t) are continuous-time variables. Unfortunately, in continuous time control laws of this form can lead to chattering because neighbor relations can change abruptly with changes in agents’ positions. One way to avoid this problem is to introduce dwell time, much as was done in [26]. What this means in the present context is that each agent is constrained to change its control law only at discrete times. In particular, instead of using (54), to avoid chatter agent i would use a hybrid control law of the form ? ? 1 ?(ni (tik ) + bi (tik ))θi (t) ? ui (t) = ? θj (t) ? bi (tik )θ0 ? , t ∈ [tik , tik + τi ) 1 + ni (tik ) + bi (tik )

j ∈Ni (tik )

(57) where τi is a pre-speci?ed positive number called a dwell time and t0 , t1 , . . . is an in?nite time sequence such that ti(k+1) ? tik = τi , k ≥ 0. In the sequel we will analyze controls of this form subject to two simplifying assumptions. First we will assume that all n agents use the same dwell time which we henceforth denote by τD . Second we assume the agents are synchronized in the sense that tik = tjk for all i, j ∈ {1, 2, . . . , n} and all k ≥ 0. These assumptions enable us to write u as u = ?(I + Dσ + Bσ )?1 ((Lσ + Bσ )θ ? Bσ 1θ0 ) (58) ? , Dp , Bp and Ap are as before, Lp = Dp ? Ap is the Laplacian of Gp , and σ : [0, ∞) → P ? is where P a piecewise constant switching signal with successive switching times separated by τD time units. Application of this control to the vector version of (56) results in the closed-loop continuous-time leader-follower model ˙ = ?(I + Dσ + Bσ )?1 ((Lσ + Bσ )θ ? Bσ 1θ0 ) θ (59)

In analogy to the discrete-time case, let us agree to say that the n agents are linked to the leader accross an interval [t, τ ) between switching times t and τ , if the collection of graphs ? σ(t) , G ? σ(t+1) , . . . , G ? σ(τ ?1) } encounted along the interval, is jointly connected. Much like before, {G our goal here is to show for a large class of switching signals and for any initial set of follower agent headings, that the headings of all n followers converge to the heading of the leader. For convergence, we shall continue to require there to exist in?nite sequence of bounded, non-overlaping time-intervals across which the n-agent group is linked to its leader. However, unlike the discretetime case we shall not require this sequence of intervals to be contiguous. 19

? be a piecewise-constant Theorem 5 Let τD > 0, θ(0) and θ0 be ?xed and let σ : [0, ∞) → P switching signal whose switching times t1 , t2 , . . . satisfy ti+1 ? ti ≥ τD , i ≥ 1. If there is an in?nite sequence of bounded, non-overlaping time-intervals [tij , tij +kj ), j ≥ 1, with the property that across each such interval the n-agent group of followers is linked to its leader, then

t→∞

lim θ(t) = θ0 1

(60)

Theorem 5 states that θ will converge to θ0 1, no matter what the value of τD , so long as τD is greater than zero. This is in sharp contrast to other convergence results involving dwell time switching such as those given in [27], which hold only for su?ciently large values of τD . Theorem 5 is a more or less obvious consequence of the following lemma. Lemma 7 Let Then ||eMp t || ≤ 1, ?t ≥ 0, ? p∈P (62) ?p ,G ?p ,...,G ? pm } is ? for which {G Moreover, for each each ?nite set of indices p1 , p2 , . . . , pm in P 1 2 jointly connected, and each set of ?nite, positive times t1 , t2 , . . . , tm , ||eMpm tm · · · eMp2 t2 eMp1 t1 || < 1

? ? and for i ≥ 1, set Proof of Theorem 5: Let Mp = ?(I + Dp + Bp )?1 (Lp + Bp ), p ∈ P

Mp = ?(I + Dp + Bp )?1 (Lp + Bp ),

?

? p∈P

(61)

(63)

Ni = eMσ(ti ) (ti+1 ?ti ) From inequality (62) in Lemma 7 it follows that ||eNi || ≤ 1, i ≥ 1

(64)

(65)

By assumption there is a ?nite upper bound T on the lengths of the intervals [tij , tij +kj ) across which the n agents are linked to their leader. This and the assumption that ti+1 ? ti ≥ τD , i ≥ 0, imply that kj ≤ m, j ≥ 1, where m is the smallest positive integer such that T ≤ mτD . Let J be ?p ,G ?p ,...,G ? p } is ? of at length at most m for which {G the set of all sequences p1 , p2 , . . . pl ∈ P 1 2 l jointly connected. De?ne λ=

τ1 ∈[τD ,T ] τ2 ∈[τD ,T ]

max

max . . . max max ||eMpl τl · · · eMp2 τ2 eMp1 τ1 ||

τl ∈[τD ,T ] J

(66)

Note that λ < 1 because the inequality in (63) is strict, because J is a ?nite set, because [τD , T ] is compact and because the matrix exponentials in (66) depend continuously on the τi . In view of the de?nition of λ and the de?nitions of the Ni in (64), ||e But eNij +1 ?1 · · · eNij +1 eNij = eNij +1 ?1 · · · e

Nij +kj Nij +kj ?1

· · · eNij +1 eNij || ≤ λ, e

j≥1 · · · eNij +1 eNij , j ≥ 1

(67)

Nij +kj ?1

20

This, (65), (67) and the sub-multiplicative property of the induced in?nity norm imply that ||eNij +1 ?1 · · · eNij +1 eNij || ≤ λ, ?(t) = θ(t) ? 1θ0 and note that Set θ ˙ = ?(I + D + B )?1 (L + B )θ ? ? θ σ σ σ σ because of (59). Let Φ(t, ?) be the state transition matrix of ?(I + Dσ(t) + Bσ(t) )?1 (Lσ(t) + Bσ(t) ). ?(t) = Φ(t, 0)θ ?(0). To complete the proof it is therefore enough to show that Then θ ||Φ(tij , ti1 )|| ≤ λj ?1 , In view of the de?nitions of the Ni , Φ(tij +1 , tij ) = eNij +1 ?1 · · · eNij +1 eNij , From this and (68) it follows that ||Φ(tij +1 , tij )|| ≤ λ, j ≥ 1 But Φ(tij , t1 ) = Φ(tij , tij ?1 ) · · · Φ(ti2 , ti1 ) so ||Φ(tij , t1 )|| ≤ ||Φ(tij , tij ?1 )|| · · · ||Φ(ti2 , ti1 )|| From this and (70), it now follows that (69) is true. ? . Observe ?rst that Proof of Lemma 7: Fix t > 0 and p ∈ P Mp = Fp ? I (71) (70) j≥1 j≥1 (69) j≥1 (68)

where Fp is the matrix Fp = (I + Dp + Bp )?1 (I + Ap ). As noted previously, the partitioned matrix

? Fp ?p = F 0

Hp 1 1

(72)

originally de?ned in (43), is stochastic with positive diagonal elements as are the matrices ? i ? (j ?1) i Fp Hp 1 j =1 Fp ?i = ? ?, i ≥ 1 F p 0 Since eFp t =

i=0 ? eFp t ?

(73)

1

∞

?p )i (tF i!

(74)

? ? ? ? must also be nonnegative with positive diagonal elements. But e(Fp ?I )t = e?t eFp t , where I ? ? ( F ? I ) t p ? ? is the (n + 1) × (n + 1) identity, so the same must be true of e . Moreover (Fp ? I )1 = 0

21

which means that e(Fp ?I )t 1 = e0 1 = 1 and thus that e(Fp ?I )t is stochastic. In summary, e(Fp ?I )t is a stochastic matrix with positive diagonal entries. Equations (72) - (74) imply that eFp t = where kp =

i=0 ?

?

?

?

?

?

?

eFp t 0

i

kp et

∞

ti i!

(j ?1) Fp Hp 1 j =1

(75)

Therefore e(Fp ?I )t =

? ? ? ?

e(Fp ?I )t 0

kp 1

(76)

But e(Fp ?I )t is row-stochastic, so e(Fp ?I )t must have its row sums all bounded above by 1. From this and (71) it follows that (62) is true. ?p ,G ?p ,...,G ? pm } is a jointly connected collection of graphs. Then by Now suppose that {G 1 2 Lemma 5

m (i?1) Fp Hpj 1 > 0, j j =1

i>n

(77)

This and (75) imply that

m

kpj > 0

j =1

(78)

because all of the matrices in the sums de?ning the kp in (75) are non-negative. Using (76) and the de?nition of Mp in (71) we can write ? Mp tm Mp e m e m?1 tm?1 · · · eMp1 t1 ? ? ? ? ? ? e(Fpm ?I )tm e(Fpm?1 ?I )tm?1 · · · e(Fp1 ?I )t1 = ? 0

m j =1 Φmj kpj

? ? (79)

1

where Φmm = I and Φmj = eMpm tm · · · eMpj +1 tj +1 , j < m. Since the matrix on the right in (79) is stochastic, its row sums all equal one. To complete the proof it is therefore enough to show that

m

Φmj kpj > 0

j =1

(80)

1 i Note that for any non-negative n × n matrix N , eN ≥ I because the matrix ∞ i=1 i! N in the M t ∞ 1 p de?nition eN = i=0 i! N i is non-negative. Thus for j ∈ {1, 2, . . . , m}, e j j ≥ I and consequently Φmj ≥ I . Therefore, Φmj kj ≥ kj , j ∈ {1, 2, . . . , m}. From this and (78) it follows that (80) is true and thus that the inequality in (63) is correct.

22

5

Concluding Remarks

The convergence proof for Vicsek’s model presented in Section 2 relies heavily on Wolfowitz’s theorem. By generalizing some of the constructions Wolfowitz used in his proof, it is possible to develop a convergence result for a continuous-time analog of the Vicsek model which is quite similar to Theorem 5. In studying continuous-time leader-following, we imposed the requirement that all followers use the same dwell time. This is not really necessary. In particular, without much additional e?ort it can be shown that Theorem 5 remains true under the relatively mild assumption that all agents use dwell times which are rationally related. In contrast, the synchronization assumption may be more di?cult to relax. Although convergence is still likely without synchronization, the aperiodic nature of σ ’s switching times which could result, make the analysis problem more challenging. The models we have analyzed are of course very simple and as a consequence, they are probably not really descriptive of actual bird-?ocking, ?sh schooling, or even the coordinated movements of envisioned groups of mobile robots. Nonetheless, these models do seem to exhibit some of the rudimentary behaviors of large groups of mobile autonomous agents and for this reason they serve as a natural starting point for the analytical study of more realistic models. It is clear from the developments in this paper, that ideas from graph theory and dynamical system theory will play a central role in both the analysis of such biologically inspired models and in the synthesis of provably correct distributed control laws which produce such emergent behaviors in man-made systems.

References

[1] T. Vicsek, A. Czirok, E. Ben Jacob, I. Cohen, and O. Schochet. Novel type of phase transitions in a system of self-driven particles. Physical Review Letters, 75:1226–1229, 1995. [2] C. Reynolds. Flocks, birds, and schools: a distributed behavioral model. Computer Graphics, 21:25–34, 1987. [3] A. Czirok, A. L. Barabasi, and T. Vicsek. Collective motion of self-propelled particles:kinetic phase transition in one dimension. Physical Review Letters, 82:209–212, 1999. [4] J. Toner and Y. Tu. Flocks, herds, and schools: A quantitative theory of ?ocking. Physical Review E., 58:4828–4858, 1998. [5] J. Toner and Y. Tu. Long range order in a two dimensional xy model: How birds ?y together. Physical Review Letters, 75:4326–4329, 1995. [6] A. S. Mikhailov and D. Zannette. Noise induced breakdown of collective coherent motion in swarms. Physical Review E, 60:4571–4575, 1999. [7] C. P. Schenk, P Schutz, M. Bode, and H.G. Purwins. Interaction of self organized quasi particles in a two dimensional reaction-di?usion system: The formation of molecules. Physical Review E, 58:6480–6486, 1998.

23

[8] Y. Liu, K.M. Passino, and M. Polycarpou. Stability analysis of one-dimensional asynchronous swarms. In American Control Conference, Arlington, VA, pages 716–721, June, 2001. [9] N. Leonard and E. Friorelli. Virtual leaders, arti?cial potentials and coordinated control of groups. IEEE Conference on Decision and Control, Orlando, FL, 2001. [10] R. Olfati-Saber and R. M. Murray. Distributed cooperative control of multiple vehicle formations using structural potential functions. In IFAC World Congress, Barcelona, Spain, To appear, 2002. [11] J. A. Fax and R. M. Murray. Graph laplacians and stabilization of vehicle formations. To appear, 15th IFAC Congress, Barcelona, Spain, 2002. [12] J. P. Desai, J.P. Ostrowski, and V. Kumar. Modeling and control of formations of nonholonomic mobile robots. IEEE transactions on Robotics and Automation, 17(6):905–908, 2001. [13] J. Wolfowitz. Products of indecomposable, aperiodic, stochastic matrices. Proceedings of the American Mathematical Society, 15:733–737, 1963. [14] E. Seneta. Non-negative matrices and Markov chains. Springer Verlag, New York, 1981. [15] I. Daubechies and J. C. Lagarias. Sets of matrices all in?nite products of which converge. Linear Algebra and Applications, 161:227–263, 1992. [16] I. Daubechies and J. C. Lagarias. Corrigendum/addendum to“sets of matrices all in?nite products of which converge”. Linear Algebra and Applications, 327:69–83, 2001. [17] R. Bru, L. Elsner, and M. Neumann. Convergence of in?nite products of matrices and innerouter iteration schemes. Electronic Transactions on Numerical Analysis, 2:183–193, 1994. [18] W. J. Beyn and L. Elsner. In?nite products and paracontracting matrices. Electronic Journal of Linear Algebra, 2:1–8, 1997. [19] A. Rhodius. On the maximum of ergodicity coe?cients, the Dobrushin ergodicity coe?cient, and products of stochastic matrices. Linear Algebra and Applications, 253:141–154, 1997. [20] A. Vladimirov, E. Elsner, and W.J. Beyn. Stability and paracontractivity of discrete linear inclusions. Linear Algebra and Applications, 312:125–134, 2000. [21] B. Mohar. The Laplacian spectrum of graphs. in Graph theory, combinatorics and applications (Ed. Y. Alavi G. Chartrand, O. R. Ollerman, and A. J. Schwenk), 2:871–898, 1991. [22] R. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, New York, 1985. [23] M. A. Berger and Y. Wang. Bounded semigroups of matrices. Linear Algebra and Applications, 166:21–27, 1992. [24] M. Ando and M. H. Shih. Simultaneous contractibility. SIAM Journal on Matrix Analysis and Applications, 19:487–498, 1998. [25] C. Godsil and G. Royle. Algebraic Graph Theory. Springer Graduate Texts in Mathematics # 207, New York, 2001. 24

[26] A. S. Morse. Dwell-time switching. In Proceedings of the 2nd European Control Conference, pages 176–181, 1993. [27] A. S. Morse. A bound for the disturbance-to-tracking error gain of a supervised set-point control system. In D Normand Cyrot, editor, Perspectives in Control – Theory and Applications, pages 23 – 41. Springer-Verlag, 1998.

25