988 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO.

6, JUNE 2003

Coordination of Groups of Mobile Autonomous

Agents Using Nearest Neighbor Rules
Ali Jadbabaie, Jie Lin, and A. Stephen Morse, Fellow, IEEE

Abstract—In a recent Physical Review Letters article, Vicsek There is a large and growing literature concerned with
et al. propose a simple but compelling discrete-time model of the coordination of groups of mobile autonomous agents.
autonomous agents (i.e., points or particles) all moving in the plane Included here is the work of Czirok et al. [3] who propose
with the same speed but with different headings. Each agent’s
heading is updated using a local rule based on the average of its one-dimensional models which exhibit the same type of
own heading plus the headings of its “neighbors.” In their paper, behavior as Vicsek’s. In [4] and [5], Toner and Tu construct
Vicsek et al. provide simulation results which demonstrate that a continuous ”hydrodynamic" model of the group of agents,
the nearest neighbor rule they are studying can cause all agents while other authors such as Mikhailov and Zanette [6] consider
to eventually move in the same direction despite the absence of the behavior of populations of self propelled particles with
centralized coordination and despite the fact that each agent’s
set of nearest neighbors change with time as the system evolves. long range interactions. Schenk et al. determined interactions
This paper provides a theoretical explanation for this observed between individual self-propelled spots from underlying reac-
behavior. In addition, convergence results are derived for several tion-diffusion equation [7]. Meanwhile, in modeling biological
other similarly inspired models. The Vicsek model proves to be systems, Grünbaum and Okubo use statistical methods to
a graphic example of a switched linear system which is stable, analyze group behavior in animal aggregations [8]. This paper
but for which there does not exist a common quadratic Lyapunov
function. and, for example, the work reported in [9]–[12] are part of a
large literature in the biological sciences focusing on many
Index Terms—Cooperative control, graph theory, infinite prod- aspects of aggregation behavior in different species.
ucts, multiagent systems, switched systems.
In addition to these modeling and simulation studies, research
papers focusing on the detailed mathematical analysis of emer-
I. INTRODUCTION gent behaviors are beginning to appear. For example, Lui et al.
[13] use Lyapunov methods and Leonard et al. [14] and Ol-
I N [1], Vicsek et al. propose a simple but compelling
discrete-time model of autonomous agents (i.e., points
or particles) all moving in the plane with the same speed but
fati and Murray [15] use potential function theory to understand
flocking behavior, and Ögren et al. [16] uses control Lyapunov
with different headings. Each agent’s heading is updated using function-based ideas to analyze formation stability, while Fax
a local rule based on the average of its own heading plus the and Murray [17] and Desai et al. [18] employ graph theoretic
headings of its “neighbors.” Agent ’s neighbors at time , are techniques for the same purpose.
those agents which are either in or on a circle of pre-specified The one feature which sharply distinguishes previous ana-
radius centered at agent ’s current position. The Vicsek lyzes from that undertaken here is that this paper explicitly takes
model turns out to be a special version of a model introduced into account possible changes in nearest neighbors over time.
previously by Reynolds [2] for simulating visually satisfying Changing nearest neighbor sets is an inherent property of the
flocking and schooling behaviors for the animation industry. In Vicsek model and in the other models we consider. To ana-
their paper, Vicsek et al. provide a variety of interesting simu- lyze such models, it proves useful to appeal to well-known re-
lation results which demonstrate that the nearest neighbor rule sults [19], [20] characterizing the convergence of infinite prod-
they are studying can cause all agents to eventually move in the ucts of certain types of nonnegative matrices. The study of in-
same direction despite the absence of centralized coordination finite matrix products is ongoing [21]–[26], and is undoubtedly
and despite the fact that each agent’s set of nearest neighbors producing results which will find application in the theoretical
change with time as the system evolves. In this paper, we study of emergent behaviors.
provide a theoretical explanation for this observed behavior. Vicsek’s model is set up in Section II as a system of
simultaneous, one-dimensional recursion equations, one for
each agent. A family of simple graphs on vertices is then
Manuscript received March 4, 2002; revised December 2, 2002. Recom- introduced to characterize all possible neighbor relationships.
mended by Associate Editor A. Bemporad. This work was supported by the
Defense Advanced Research Project Agency (DARPA) under its SEC program Doing this makes it possible to represent the Vicsek model
and by the National Science Foundation under its KDI/LIS initiative. as an -dimensional switched linear system whose switching
A. Jadbabaie was with Yale University, New Haven, CT 06520 USA. He is signal takes values in the set of indices which parameterize
now with the Department of Electrical and Systems Engineering and GRASP
Laboratory, University of Pennsylvania, Philadelphia, PA 19104 USA (e-mail: the family of graphs. The matrices which are switched within
jadbabai@seas.upenn.edu). the system turn out to be nonnegative with special structural
J. Lin and A. S. Morse are with the Center for Computational Vision and properties. By exploiting these properties and making use of a
Control, Department of Electrical Engineering, Yale University, New Haven,
CT 06520 USA. classical convergence result due to Wolfowitz [19], we prove
Digital Object Identifier 10.1109/TAC.2003.812781 that all agents’ headings converge to a common steady state
0018-9286/03$17.00 © 2003 IEEE
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 989

heading provided the agents are all “linked together” via Because of this, it makes sense to represent headings at any
their neighbors with sufficient frequency as the system evolves. finite time , as real numbers in . Of course it is entirely
The model under consideration turns out to provide a graphic possible that in the limit as , a heading might approach
example of a switched linear system which is stable, but for the value ; any such limiting value is interpreted as a heading
which there does not exist a common quadratic Lyapunov of 0. Analogous statement apply to all other models considered
function. in the sequel. Accordingly, throughout the paper headings at any
In Section II-B, we define the notion of an average heading finite time , are represented as real numbers in .
vector in terms of graph Laplacians [27] and we show how The explicit form of the update equations determined by
this idea leads naturally to the Vicsek model as well as to (1) and (2) depends on the relationships between neighbors
other decentralized control models which might be used for the which exist at time . These relationships can be conveniently
same purposes. We propose one such model which assumes described by a simple, undirected graph2 with vertex set
each agent knows an upper bound on the number of agents in which is defined so that is one of the
the group, and we explain why this model has convergence graph’s edges just in case agents and are neighbors. Since
properties similar to Vicsek’s. the relationships between neighbors can change over time, so
In Section III, we consider a modified version of Vicsek’s dis- can the graph which describes them. To account for this we
crete-time system consisting of the same group of agents, plus will need to consider all possible such graphs. In the sequel we
one additional agent, labeled 0, which acts as the group’s leader. use the symbol to denote a suitably defined set, indexing the
Agent 0 moves at the same constant speed as its followers but class of all simple graphs defined on vertices.
with a fixed heading . The th follower updates its heading just The set of agent heading update rules defined by (1) and (2),
as in the Vicsek model, using the average of its own heading plus can be written in state form. Toward this end, for each ,
the headings of its neighbors. For this system, each follower’s define
set of neighbors can also include the leader and does so when-
ever the leader is within the follower’s neighborhood defining (3)
circle of radius . We prove that the headings of all agents
must converge to the leader’s provided all agents are “ linked where is the adjacency matrix of graph and the diag-
to their leader” together via their neighbors frequently enough onal matrix whose th diagonal element is the valence of vertex
as the system evolves. Finally, we develop a continuous-time within the graph. Then
analog of this system and prove under condition milder than im-
(4)
posed in the discrete-time case, that the headings of all agents
again converge to the heading of the group’s leader. where is the heading vector and
is a switching signal whose value at time
II. LEADERLESS COORDINATION , is the index of the graph representing the agents’ neighbor
The system studied by Vicsek et al. [1] consists of au- relationships at time . A complete description of this system
tonomous agents (e.g., points or particles), labeled 1 through , would have to include a model which explains how changes
all moving in the plane with the same speed but with different over time as a function of the positions of the agents in the
headings.1 Each agent’s heading is updated using a simple local plane. While such a model is easy to derive and is essential for
rule based on the average of its own heading plus the headings of simulation purposes, it would be difficult to take into account in
its “neighbors.” Agent ’s neighbors at time , are those agents a convergence analysis. To avoid this difficulty, we shall adopt
which are either in or on a circle of pre-specified radius cen- a more conservative approach which ignores how depends on
tered at agent ’s current position. In the sequel denotes the agent positions in the plane and assumes instead that might
the set of labels of those agents which are neighbors of agent be any switching signal in some suitably defined set of interest.
at time . Agent ’s heading, written , evolves in discrete-time Our goal is to show for a large class of switching signals
in accordance with a model of the form and for any initial set of agent headings that the headings
of all agents will converge to the same steady state value
(1) . Convergence of the to is equivalent to the state
vector converging to a vector of the form where
where is a discrete-time index taking values in the nonnegative
integers , and is the average of the head- . Naturally, there are situations where
ings of agent and agent ’s neighbors at time ; that is convergence to a common heading cannot occur. The most
obvious of these is when one agent—say the th—starts so
far away from the rest that it never acquires any neighbors.
(2) Mathematically, this would mean not only that is never
2By an undirected graph = 1 2 ...
on vertex set V f ; ; ng is meant V
where is the number of neighbors of agent at time . = ( ):
together with a set of unordered pairs E f i; j i; j 2 Vg which are called
( )
’s edges. Such a graph is simple if it has no self-loops [i.e., i; j 2 E only if
Observe that the preceding heading update rule maps headings =
i 6 j ] or repeated edges (i.e., E contains only distinct elements). By the valence
with values into a heading with a value also in . of a vertex v of is meant the number of edges of which are “incident” on
( )
v where by an indicant edge on v is meant an edge i; j of for which either
1The Vicsek system also includes noise input signals, which we ignore in this i= =
v or j v . The adjacency matrix of is an n 2 n matrix of whose ij th
paper. ( )
entry is 1 if i; j is one of ’s edges and 0 if it is not.
990 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO. 6, JUNE 2003

connected3 at any time , but also that vertex remains an Theorem 2: Let be fixed and let
isolated vertex of for all . This situation is likely to be be a switching signal for which there exists an infinite sequence
encountered if is very small. At the other extreme, which of contiguous, nonempty, bounded, time-intervals ,
is likely if is very large, all agents might remain neighbors , starting at , with the property that across each
of all others for all time. In this case, would remain fixed such interval, the agents are linked together. Then
along such a trajectory at that value in for which
is a complete graph. Convergence of to can easily be
(6)
established in this special case because with so fixed, (4)
is a linear, time-invariant, discrete-time system. The situation
of perhaps the greatest interest is between these two extremes where is a number depending only on and .
when is not necessarily complete or even connected for The hypotheses of Theorem 2 require each of the collec-
any , but when no strictly proper subset of ’s vertices tions , , to be jointly
is isolated from the rest for all time. Establishing convergence connected. Although no constraints are placed on the intervals
in this case is challenging because changes with time and (4) , , other than that they be of finite length, the con-
is not time-invariant. It is this case which we intend to study. straint on is more restrictive than one might hope for. What
Toward this end, we denote by the subset of consisting one would prefer instead is to show that (6) holds for every
of the indices of the connected graphs in . Our switching signal for which there is an infinite sequence of
first result establishes the convergence of for the case when bounded, nonoverlapping but not necessarily contiguous in-
takes values only in . tervals across which the agents are linked together. Whether
Theorem 1: Let be fixed and let or not this is true remains to be seen.
be a switching signal satisfying , . Then A sufficient but not necessary condition for to satisfy the
hypotheses of Theorem 2 is that on each successive interval
, take on at least one value in . Theorem 1 is thus
(5)
an obviously a consequence of Theorem 2 for the case when all
intervals are of length 1. For this reason we need only develop
where is a number depending only on and . a proof for Theorem 2. To do this we will make use of certain
It is possible to establish convergence to a common heading structural properties of the . As defined, each is square and
under conditions which are significantly less stringent that those nonnegative, where by a nonnegative matrix is meant a matrix
assumed in Theorem 1. To do this we need to introduce sev- whose entries are all nonnegative. Each also has the property
eral concepts. By the union of a collection of simple graphs, that its row sums all equal 1 (i.e., ). Matrices with these
, each with vertex set , is meant the two properties are called stochastic [28]. The have the addi-
simple graph with vertex set and edge set equaling the union tional property that their diagonal elements are all nonzero. For
of the edge sets of all of the graphs in the collection. We say that the case when (i.e., when is connected), it is known
that becomes a matrix with all positive entries for
such a collection is jointly connected if the union of its members
sufficiently large [28]. It is easy to see that if
is a connected graph. Note that if such a collection contains at
has all positive entries, then so does . Such and
least one graph which is connected, then the collection must be
are examples of “primitive matrices” where by a primitive
jointly connected. On the other hand, a collection can be jointly
matrix is meant any square, nonnegative matrix for which
connected even if none of its members are connected.
is a matrix with all positive entries for sufficiently large
It is natural to say that the agents under consideration are [28]. It is known [28] that among the eigenvalues of a prim-
linked together across a time interval if the collection itive matrix, there is exactly one with largest magnitude, that
of graph encountered along the this eigenvalue is the only one possessing an eigenvector with
interval, is jointly connected. Theorem 1 says, in essence, that all positive entries, and that the remaining eigenvalues
convergence of all agents’ headings to a common heading is are all strictly smaller in magnitude than the largest one. This
for certain provided all agents are linked together across each means that for , 1 must be ’s largest eigenvalue and
successive interval of length one (i.e., all of the time). Of course all remaining eigenvalues must lie within the open unit circle.
there is no guarantee that along a specific trajectory the As a consequence, each such must have the property that
agents will be so linked. Perhaps a more likely situation, at least for some row vector . Any stochastic ma-
when is not too small, is when the agents are linked together trices for which is a matrix of rank 1 is called
across contiguous intervals of arbitrary but finite length. If the ergodic [28]. Primitive stochastic matrices are thus ergodic ma-
lengths of such intervals are uniformly bounded, then in this trices. To summarize, each is a stochastic matrix with pos-
case too convergence to a common heading proves to be for itive diagonal elements and if then is also primitive
certain. and, as a result, ergodic. The crucial convergence result upon
which the proof of Theorem 2 depends is classical [19] and is
3A simple graph with vertex set V = 1 2 ...
f ; ; ; ng and edge set E is as follows.
connected if has a “path” between each distinct pair of its vertices i and j where Theorem 3 (Wolfowitz): Let be a fi-
by a path (of length m) between vertices i and j is meant a sequence of distinct
( )(
edges of of the form i; k ; k ; k ; ) ...( k ; j .) is complete if has a nite set of ergodic matrices with the property that for each
path of length one (i.e., an edge) between each distinct pair of its vertices. sequence of positive length, the matrix
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 991

product is ergodic. Then for each infinite primitive matrix and if , then is primitive as well.
sequence, there exists a row vector such that Lemma 1 is a simple consequence of the following result.
Lemma 2: Let be a positive integer and let
be nonnegative matrices. Suppose that
the diagonal elements of all of the are positive and let and
The finiteness of the set is crucial to Wol- denote the smallest and largest of these, respectively. Then
fowitz’s proof. This finiteness requirement is also the reason
why we’ve needed to assume contiguous, bounded intervals in (10)
the statement of Theorem 2.
In order to make use of Theorem 3, we need a few facts con-
cerning products of the types of matrices we are considering. Proof: Set . It will be shown by induction that
First, we point out that the class of stochastic matrices
(11)
with positive diagonal elements is closed under matrix multi-
plication. This is because the product of two nonnegative ma- holds for . Toward this end. note that it is
trices with positive diagonals is a matrix with the same proper- possible to write each as where is nonneg-
ties and because the product of two stochastic matrices is sto- ative. Then, for any
chastic. Second, we will use the following key result.4
Lemma 1: Let be a set of indices in for
which is a jointly connected collection
of graphs. Then the matrix product is ergodic. Hence
Proof of Theorem 25 : Let denote the least upper
bound on the lengths of the intervals , .
By assumption . Let , and
, . Clearly
. To complete the theorem’s proof, it is, Since and it follows that
therefore, enough to show that
(12)
(7)
Setting and proves that (11) holds for . If
for some row vector since this would imply (6) with , the proof is complete.
. In view of Lemma 1, the constraints on Now, suppose that and that (11) holds for
imply that each such matrix product , is where is some integer in .
ergodic. Moreover the set of possible , Then, so by the inductive
must be finite because each is a product of at hypothesis
most matrices from which is a finite set.
But . (13)
Therefore, by Theorem 3
However, using (12) times, we can write
(8)

For each , let be the largest nonnegative integer

such that . Then, and Thus
so

(9)
This and (13) imply that (11) holds for . Therefore, by
Note that is a bounded function because induction (11) is true for all .
is the product of at most matrices which Proof of Lemma 1: Set where
come from a bounded set. Moreover and are respectively the adjacency matrix and diag-
as because of (8). From this and (9), it follows that onal valence matrix of the union of the collection of graphs
as . Therefore, (7) holds. . Since the collection is jointly con-
To prove Lemma 1 we shall make use of the standard partial nected, its union is connected which means that is primitive.
ordering on nonnegative matrices by writing By Lemma 2
whenever is nonnegative. Let us note that if is a
4We are indebted to M. Artzrouni, University of Pau, France, for his help with (14)
the proof of an earlier version of this lemma.
5The authors thank D. Liberzon for pointing out a flaw in the original version where is a positive constant depending on the matrices in the
of this proof, and S. Meyn for suggesting how to fix it. product. Since for ,
992 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO. 6, JUNE 2003

and , it must be true that products of the converge to zero. It is known [29] that con-
, . From this and (14) it follows that vergence to zero of all such infinite products is in fact equiva-
lent to the “joint spectral radius” of being strictly less than
1 where by joint spectral radius of is meant
(15)
However, and so

Since the product is bounded below by a prim-

itive matrix, namely , the product must be primitive as well. Here, is any norm on the space of real matrices. It
Since is also a stochastic matrix, it must there- turns out that does not depend on the choice of norm [21,
fore be ergodic. p. 237]. On the other hand, a “tight” sufficient condition for the
As we have already noted, . Thus, span existence of a common quadratic Lyapunov function for the ma-
is an -invariant subspace. From this and standard existence trices in , is [30]. This condition is tight in
conditions for solutions to linear algebraic equations, it follows the sense that one can find a finite set of matrices with
that for any matrix with kernel spanned by , the joint spectral radius , whose infinite products con-
equations verge to zero despite the fact that there does not exist common
quadratic Lyapunov function for the set. From this one can draw
(16) the conclusion that sets of matrices with “large” are not likely
to possess a common quadratic, even though all infinite products
have unique solutions , and moreover that of such matrices converge to zero. This can in turn help explain
why it has proved to be necessary to go as high as to
spectrum (17) find a case where a common quadratic Lyapunov function for a
family of does not exist.
As a consequence of (16) it can easily be seen that for any se-
quence of indexes in A. Generalization
(18) It is possible to interpret the Vicsek model analyzed in the last
section as the closed-loop system which results when a suitably
Since has full-row rank and , the convergence of defined decentralized feedback law is applied to the -agent
a product of the form to for some row heading model
vector , is equivalent to convergence of the corresponding
product to the zero matrix. Thus, for ex- (20)
ample, if is an infinite sequence of indices in , with open-loop control . To end up with the Vicsek model,
then, in view of Theorem 3 would have to be defined as
(19) (21)

Some readers might be tempted to think, as we first did, that where is the average heading error vector
the validity of (19) could be established directly by showing
(22)
that the in the product share a common quadratic Lyapunov
function. More precisely, (19) would be true if there were a and, for each , is the symmetric matrix
single positive–definite matrix such that all of the matrices
were negative definite. Although each (23)
can easily be shown to be discrete-time stable, there
known in graph theory as the Laplacian of [27], [31]. It is
are classes of for which that no such common Lyapunov ma-
easily verified that equations (20) to (21) do indeed define the
trix exists. While we have not been able to construct a simple
Vicsek model. We have elected to call the average heading
analytical example which demonstrates this, we have been able
error because if at some time , then the heading of
to determine, for example, that no common quadratic Lyapunov
each agent with neighbors at that time will equal the average of
function exists for the class of all whose associated graphs
the headings of its neighbors.
have 10 vertices and are connected. One can verify that this is
In the present context, Vicsek’s control (21) can be viewed as
so by using semidefinite programming and restricting the check
a special case of a more general decentralized feedback control
to just those connected graphs on ten vertices with either nine
of the form
or ten edges.
It is worth noting that existence of a common quadratic Lya- (24)
punov function for all discrete time stable matrices
in some given finite set , is a much stronger where for each , is a suitably defined, nonsingular
condition than is typically needed to guarantee that all infinite diagonal matrix with th diagonal element . This, in turn, is an
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 993

abbreviated description of a system of individual agent control This means that the eigenvalues of must be smaller than
laws of the form 1 since . From these properties it clearly follows that the
eigenvalues of must all be between 0 and 1, and
that if is connected, then all will be strictly less than 1 except
for one eigenvalue at 1 with eigenvector . Since each is of
the form , each possesses all of these properties.
(25)
Let be a fixed switching signal with value at time
where for , is the th entry of and . What we’d like to do is to prove that as , the
. Application of this control to (20) would result in matrix product converges to for some row
the closed-loop system vector . As noted in the Section II-A, this matrix product will
so converge just in case
(26)
(30)
Note that the form of (26) implies that if and were to con-
verge to a constant values , and , respectively, then would
automatically satisfy . This means that control (24) au- where as in Section II-A, is the unique solution to
tomatically forces each agent’s heading to converge to the av- and is any full rank matrix satis-
erage of its neighbors, if agent headings were to converge at all. fying . For simplicity and without loss of generality we
In other words, the choice of the does not effect the require- shall henceforth assume that the rows of form a basis for the
ment that each agent’s heading equal the average of the headings orthogonal complement of the span of . This means that
of its neighbors, if there is convergence at all. equals the identity , that ,
The preceding suggests that there might be useful choices for and, thus, that each is symmetric. Moreover, in view of (17)
the alternative to those considered by Vicsek, which also and the spectral properties of the , , it is clear that each
lead to convergence. One such choice turns out to be , must have a real spectrum lying strictly inside of
the unit circle. This plus symmetry means that for each ,
(27) is negative definite, that is negative definite
where is any number greater than . Our aim is to show that and thus, that is a common discrete-time Lyapunov matrix for
with the so defined, Theorem 2 continues to be valid. In all such . Using this fact it is straight forward to prove that
sharp contrast with the proof technique used in the last section, Theorem 1 holds for system (26) provided the are defined
convergence will be established here using a common quadratic as in (27) with .
Lyapunov function. In general, each is a discrete-time stability matrix for
As before, we will use the model which is negative definite only if . To craft a
proof of Theorem 2 for the system described by (26) and (27),
(28) one needs to show that for each interval on which
is a jointly connected
where, in view of the definition of the in (27), the are
now symmetric matrices of the form collection of graphs, the product
is a discrete-time stability matrix and
(29)

To proceed we need to review a number of well known and

is negative definite. This is a direct consequence of the following
easily verified properties of graph Laplacians relevant to the
proposition.
problem at hand. For this, let be any given simple graph with
Proposition 1: If is a jointly con-
vertices. Let be a diagonal matrix whose diagonal elements
nected collection of graphs, then
are the valences of ’s vertices and write for ’s adjacency
matrix. Then, as noted before, the Laplacian of is the sym-
metric matrix . The definition of clearly implies
that . Thus, must have an eigenvalue at zero and is a negative–definite matrix.
must be an eigenvector for this eigenvalue. Surprisingly is al- In the light of Proposition 1, it is clear that the conclusion
ways a positive semidefinite matrix [31]. Thus, must have a Theorem 2 is also valid for the system described by (26) and
real spectrum consisting of nonnegative numbers and at least (27). A proof of this version of Theorem 2 will not be given.
one of these numbers must be 0. It turns out that the number of To summarize, both the Vicsek control defined by
connected components of is exactly the same as the multi- and the simplified control given by
plicity of ’s eigenvalue at 0 [31]. Thus, is a connected graph achieve the same emergent behavior. While
just in case has exactly one eigenvalue at 0. Note that the trace latter is much easier to analyze than the former, it has the
of is the sum of the valences of all vertices of . This number disadvantage of not being a true decentralized control because
can never exceed and can attain this high value only each agent must know an upper bound (i.e., ) on the total
for a complete graph. In any event, this property implies that the number of agents within the group. Whether or not this is really
maximum eigenvalue of is never larger that . Actu- a disadvantage, of course depends on what the models are to
ally, the largest eigenvalue of can never be larger than [31]. be used for.
994 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO. 6, JUNE 2003

The proof of Proposition 1 depends on two lemmas. In the which is valid for . Since all matrices in (35) are posi-
sequel, we state the lemmas, use them to prove Proposition 1, tive semidefinite, any vector which makes the quadratic form
and then conclude this section with proofs of the lemmas them- vanish, must also make
selves. the quadratic form vanish. Since
Lemma 3: If is a jointly connected any vector in the kernel of each matrix has this property,
collection of graphs with Laplacians , then we can draw the following conclusion:

kernel span (31) kernel kernel

Lemma 4: Let be a set of real Suppose now that is a jointly con-

symmetric, matrices whose induced 2-norms are all less than nected collection. Then the union is
or equal to 1. If connected so its Laplacian must have exactly span for its
kernel. Hence, the intersection of the kernels of the
kernel (32) must be contained in span . But span is contained in
the kernel of each matrix in the intersection and, there-
then the induced two-norm of is less than 1. fore, in the intersection of the kernels of these matrices as well.
Proof of Proposition 1: The definition of the in (29) It follows that (31) is true.
implies that . Hence, by Lemma 3 and the Proof of Lemma 4: In the sequel we write for the
hypothesis that is a jointly connected 2-norm of a real -vector and for the induced 2-norm of
collection a real matrix. Let be any real, nonzero -vector.
It is enough to show that
kernel span (33)
(36)
We claim that In view of (32) and the assumption that , there must be a
largest integer such that kernel
kernel (34) . We claim that

(37)
To establish this fact, let be any vector such that
, . Since has independent rows, there is a To show that this is so we exploit the symmetry of to write
vector such that . But , so as where
. Hence, for some number are real numbers and is an orthonormal set of
. But , so . This eigenvectors of with real eigenvalues . Note
implies that and, thus, that . However, that , , because . Next,
this must be true for all . It follows from (33) observe that since
that span and, since , that . Therefore, and , there must be at least one integer such that
(34) is true. . Hence, . However,
As defined, the are all symmetric, positive semi-definite so
matrices with induced 2-norms not exceeding 1. This and (34)
imply that the family of matrices satisfy the
hypotheses of Lemma 4. It follows that Proposition 1 is true. Moreover
Proof of Lemma 3: In the sequel we write for the
Laplacian of a simple graph . By the intersection of a collec-
tion of simple graphs, , each with vertex
set , is meant the simple graph with vertex set and edge set
equaling the intersection of the edge sets of all of the graphs in so ; therefore, (37) is true.
the collection. It follows at once from the definition of a Lapla- In view of the definition of , .
cian that From this and (37), it follows that
.
However, because each has an induced
for all . Repeated application of this identity to the set two-norm not exceeding 1. Therefore, (36a) is true.
yields the relation
III. LEADER FOLLOWING
In this section, we consider a modified version of Vicsek’s
discrete-time system consisting of the same group of agents
as before, plus one additional agent, labeled 0, which acts as the
(35) group’s leader. Agent 0 moves at the same constant speed as its
followers but with a fixed heading . The th follower updates
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 995

its heading just as before, using the average of its own heading their leader across an interval just when the -member
plus the headings of its neighbors. The difference now is that group consisting of the agents and their leader is linked to-
each follower’s set of neighbors can include the leader and does gether across . Note that for the -agent group to be linked to
so whenever the leader is within the follower’s neighborhood its leader across does not mean that the -agent group must be
defining circle of radius . Agent ’s update rule, thus, is of the linked together across . Nor is the -agent group necessarily
form linked to its leader across when it is linked together across .
Our main result on discrete-time leader following is next.
Theorem 4: Let and be fixed and let
be a switching signal for which there
exists an infinite sequence of contiguous, nonempty, bounded,
(38) time-intervals , , starting at , with the
property that across each such interval, the -agent group of
where as before, is the set of labels of agent ’s neighbors followers is linked to its leader. Then
from the original group of followers, and is the number (40)
of labels within . Agent 0’s heading is accounted for in
the th average by defining to be 1 whenever agent 0 is a The theorem says that the members of the -agent group all
neighbor of agent and 0 otherwise. eventually follow their leader provided there is a positive integer
The explicit form of the update equations exemplified by which is large enough so that the -agent group is linked to its
(38), depends on the relationships between neighbors which leader across each contiguous, nonempty time-interval of length
exist at time . Like before, each of these relationships can be at most . In the sequel, we outline several ideas upon which the
conveniently described by a simple undirected graph. In this proof of Theorem 4 depends.
case, each such graph has vertex set and is To begin, let us note that to prove that (40) holds is equivalent
defined so that is one of the graph’s edges just in case to proving that where is the heading error
agents and are neighbors. For this purpose we consider an vector . From (39) it is easy to deduce that
agent—say —to be a neighbor of agent 0 whenever agent 0 satisfies the equation
is a neighbor of agent . We will need to consider all possible
such graphs. In the sequel we use the symbol to denote a set (41)
indexing the class of all simple graphs defined on vertices
. We will also continue to make reference to the where for , is
set of all simple graphs on vertices . Such graphs are (42)
now viewed as subgraphs of the . Thus, for , now
denotes the subgraph obtained from by deleting vertex 0 and Note that the partitioned matrices
all edges incident on vertex 0.
The set of agent heading update rules defined by (38) can be (43)
written in state form. Toward this end, for each , let
denote the adjacency matrix of the -agent graph and are stochastic where, for
let be the corresponding diagonal matrix of valences of .
Then, in matrix terms, (38) becomes (44)

To proceed, we need a few more ideas concerned with non-

(39) negative matrices. In the sequel, we write whenever
is a positive matrix, where by a positive matrix is meant
where is now a switching signal whose a matrix with all positive entries. For any nonnegative matrix
value at time , is the index of the graph representing the of any size, we write for the largest of the row sums of
agent system’s neighbor relationships at time and for , . Note that is the induced infinity norm of and con-
is the diagonal matrix whose th diagonal element is sequently is sub-multiplicative. We denote by , the matrix
1, if is one of ’s edges and 0, otherwise. obtained by replacing all of ’s nonzero entries with a 1. Note
Much like before, our goal here is to show for a large class of that if and only if . It is also true for any pair of
switching signals and for any initial set of follower agent head- nonnegative matrices and with positive diagonal el-
ings, that the headings of all followers converge to the heading ements, that . Moreover, in view of Lemma
of the leader. For convergence in the leaderless case we required 2, any such pair of matrices must also satisfy and
all -agents to be linked together across each interval within .
an infinite sequence of contiguous, bounded intervals. We will Let be a given set of indices in . It
need a similar requirement in the leader following case under is possible to relate the connectedness of the collection
consideration. Let us agree to say that the agents are linked to properties of the matrix pairs
to the leader across an interval if the collection of graphs . Let us note first that for any
encountered along the interval is , the indices of the nonzero rows of are precisely
jointly connected. In other words, the agents are linked to the labels of vertices in which are connected to vertex 0
996 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO. 6, JUNE 2003

by paths of length 1. More generally, for any integer , Suppose that is a matrix which occurs in the sequence at least
the indices of the nonzero rows of are the times. Then
labels of vertices in connected to vertex 0 by paths of length
less than or equal to . Hence, for such , the nonzero rows (49)
of the sum must be the labels of Proof: We claim that for
vertices in the union of the collection
which are connected to vertex 0 by paths of length less than (50)
or equal to . It follows that if is
provided is a product within which occurs at
jointly connected, there must be a value of sufficiently large
least times. Suppose is a product within which
so that . Since any vertex
occurs at least once. Then where
in a connected graph with vertices is reachable from
and are nonnegative matrices with positive diagonal elements.
any other vertex along a path of length of at most , it
By Lemma 2, and . Thus,
follows that if is jointly connected,
which proves that (50) is true for .
then , . Now it is easy
Now suppose that (50) holds for and let
to see from the definitions of the and in (42) and (44)
be a product within which occurs at least
respectively, that , . We
times. We can write where
have proved the following lemma.
and are nonnegative matrices with positive diagonal elements
Lemma 5: Let be any set of indices in
and is a product within which occurs at least times. By the
for which is a jointly connected collec-
inductive hypothesis, . By Lemma 2,
tion of graphs. Then
. It follows that
and thus that (50) holds for . By induction, (50)
(45) therefore holds for all . Hence, the lemma is
true.
Proof of Proposition 2: It will be enough to prove that
Now, consider the partitioned matrices defined by (43).
Since each of these matrices is stochastic and products of sto- (51)
chastic matrices are also stochastic, for each and each
, is stochastic. However for every sequence of length at most possessing
values which each occur in the sequence at least
times and for which is a jointly
connected collection of graphs. For if this is so, then one can
define the uniform bound

Moreover, if is connected, then

where is the set of all such sequences. Note that if (51)
holds, because is a finite set.
(46) Let be a sequence of at length at most pos-
sessing values which each occur in the sequence
at least times and for which is a
because of Lemma 5. It follows that if is connected and jointly connected collection of graphs. The definition of the
, the row sums of must all be less that 1. In other words in (43) implies that
(47)

The following proposition generalizes (47) and is central to the

proof of Theorem 4.
Proposition 2: Let be a finite positive integer. There exists
a positive number , depending only on , for which where and for . Since
the are all stochastic, must be stochastic
(48) as well. Thus, to establish (51) it is sufficient to prove that

for every sequence of at length at most pos-

sessing values which each occur in the sequence (52)
at least times and for which is a
jointly connected collection of graphs. By assumption, each member of occurs
The proof of this proposition depends on the following basic in the sequence at least times. For
property of nonnegative matrices. , let be the smallest integer such that .
Lemma 6: Let be a finite sequence of Since each occurs at least times, each must occur at
nonnegative matrices whose diagonal entries are all positive. least times in the subsequence . It follows
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 997

from Lemma 6 and the definition of that . agent ’s heading, defined by (38), is what results when the local
Thus, . Since this hold for all feedback law
,

(54)

From this and (45) it follows that . But

is applied to the open-loop discrete-time heading model
, so (52) is true.
Proposition 2 actually implies that any finite product (55)
will be a discrete-time stability matrix pro-
vided there is a set of indices for which The continuous-time analog of (55) is the integrator equation
i) each occurs in the set at least (56)
times and ii) is a jointly connected
collection of graphs. From this it is not difficult to see that where now takes values in the real half interval .
any finite product will be ergodic provided On the other hand, the continuous time analog of (54) has
is a jointly connected collection of exactly the same form as (54), except in the continuous time
graphs.6 It is possible to use this fact together with Wolfowitz’s case, , and are continuous-time variables.
theorem (Theorem 3) to devise a proof of Theorem 4, much Unfortunately, in continuous time control laws of this form
like the proof of Theorem 2 given earlier. On the other hand, can lead to chattering because neighbor relations can change
it is also possible to give a simple direct proof of Theorem 4, abruptly with changes in agents’ positions. One way to avoid
without using Theorem 3, and this is the approach we take. this problem is to introduce dwell time, much as was done in
Proof of Theorem 4: Let denote the set of all [32]. What this means in the present context is that each agent
subsets of with the property that is constrained to change its control law only at discrete times.
is a jointly connected collection. The In particular, instead of using (54), to avoid chatter agent
constraints on imply that takes on every value in one would use a hybrid control law of the form
such subset on every interval , . Let be the
number of elements in . Then for any integer there must
be at least one subset in whose elements are each values of
at least times on any sequence of contiguous time-intervals.
Set , and let be the least upper bound on
the lengths of the intervals, , . By assumption, (57)
. Let denote the state transition matrix defined
by , and ,
where is a pre-specified positive number called a dwell time
,. Then . To complete the
and is an infinite time sequence such that
theorem’s proof, it is, therefore, enough to show that
, . In the sequel we will analyze controls of this
form subject to two simplifying assumptions. First we will as-
(53)
sume that all agents use the same dwell time which we hence-
forth denote by . Second we assume the agents are synchro-
Clearly . More- nized in the sense that for all
over, for , is an interval of length at most and all . These assumptions enable us to write as
on which takes on at least times, every value
in some subset in . It follows from Propo- (58)
sition 2 and the definition of that , where , and are as before, is the
where is a positive number depending only on Laplacian of , and is a piecewise constant
which satisfies . Hence, , from switching signal with successive switching times separated by
which (53) follows at once. time units. Application of this control to the vector version of
(56) results in the closed-loop continuous-time leader-follower
IV. LEADER FOLLOWING IN CONTINUOUS TIME model
Our aim here is to study the convergence properties of the (59)
continuous-time version of the leader-follower model discussed
in the last section. We begin by noting that the update rule for In analogy to the discrete-time case, let us agree to say
6Using this fact and the structure of the F it is also not difficult to show
that the agents are linked to the leader across an interval
that any finite product F F 1 1 1 F will be a discrete-time stability matrix
between switching times and , if the collection of
provided only that f ; ; ...; g is a jointly connected collection of
graphs encountered along
graphs. the interval, is jointly connected. Much like before, our goal
998 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO. 6, JUNE 2003

here is to show for a large class of switching signals and for matrix exponentials in (66) depend continuously on the . In
any initial set of follower agent headings, that the headings view of the definition of and the definitions of the in (64),
of all followers converge to the heading of the leader. For
convergence, we shall continue to require there to exist infinite (67)
sequence of bounded, nonoverlapping time-intervals across However
which the -agent group is linked to its leader. However, unlike
the discrete-time case we shall not require this sequence of
intervals to be contiguous.
Theorem 5: Let , and be fixed and let
be a piecewise-constant switching signal
This, (65), (67) and the sub-multiplicative property of the in-
whose switching times satisfy , .
duced infinity norm imply that
If there is an infinite sequence of bounded, nonoverlapping
time-intervals , , with the property that across (68)
each such interval the -agent group of followers is linked to
its leader, then Set and note that
(60)

Theorem 5 states that will converge to , no matter what because of (59). Let be the state transition ma-
the value of , so long as is greater than zero. This is in trix of . Then
sharp contrast to other convergence results involving dwell time . To complete the proof it is, therefore,
switching such as those given in [33], which hold only for suffi- enough to show that
ciently large values of . Theorem 5 is a more or less obvious
(69)
consequence of the following lemma.
Lemma 7: Let In view of the definitions of the ,
(61)

Then From this and (68) it follows that

(62) (70)
However
Moreover, for each finite set of indices in for
which is jointly connected, and each set
of finite, positive times ,
so
(63)

Proof of Theorem 5: Let

From this and (70), it now follows that (69) is true.
, and for , set Proof of Lemma 7: Fix and . Observe first
(64) that

(71)
From inequality (62) in Lemma 7 it follows that
where is the matrix . As
(65)
noted previously, the partitioned matrix
By assumption there is a finite upper bound on the lengths of
the intervals across which the agents are linked (72)
to their leader. This and the assumption that ,
, imply that , where is the smallest originally defined in (43), is stochastic with positive diagonal
positive integer such that . Let be the set of all elements as are the matrices
sequences of at length at most for which
is jointly connected. Define
(73)

(66) Since

Note that because the inequality in (63) is strict, because (74)

is a finite set, because is compact and because the
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 999

must also be nonnegative with positive diagonal elements. V. CONCLUDING REMARKS

But , where is the As stated in the abstract, the main objective of this paper has
identity, so the same must be true of . Moreover been to provide a theoretical explanation for behavior observed
which means that and, thus, in the simulation studies reported in [1]. We refer the interested
that is stochastic. In summary, is a stochastic reader to Vicsek’s paper and references cited therein, for a more
matrix with positive diagonal entries. thorough description of the model considered and for data doc-
Equations (72)–(74) imply that umenting the simulation studies performed.
The theorems in this paper all provide convergence results
for rich classes of switching signals and arbitrary initial heading
vectors. Of course as soon as one elects to interpret these results
where in the context of heading models for mobile autonomous agents,
one needs to add qualifications, because the actual switching
signal generated along a particular model’s trajectory would
(75)
have to depend on the model’s initial heading vector. To make
such a dependence explicit (and to run meaningful simulations)
Therefore more complete models would have to be defined. In carrying out
this step, one can expect to obtain a variety of results. For ex-
(76) ample, with very large agent sensing regions (i.e., very large)
and agents initially near each other, one would expect enough
However, is row-stochastic, so must have its connectivity along resultant trajectories for convergence to a
row sums all bounded above by 1. From this and (71) it follows common heading to occur. On the other hand, with widely dis-
that (62) is true. tributed initial agent positions and very small, one would ex-
Now suppose that is a jointly con- pect to see a bifurcation of the group into distinct subgroups with
nected collection of graphs. Then by Lemma 5 different steady state headings. In other words, a complete deter-
ministic understanding of the flocking problems we’ve consid-
ered would require both more complete agent motion models as
(77) well as an understanding of the nonlinear feedback process upon
which actually would depend. An alternative probabilistic ap-
This and (75) imply that proach might enable one to circumvent or at least simplify the
analysis of the feedback process.
Some versions of the Vicsek model and others considered
(78)
in this paper may ultimately find application in coordination
of groups of mobile autonomous agents. Of course before this
because all of the matrices in the sums defining the in (75) can happen many compelling issues such as collision avoidance,
are nonnegative. and the effects of disturbances, noise, sensing errors, vehicle
Using (76) and the definition of in (71) we can write modeling errors, etc. would have to be satisfactorily addressed.
For example, the collision avoidance question might also be ap-
proached by replacing the point models implicitly used in this
paper, with the model of a bumper-like “virtual shell” within
(79) which each agent vehicle is constrained to remain [34].
While the analysis in this paper is deterministic and does
not address the noise issue, the results obtained suggest that
where and , . to understand the effect of additive noise, one should focus on
Since the matrix on the right in (79) is stochastic, its row sums how noise inputs effect connectivity of the associated neighbor
all equal one. To complete the proof it is, therefore, enough to graphs. Simulation results presented in [1] indicate that when
show that noise intensity in the system is fixed, there is a phase transi-
tion as the density of the agents is increased, i.e., there is a crit-
ical density after which all agents eventually become aligned.
(80)
It is possible that this phenomenon can be adequately explained
using percolation theory of random graphs [35].
Note that for any nonnegative matrix , The results of this paper have been extended to the case
because the matrix in the def- where there are inter-agent forces due to attraction, repulsion
inition is nonnegative. Thus, for and alignment [36]. The new results indicate that the conver-
, and consequently . gence arguments used in this paper also apply to the more
Therefore, . From this and general problem considered in [36] under similar assumptions
(78) it follows that (80) is true and, thus, that the inequality in regarding the connectivity of the graph representing the nearest
(63) is correct. neighbor relationships.
1000 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 48, NO. 6, JUNE 2003

The convergence proof for Vicsek’s model presented in Sec- [8] D. Grunbaum and A. Okubo, “Modeling social animal aggregations,” in
tion II relies heavily on Wolfowitz’s theorem. By generalizing Frontiers in Theoretical Biology. New York: Springer-Verlag, 1994,
100 of Lecture Notes in Biomathematics, pp. 296–325.
some of the constructions Wolfowitz used in his proof, it is [9] C. M. Breder, “Equations descriptive of fish schools and other animal
possible to develop a convergence result for a continuous-time aggregations,” Ecology, vol. 35, pp. 361–370, 1954.
analog of the Vicsek model which is quite similar to Theorem 5. [10] A. Okubo, “Dynamical aspects of animal grouping: Swarms, schools,
flocks, and herds,” Adv. Biophys., vol. 22, pp. 1–94, 1986.
In studying continuous-time leader-following, we imposed [11] K. Warburton and J. Lazarus, “Tendency-distance models of social
the requirement that all followers use the same dwell time. This cohesion in animal groups,” J. Theoret. Biol., vol. 150, pp. 473–488,
is not really necessary. In particular, without much additional 1991.
[12] G. Flierl, D. Grunbaum, S. Levin, and D. Olson, “From individuals to
effort it can be shown that Theorem 5 remains true under the aggregations: The interplay between behavior and physics,” J. Theoret.
relatively mild assumption that all agents use dwell times which Biol., vol. 196, pp. 397–454, 1999.
[13] Y. Liu, K. M. Passino, and M. Polycarpou, “Stability analysis of one-di-
are rationally related. In contrast, the synchronization assump- mensional asynchronous swarms,” in Proc. Amer. Control Conf., Ar-
tion may be more difficult to relax. Although convergence is lington, VA, June 2001, pp. 716–721.
still likely without synchronization, the aperiodic nature of ’s [14] N. Leonard and E. Friorelli, “Virtual leaders, artificial potentials and
coordinated control of groups,” presented at the IEEE Conf. Decision
switching times which could result, make the analysis problem Control, Orlando, FL, 2001.
more challenging. [15] R. Olfati and R. M. Murray, “Distributed structural stabilization and
The use of simply averaging rules such as those discussed in tracking for formations of dynamic multi-agents,” presented at the IEEE
Conf. Decision Control, Las Vegas, NV, 2002.
this paper can sometimes have counter-intuitive consequences [16] P. Ogren, M. Egerstedt, and X. Hu, “A control Lyapunov function ap-
which may be undesirable in some applications. For example proach to multi-agent coordination,” IEEE Trans. Robot. Automat., p.
the average of headings 0.01 and is so this might 18, Oct. 2002.
[17] J. A. Fax and R. M. Murray, “Graph Laplacians and stabilization of ve-
cause two agents with headings both close to 0, to both approx- hicle formations,” presented at the 15th IFAC Congr., Barcelona, Spain,
imately reverse direction to a heading of on the next step. It 2002.
[18] J. P. Desai, J. P. Ostrowski, and V. Kumar, “Modeling and control of for-
would be of interest to determine how update rules might be mations of nonholonomic mobile robots,” IEEE Trans. Robot. Automat.,
modified to avoid this type of behavior. Of course issues along vol. 17, pp. 905–908, June 2001.
these lines would not arise at all if the systems we’ve consid- [19] J. Wolfowitz, “Products of indecomposable, aperiodic, stochastic ma-
trices,” in Proc. Amer. Mathematical Soc., vol. 15, 1963, pp. 733–736.
ered were modeling other physically significant variables such [20] E. Seneta, Non-Negative Matrices and Markov Chains. New York:
as agent speed or temperature where one could take all of Springer-Verlag, 1981.
rather than just as the set in which the take values. [21] I. Daubechies and J. C. Lagarias, “Sets of matrices all infinite products
of which converge,” Linear Alg. Applicat., vol. 161, pp. 227–263,
The models we have analyzed are of course very simple and 1992.
as a consequence, they are probably not really descriptive of ac- [22] , “Corrigendum/addendum to ‘Sets of matrices all infinite prod-
tual bird-flocking, fish schooling, or even the coordinated move- ucts of which converge’,” Linear Alg. Applicat., vol. 327, pp. 69–83,
2001.
ments of envisioned groups of mobile robots. Nonetheless, these [23] R. Bru, L. Elsner, and M. Neumann, “Convergence of infinite products
models do seem to exhibit some of the rudimentary behaviors of of matrices and inner-outer iteration schemes,” Electron. Trans. Numer.
Anal., vol. 2, pp. 183–193, 1994.
large groups of mobile autonomous agents and for this reason [24] W. J. Beyn and L. Elsner, “Infinite products and paracontracting ma-
they serve as a natural starting point for the analytical study trices,” Electron. J. Linear Alg., vol. 2, pp. 1–8, 1997.
of more realistic models. It is clear from the developments in [25] A. Rhodius, “On the maximum of ergodicity coefficients, the Dobrushin
ergodicity coefficient, and products of stochastic matrices,” Linear Alg.
this paper, that ideas from graph theory and dynamical system Applicat., vol. 253, pp. 141–154, 1997.
theory will play a central role in both the analysis of such biolog- [26] A. Vladimirov, E. Elsner, and W. J. Beyn, “Stability and paracontrac-
ically inspired models and in the synthesis of provably correct tivity of discrete linear inclusions,” Linear Alg. Applicat., vol. 312, pp.
125–134, 2000.
distributed control laws which produce such emergent behav- [27] B. Mohar, “The Laplacian spectrum of graphs,” in Graph Theory,
iors in man-made systems. Combin. Applicat., Y. A. G. Chartrand, O. R. Ollerman, and A. J.
Schwenk, Eds., 1991, vol. 2, pp. 871–898.
[28] R. Horn and C. R. Johnson, Matrix Analysis. New York: Cambridge
REFERENCES Univ. Press, 1985.
[1] T. Vicsek, A. Czirok, E. Ben Jacob, I. Cohen, and O. Schochet, “Novel [29] M. Berger and Y. Wang, “Bounded semigroups of matrices,” Linear Alg.
type of phase transitions in a system of self-driven particles,” Phys. Rev. Applicat., vol. 166, pp. 21–27, 1992.
[30] M. Ando and M. H. Shih, “Simultaneous contractibility. Siam journal
Lett., vol. 75, pp. 1226–1229, 1995.
on matrix analysis and applications,” Linear Alg. Applicat., vol. 19, pp.
[2] C. Reynolds, “Flocks, birds, and schools: A distributed behavioral
487–498, 1998.
model,” Comput. Graph., vol. 21, pp. 25–34, 1987.
[31] C. Godsil and G. Royle, Algebraic Graph Theory. New York:
[3] A. Czirok, A. L. Barabasi, and T. Vicsek, “Collective motion of self- Springer-Verlag, 2001.
propelled particles: Kinetic phase transition in one dimension,” Phys. [32] A. S. Morse, “Dwell-time switching,” in Proc. 2nd Eur. Control Conf.,
Rev. Lett., vol. 82, pp. 209–212, 1999. 1993, pp. 176–181.
[4] J. Toner and Y. Tu, “Flocks, herds, and schools: A quantitative theory of [33] , “A bound for the disturbance-to-tracking error gain of a super-
flocking,” Phys. Rev. E, vol. 58, pp. 4828–4858, 1998. vised set-point control system,” in Perspectives in Control—Theory and
[5] , “Long range order in a two dimensional xy model: How birds fly Applications, D. N. Cyrot, Ed. New York: Springer-Verlag, 1998, pp.
together,” Phys. Rev. Lett., vol. 75, pp. 4326–4329, 1995. 23–41.
[6] A. S. Mikhailov and D. Zannette, “Noise induced breakdown of collec- [34] , (2001, July) Virtual shells for avoiding collisions. [Online]. Avail-
tive coherent motion in swarms,” Phys. Rev. E, vol. 60, pp. 4571–4575, able: http://entity.eng.yale.edu/controls/publications.html.
1999. [35] B. Bollabas, Random Graphs, 2nd ed. New York: Cambridge Univ.
[7] C. P. Schenk, P. Schutz, M. Bode, and H. G. Purwins, “Interaction of Press, 2001.
self organized quasi particles in a two dimensional reaction-diffusion [36] H. Tanner, A. Jadbabaie, and G. Pappas, “Distributed coordination
system: The formation of molecules,” Phys. Rev. E, vol. 58, pp. strategies for groups of mobile autonomous agents,” ESE Dept., Univ.
6480–6486, 1998. Pennsylvania, Tech. Rep., Dec. 2002.
JADBABAIE et al.: COORDINATION OF GROUPS OF MOBILE AUTONOMOUS AGENTS 1001

Ali Jadbabaie received the B.S. degree (with high A. Stephen Morse (S’62–M’67–SM’78–F’84) was
honors) from Sharif University of Technology, born in Mt. Vernon, NY. He received the B.S.E.E.
Tehran, Iran, the M.S. degree in electrical en- degree from Cornell University, Ithaca, NY, the M.S.
gineering from the University of New Mexico, degree from the University of Arizona, Tucson,
Albuquerque, and the Ph.D. degree in control and and the Ph.D. degree from Purdue University, West
dynamical systems (CDS) from the California Lafayette, IN, in 1962, 1964, and 1967, respectively.
Institute of Technology (Caltech), Pasadena, in From 1967 to 1970, he was associated with the Of-
1995, 1997, and 2000, respectively. fice of Control Theory and Application (OCTA) at
From October 2000 to July 2001, he was a Post- the NASA Electronics Research Center, Cambridge,
doctoral Scholar at the CDS Department at Caltech. MA. Since 1970, he has been with Yale University,
From July 2001 to August 2002, he was a Postdoc- New Haven, CT, where he is currently a Professor of
toral Scholar at the Electrical Engineering Department, Yale University, New Electrical Engineering. His main interest is in system theory, and he has done
haven, CT. Since August 2002, he has been an Assistant Professor in the depart- research in network synthesis, optimal control, multivariable control, adaptive
ment of Electrical and Systems Engineering and the General Robotics Automa- control, urban transportation, vision-based control, hybrid and nonlinear sys-
tion, Sensing, and Perception (GRASP) laboratory at the University of Pennsyl- tems, and, most recently, coordination and control of large grouping of mobile
vania, Philadelphia. His research interests are in real-time optimization-based autonomous agents.
control with applications to Unmanned Aerial Vehicles, distributed coordina- Dr. Morse is a Distinguished Lecturer of the IEEE Control Systems Society,
tion of mobile autonomous vehicles, and robust and optimal control. and a corecipient of the Society’s George S. Axelby Outstanding Paper Award.
He has twice received the American Automatic Control Council’s Best Paper
Award, and is the 1999 recipient of the IEEE Technical Field Award for Control
Systems. He is a member of the National Academy of Engineering.
Jie Lin was born in Shangrao, P.R. China, in 1976. He received the undergrad-
uate degree in physics from Fudan University, Shanghai, P.R. China, the M.S.
degree in physics from Creighton University, Omaha, NE, and the M.S. degree
in electrical engineering from Yale University, New Haven, CT, in 1997, 1999,
and 2000, respectively. He is currently working toward the Ph.D. degree at Yale
University.
His research interests are in the areas of analysis and synthesis of multiagent
coordination control, as well as the applications to mobile sensor networks and
robotics.