Kalman Consensus Strategies and Their Application to Cooperative Control
Sponsorship: AFOSR, NSF. In this paper, we propose discrete-time and continuous-time consensus update schemes motivated by the discrete-time and continuous-time Kalman filters. With certainty information encoded into each agent, the proposed consensus schemes explicitly account for relative confidence in the information that is communicated from each agent in the team. We show mild sufficient conditions under which consensus can be achieved using the proposed schemes in the presence of switching interaction topologies. The Kalman consensus scheme is shown to be input-to-state stable. We show how to exploit this fact in multi-agent cooperative control scenarios.
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 1 Kalman Consensus Strategies and Their Application to Cooperative Control Wei Ren, Member, Randal W. Beard, Senior Member, Derek Kingston, Student Member Abstract In this paper, we propose discrete-time and continuous-time consensus update schemes motivated by the discrete-time and continuous-time Kalman filters. With certainty information encoded into each agent, the proposed consensus schemes explicitly account for relative confidence in the information that is communicated from each agent in the team. We show mild sufficient conditions under which consensus can be achieved using the proposed schemes in the presence of switching interaction topologies. The Kalman consensus scheme is shown to be input-to-state stable. We show how to exploit this fact in multi-agent cooperative control scenarios. Index Terms Information consensus, multi-agent systems, cooperative control, switched systems, Kalman filtering. I. INTRODUCTION During the last two decades there has been a dramatic paradigm shift in the way that computer systems are designed: moving from centralized mainframe computers to networks of less Manuscript submitted for review November, 2004. W. Ren is a Research Associate in the Space Systems Laboratory at the University of Maryland. R. W. Beard is an associate professor and D. Kingston is a graduate research assistant in the Electrical and Computer Engineering Department at Brigham Young University. This work was funded by AFOSR grants F49620-01-1-0091, FA9550-04-1-0209 and F49620-02-C-0094, and by DARPA grant NBCH1020013. R. W. Beard is the corresponding author: beard@ee.byu.edu November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 2 capable, but much less expensive, personal computers. In much the same way, replacing large, expensive, monolithic vehicles with teams of networked vehicles, promises less expensive, more capable systems. In addition, there are applications where a team of vehicles can accomplish objectives that would be impossible for a single vehicle. For example, a formation of networked spacecraft could be used to synthesize a space-based interferometer with base-lines reaching tens to hundreds of kilometers [1], [2]. With teams of vehicles, much of the design complexity is shifted from mechanical hardware design to software that regulates the interaction of the team. In recent years, there has been significant interest and research activity in the area of coordinated and cooperative control [3], [4], [5], [6], [7], [8], [9], [10]. Much of this work assumes the availability of global team knowledge, and/or the ability to plan group actions in a centralized manner. Centralized coordination techniques are suitable if each member of the team has the ability to communicate to a centralized location or if the team is able to share information via a static fully connected network. On the other hand, real-world communication topologies are usually not fully connected. In many cases they depend on the relative position of the vehicles and on other environmental factors and are therefore dynamically changing in time. In addition, wireless communication channels are subject to multi-path, fading and drop-out. Therefore, cooperative control in the presence of real-world communication constraints, becomes a significant challenge. In a recent article we argued that shared information is a necessary condition for cooperation [11]. Shared information may take the form of common objectives, common control algorithms, relative position information, or a world map. If this assertion is true, then information exchange becomes a central issue in cooperative control. In this article, we will refer to the information that is necessary for coordination as the coordination information or coordination variable [12]. In the presence of an unreliable, dynamically changing communication topology, it is not possible for all of the vehicles to have access to identical coordination information. Suppose that a particular cooperation strategy has been devised and shown to work if the team has global access to the coordination information. Cooperation will occur if each member on the team has access to the same information. As an example, consider the meet-for-dinner problem introduced in [11]. In this problem, a group of friends decide to meet for dinner at a particular restaurant but fail to specify a precise time to meet. On the afternoon of the dinner appointment, each individual realizes that November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 3 they are uncertain about the time that the group will meet for dinner. A centralized solution to this problem is for the group to have a conference call, to poll each individual regarding their preferred time for dinner, and to average the answers to arrive at a time that the group will meet for dinner. However, this centralized solution requires that a conference line is available, and that the time of the conference call is known to the group. Since, whatever algorithm was used to convey the time of the conference call to the group, could also have been used to convey the time to meet for dinner, the central problem remains. The information variable in this example is the time that the group will meet for dinner. The particular time is not what is important, but rather that each individual in the group has a consistent understanding of that information. A decentralized solution to the problem would be for each individual to call, one at a time, a subset of the group. Given his current estimate of the meeting time, the individual might update his estimate of the meeting time to be a weighted average of his current meeting time and that of the person with whom he is conversing. The question (which will be answered in this paper) is under what conditions this strategy will enable the entire team to converge to a consistent meeting time. Therefore, if a centralized solution to a cooperation problem, with its associated coordination information, has been devised, then two additional questions must be addressed. First, what algorithms should be employed to ensure that the team is converging to a consistent view of the coordination information in the presence of an unreliable, dynamically changing communication topology? Second, if the action of the group is based on the (dynamically changing) coordination variable, will the cooperative control algorithm be robust with respect to the transient error in the coordination variable across the team? Convergence to a consistent view of the coordination variable in the presence of an unreliable, dynamically changing communication topology is called the consensus problem. Consensus problems have recently been addressed in [13], [14], [15], [16], [17], [11], [18], [19], to name a few. In [14], sufficient conditions are given for consensus of the heading angles of a group of agents under undirected switching interaction topologies. In [15], average consensus problems are solved for a network of integrators using directed graphs. In [11] and [18], an algebraic graph approach is used to show necessary and/or sufficient conditions for consensus of information under time-invariant and switching interaction topologies respectively. In [16], a set-valued Lyapunov function approach is used to consider discrete-time consensus problems with unidirectional November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 4 time-dependent communication links. Previous consensus seeking results reported in the literature do not explicitly account for agent confidence in their instantiation of the coordination variable. Most results assume that each individual in the group has identical confidence in their instantiation of the coordination variable. However, there are many cases where some individuals on the team will have access to better information than others. In cases like these, the consensus algorithm needs to be biased to favor agents with better information. For example, if a team of UAVs is tasked with tracking the location of a group of ground vehicles, the quality of information will be proportional to the relative sensing distance. UAVs that have recently flown close to a ground vehicle should be considered more reliable than those that are sensing from a greater distance, or whose information is old. As another example, in the meet-for-dinner problem described above, if one individual is considered more reliable than the others, his/her information should be weighted more heavily when making the team decision. The primary contribution of this paper is to derive continuous-time and discrete-time consensus strategies, based on a Kalman-filter structure, that asymptotically achieves consensus in the presence of an unreliable, dynamically changing communication topology, giving proper weight to individuals with greater certainty in their coordination variable. In addition, we will show that the Kalman consensus scheme is input-to-state stable (ISS) where the input is the communication noise on each channel and the state is the consensus error between each pair of agents. The ISS property will be exploited to develop a distributed multi-vehicle cooperative control solution to the cooperative timing problem. UAV cooperative timing problems have been investigated recently in the context of battlefield scenarios where the UAVs are required to converge on the boundary of a radar detection area to maximize the element of surprise [20], [12], [3], [21], [22]. Cooperative timing problems also arise in refueling scenarios, fire and hazardous material monitoring, moving area of regard problems, and continuous surveillance problems. In this paper we will investigate a simplified cooperative timing problem that must be accomplished in the presence of an unreliable, dynamically changing communication topology. The paper is organized as follows. In Section II, we give an intuitive, non-rigorous derivation of the Kalman-like consensus strategies, and show their application to the meet-for-dinner problem. Section III contains the main technical results that shows that the proposed consensus strategies November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 5 are convergent under certain mild conditions. In Section IV we show that the Kalman consensus scheme is input-to-state stable. As a corollary, we show that most of the other consensus schemes proposed in the literature, are also ISS. In Section V the ISS property is exploited to develop a distributed solution to the cooperative timing problem. Finally, Section VI contains our conclusions. II. KALMAN-FILTER APPROACH TO MULTI-AGENT CONSENSUS The Kalman filter is used extensively to estimate a system s current state from imprecise measurement data [23], [24], [25]. It is well-known that the Kalman filter is an optimal estimator in the case of Gaussian statistics and that it is the best linear estimator in the case of other statistics [26]. Motivated by the Kalman filter scheme, we treat the final consensus value as the system state, which is unknown a priori but is the final equilibrium state that each agent in the group is expected to achieve. In the consensus problem, each agent has an estimate of the final consensus value. Communication from other agents regarding their estimate of the final consensus value will be regarded as measurement data. In this sense, each agent in the group performs its own estimate of the final consensus value based on the information available to it. Our goal is to guarantee that the information state of each agent achieves the final consensus value. In other words, the objective is to minimize the mean squared error between each agent s estimate of the coordination variable and the final consensus value. The error covariance matrix is interpreted as the confidence that each agent has in its current estimate of the coordination variable, where large covariance indicates low confidence, and small covariance indicates a high degree of confidence. In Section II-A we will derive the Kalman-consensus scheme for a continuous-time update scheme, and in Section II-B we will address the discrete-time case. Analytical properties of the algorithms will be derived in Section III. A. Continuous-time Consensus The standard continuous-time Kalman filter is summarized in Table II-A [27]. The objective of this section is to show how the Kalman filter equations can be used to derive a decentralized information consensus scheme. Let 2 Rm be the a priori unknown information state over which the team is to form consensus. In other words, each information state i will converge to the consensus value as November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 6 System model and measurement model: x_ = Ax + Bu + Gw z = Hx + v x(0) ( x0; P0);w (0;Q); v (0;R) Assumptions: fw(t)g and fv(t)g are white noise processes uncorrelated with x(0) and with each other. R > 0. Initialization: P(0) = P0; ^x(0) = x0 Error covariance update: _P = AP + PAT + GQGT PHTR 1HP Kalman gain: K = PHTR 1 Estimate update: _^ x = A^x + Bu + K(z H^x) TABLE I CONTINUOUS-TIME KALMAN FILTER [27]. t ! 1. Note that the consensus value will depend not only on interaction topologies but on the weighting factors in the update schemes. In this paper we will assume that the consensus state is a constant, which implies that the system dynamics are given by _ = w; where, with reference to Table II-A, A = 0, B = 0, G = Im, and EfwwT g = Q. In the following, we assume that Q(t) > 0 is uniformly lower and upper bounded. Treat the ith information state i as the ith agent s estimate of and suppose that the jth agent communicates j to the ith agent with transmission, or communication noise ij . Also, let gij(t) be a time-varying boolean variable that indicates the presence of an open communication channel from agent j to agent i at time t, i.e., gij(t) = 1 if information is communicated from j to i at time t and zero otherwise. Note that gii(t) 4= 1. Using these definitions, it is clear that November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 7 the measurement model of the ith agent can be given by zi = 0 BBB@ gi1 ( 1 + i1) ... giN ( N + iN ) 1 CCCA = 0 BBB@ gi1I ... giN I 1 CCCA + 0 BBB@ gi1 ( 1 + i1) ... giN ( N + iN ) 1 CCCA ; where, with reference to Table II-A, HT i = gi1I : : : giN I and vi = 0 BBB@ gi1 ( 1 + i1) ... giN ( N + iN ) : 1 CCCA If we define Pi 4= Ef( i )( i )T g and assume that Ef( i )( j )T g = 0, where i 6= j, then Ri 4= EfvivT i g = 0 BBB@ gi1(P1 + i1) : : : 0 ... . . . ... 0 : : : giN (PN + iN ) 1 CCCA ; where ij 4= Ef ij T ijg is assumed to be upper bounded. Therefore, the error covariance update in Table II-A becomes _P i = PiHT i R 1 i HiPi + Q = Pi[ XN j=1 gij(Pj + ij) 1]Pi + Q: Similarly, the Kalman gain is given by Ki = PiHT i R 1 i = gi1Pi(P1 + i1) 1 ginPi(PN + iN ) 1 ; November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 8 and the estimate update is given by _i = Ki(zi Hi i) = Ki 2 6664 0 BBB@ gi1( 1 + i1) ... gin( N + iN ) 1 CCCA 0 BBB@ gi1Im ... giN Im 1 CCCA i 3 7775 = XN j=1 Kijgij( j i + ij); where Ki = [Ki1;Ki2; ;Kin]. Summarizing, we have the following Kalman consensus scheme for the ith agent: _P i = Pi " X j gij(t)(Pj + ij) 1 # Pi + Q (1) Kij = Pi(Pj + ij) 1 (2) _i = Xn j=1 gij(t)Kij (( j + ij) i) : (3) Note that Eq. (1) indicates that the certainty of information increases with communication but decreases with the size of the process noise. In addition, the rate of increase in certainty for the ith agent is inversely proportional to the certainty of the jth agent and the communication noise. Note also that the Kalman gain Kij is reduced if either the communication noise is large, or if the certainty of the jth agent is small (hence Pj large). Note that Eq. (3) is similar to the continuous-time consensus schemes proposed in [14], [15], [11] except that the consensus gain Kij is time-varying in (3), and the communication noise is explicitly included. B. Discrete-time Consensus The standard discrete-time Kalman filter is summarized in Table II-B [27]. Again assuming that is constant we get [k + 1] = [k] + w[k]; where, with reference to Table II-A, A[k] = I, B[k] = 0, G[k] = Im, and Efw[k]w[k]T g = Q[k]. Again letting ij [k] represent the communication noise, the measurement model for the ith agent can be given by November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 9 System model and measurement model: x[k + 1] = A[k]x[k] + B[k]u[k] + G[k]w[k] z[k] = H[k]x[k] + v[k] x(0) ( x0; Px0 );w (0;Q[k]); v[k] (0;R[k]) Assumptions: fw[k]g and fv[k]g are white noise processes uncorrelated with x0 and with each other. R[k] > 0. Initialization: P[0] = Px0 ; ^x0 = x0 Time update: (effect of system dynamics) error covariance: P[k + 1] = A[k]P[k]A[k]T + G[k]Q[k]G[k]T estimte: ^x[k + 1] = A[k]^x[k] + B[k]u[k] Measurement update: (effect of measurement z[k]) error covariance: P[k + 1] = [(P[k + 1] ) 1 + H[k + 1]TR[k + 1] 1H[k + 1]] 1 estimate: ^x[k + 1] = ^x[k + 1] + P[k + 1]H[k + 1]TR[k + 1] 1(z[k + 1] H[k + 1]^x[k + 1] ) TABLE II DISCRETE-TIME KALMAN FILTER [27]. zi[k] = 0 BBB@ gi1[k] ( 1[k] + i1[k]) ... giN [k] ( N[k] + iN [k]) 1 CCCA = 0 BBB@ gi1[k]I ... giN [k]I 1 CCCA [k] + 0 BBB@ gi1[k] ( 1[k] [k] + i1[k]) ... giN [k] ( N[k] [k] + iN [k]) 1 CCCA ; where, with reference to Table II-A, HT i [k] = gi1[k]I : : : giN [k]I and vi = 0 BBB@ gi1[k] ( 1[k] [k] + i1[k]) ... giN [k] ( N[k] [k] + iN [k]) 1 CCCA : November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 10 If we define Pi[k] 4= Ef( i[k] [k])( i[k] [k])T g and assume that Ef( i[k] [k])( j [k] [k])T g = 0, where i 6= j, then Ri[k] 4= Efvi[k]vi[k]T g = 0 BBB@ gi1[k](P1[k] + i1[k]) : : : 0 ... . . . ... 0 : : : giN [k](PN[k] + iN [k]) 1 CCCA ; where ij [k] 4= Ef ij [k] ij [k]T g. Therefore, the time update in Table II-B becomes P i [k + 1] = Pi[k] + Q[k] i [k + 1] = i[k]: The measurement update is given by Pi[k + 1] = (P i [k + 1]) 1 + HT i [k + 1]R 1 i [k][k + 1]Hi[k + 1] 1 = [(Pi[k] + Q[k]) 1 + Xn j=1 gij [k](Pj [k] + ij [k]) 1] 1; i[k + 1] = [k + 1] + Pi[k + 1]HT i [k + 1]R 1 i [k + 1] zi[k + 1] Hi[k + 1] [k + 1] = i[k] + Pi[k + 1] Xn j=1 gij [k](Pj [k] + ij) 1[k] (( j [k] + ij [k + 1]) i[k]) ! : Summarizing, we have the following discrete-time Kalman consensus scheme for the ith agent: Pi[k + 1] = [(Pi[k] + Q[k]) 1 + Xn j=1 gij [k](Pj [k] + ij [k]) 1] 1; (4) i[k + 1] = i[k] + Pi[k + 1] Xn j=1 gij [k](Pj [k] + ij) 1[k] ( j [k] + ij [k + 1]) i[k]) ! : (5) C. Meet for Dinner Example To illustrate, consider the meet-for-dinner problem discussed in the introduction. Suppose that there are N = 10 agents who communicate with exactly one other individual, chosen randomly from the group, for a random length of time. After the communication has expired, the process November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 11 0 10 20 30 4.5 5 5.5 6 6.5 7 7.5 xi No Leader 0 10 20 30 0 0.2 0.4 0.6 0.8 1 1.2 1.4 time Pi 0 10 20 30 4.5 5 5.5 6 6.5 7 7.5 Leader 0 10 20 30 0 0.2 0.4 0.6 0.8 1 1.2 1.4 time Fig. 1. Continuous-time meet-for-dinner simulation. The subplot in the upper left shows the evolution of the coordination variable assuming that all agents begin with equally confident covariance. The subplot in the lower left shows the associated covariance. The subplots on the right show identical data where the agent with initial time i = 7 has an initial covariance of Pi = 0:001. is repeated. Figure 1 shows the state and variance plots under the continuous Kalman consensus scheme (1) (3) where the initial state is uniformly assigned. The subplots on the left show the arrival times and variance when the initial variances are uniformly assigned. The subplots on the right show the arrival times and variances when the variance of the agent with initial arrival time i = 7 is given an initial variance of Pi = 0:001, which is significantly lower than the other agents. Note that in this case, the final consensus value is influenced to a greater degree by this agent. Figure 2 shows similar plots using the discrete Kalman consensus scheme (4) (5). Both the continuous-time and discrete-time simulations use the values ij = 0:1, Q = 0:1. III. CONVERGENCE RESULTS The objective of this section is to state some technical properties of the algorithms given in Eqs. (1) (3) and Eqs. (4) (5). For notational simplicity, we will focus on the case where each information state is a scalar. The vector case reduces to the scalar case if Pi0 is a diagonal matrix. The general case where Pi0 is non-diagonal is currently a topic of research. In Section IIIA, we will introduce some notation and results from graph theory and non-negative matrices that will be used in the convergence arguments. In Section III-B we analyze the continuous-time case and in Section III-C we analyze the discrete-time case. November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 12 0 10 20 30 4.5 5 5.5 6 6.5 7 7.5 xi No Leader 0 10 20 30 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 time Pi 0 10 20 30 4.5 5 5.5 6 6.5 7 7.5 Leader 0 10 20 30 0 0.2 0.4 0.6 0.8 1 1.2 1.4 time Fig. 2. Discrete-time meet-for-dinner simulation. The subplot in the upper left shows the evolution of the coordination variable assuming that all agents begin with equally confident covariance. The subplot in the lower left shows the associated covariance. The subplots on the right show identical data where the agent with initial time i = 7 has an initial covariance of Pi = 0:001. A. Preliminaries Let A = fAiji 2 Ig, where I = f1; 2; ; ng, be a set of n agents among whom consensus is desired. A directed graph G will be used to model the interaction topology among these agents. In G, the ith vertex represents the ith agent Ai and a directed edge from Ai to Aj denoted as (Ai;Aj) represents a unidirectional information exchange from Ai to Aj , that is, agent j receives information from agent i, (i; j) 2 I. If the information flows from agent i to agent j, agent i is called the parent of j, and agent j is called the child of i. A directed path in graph G is a sequence of edges (Ai1 ;Ai2); (Ai2 ;Ai3); (Ai3 ;Ai4); in that graph. Graph G is called strongly connected if there is a directed path from Ai to Aj and Aj to Ai between any pair of distinct vertices Ai and Aj , 8(i; j) 2 I. A directed tree is a directed graph, where every node, except the root, has exactly one parent. A spanning tree of a directed graph is a directed tree formed by graph edges that connect all the vertices of the graph [28]. We say that a directed graph has a spanning tree if there exists a spanning tree that is a subset of the directed graph. Fig. 3 shows a directed graph with more than one possible spanning trees. The double arrows denote one possible spanning tree with A5 as the parent. Spanning trees with A1 and A4 as the parent, are also possible. As a comparison, Figs. 4 shows two cases where the graph does not have a spanning tree. November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 13 X_Y^AZ]5 [\ (0 $ _X^YA]Z1 \[ _X^YA]Z4 \[px : _X^YA]Z2 \[ v X_Y^AZ]3 [\ Fig. 3. A directed graph that has more than one possible spanning trees, but is not strongly connected. One possible spanning tree is denoted with double arrows. _X^YA]Z3 \[ /X_Y^AZ]1 [\ X_Y^AZ]3 [\ _X^YA]Z1 \[ X_Y^AZ]4 [\ >>} }}}}}}}}} (a) X_Y^AZ]2 [\ O _X^YA]Z4 \[ >>} }}}}}}}}} (b) _X^YA]Z2 \[ L Fig. 4. (a) A directed graph that has two leaders, and hence does not contain a spanning tree. (b) A directed graph that has two isolated groups, and hence does not contain a spanning tree. The interaction topology may change dynamically. Let G = fG1; G2; ; GMg denote the set of all possible directed interaction graphs defined for A. It is obvious that G has a finite number of elements and that G(t) 2 G. The union of a set of directed graphs fGi1 ; Gi2 ; ; Gimg G is a directed graph with vertices given by Ai, i 2 I and edge set given by the union of the edge sets of Gij , j = 1; ;m. We will assume throughout the paper that the interaction topology does not switch infinitely fast. Let Mn(R) represent the set of all n n real matrices. Given a matrix A = [aij ] 2 Mn(R), the directed graph of A, denoted by (A), is the directed graph on n vertices Vi, i 2 I, such that there is a directed edge in (A) from Vj to Vi if and only if aij 6= 0 [29]. For example, the November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 14 directed graph of the matrix A = 2 666666664 0 0 0 0 a15 a21 0 0 0 a25 0 a32 0 0 0 a41 0 0 0 0 0 0 0 a54 0 3 777777775 ; where aij 6= 0, corresponds to the graph in Fig. 3. A matrix A = [aij ] 2 Mn(R) is nonnegative, denoted as A 0, if all its entries are nonnegative. Furthermore, if all its row sums are +1, A is said to be a (row) stochastic matrix [29]. A stochastic matrix P is called indecomposable and aperiodic (SIA) if limn!1 Pn = 1yT , where y is a column vector, and 1 denotes an n 1 column vector with all the entries equal to 1 [30]. For nonnegative matrices, A B implies that A B is a nonnegative matrix. It is easy to verify that if A B, for some > 0, then the directed graph of B is a subset of the directed graph of A. Two n n nonnegative matrices are said to be of the same type if their zero elements are in the same locations [30]. We will use the notation P Q to denote that P and Q are of the same type. Lemma 3.1: Given n n nonnegative matrices P, Q, R, and S, if P R and Q S, then (P + Q) (R + S) and PQ RS. Moreover, if a time-varying nonnegative matrix M(t) with continuous entries is of a fixed type for t 2 [t1; t2], where t1 < t2, then M(t) R t2 t1 M(t)dt. Proof: Trivial. Let i 2 R, i 2 I, represent the ith information state associated with the ith agent. The set of agents A is said to achieve consensus asymptotically if for any i(0), i 2 I, k i(t) j(t)k ! 0 as t ! 1 for each (i; j) 2 I. B. Continuous-time Consensus The following theorem is our main technical result. Theorem 3.2: Given switching interaction topologies and zero transmission or communication noise, the Kalman consensus scheme given in Eqs. (1) (3) achieves asymptotic consensus if there exist infinitely many consecutive uniformly bounded time intervals such that the union of the interaction graph across each interval has a spanning tree. November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 15 The proof of this theorem depends upon the following five lemmas. Lemma 3.3: Let C(t) = [cij(t)] 2 Mn(R) be piecewise continuous, where cij 0, i 6= j, and P j cij = 0. Let C(t; t0) be the corresponding transition matrix. Then C(t; t0) is a stochastic matrix with positive diagonal entries for any t t0. Proof: From [31], we know that C(t; t0) = I + Z t t0 C( 1) d 1 + Z t t0 C( 1) Z 1 t0 C( 2) d 2 d 1 + : (6) Noting that C(t)1 = 0, where 1 is a column vector of ones, we can verify that C(t; t0)1 = 1. Note that C(t) can be written as B(t) In, where B(t) is a nonnegative matrix and is a constant greater than max 2[t0;t] maxi2I jcii( )j. It is straightforward to see that d dt C(t; t0) = C(t) C(t; t0) and d dt [ B(t; t0)e (t t0)] = B(t) B(t; t0)e (t t0) B(t; t0)e (t t0) = (B(t) In) B(t; t0)e (t t0) = C(t) B(t; t0)e (t t0); and that C(t0; t0) = B(t0; t0)e (t0 t0) = I. Therefore, we obtain C(t; t0) = B(t; t0)e (t t0). From Eq. (6), it is straightforward to see that B(t; t0) is nonnegative and has positive diagonal entries. Therefore, it follows that C(t; t0) is nonnegative and has positive diagonal entries. Combining these arguments implies that the transition matrix C(t; t0) is a stochastic matrix with positive diagonal entries. Lemma 3.4: Let C(t) = [cij(t)] 2 Mn(R) and C = [ cij(t)] 2 Mn(R) be continuous on t 2 [ ; s], where s > such that cij(t) 0 and cij(t) 0, 8i 6= j, and Pn j=1 cij(t) = Pn j=1 cij(t) = 0. Let C(s; ) and C(s; ) be the corresponding transition matrices. Also let the graph associated with C(t) be fixed for t 2 [ ; s] and suppose that C(t) corresponds to the same fixed graph as C(t). Then the graph of C(t) is a subset of the graph of C(s; ) and C(s; ) C(s; ). November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 16 Proof: Let C(t) = B(t) In, where B(t) is a nonnegative matrix and is a constant greater than maxt2[ ;s] maxi2I jcii(t)j. Following Lemma 3.3, we know that C(s; ) = B(s; )e (s ). Note that the graphs associated with C(t) and B(t) are the same, so are the graphs associated with C(s; ) and B(s; ). Therefore from Eq. (6), we can see that B(s; ) R s B( 1)d 1, where R s B( 1)d 1 B(t) for t 2 [ ; s], or in other words, the graph associated with B(t) for t 2 [ ; s] is a subset of the graph associated with B(s; ). Therefore, the graph associated with C(t) for t 2 [ ; s] is a subset of the graph associated with C(s; ). Note that C(s; ) = B (s; )e (s ), where C = B In. In order to show that C is of the same type as C, we need to show that B is of the same type as B . Note that B and B are of the same type since they correspond to the same graph. By writing B and B as in Eq. (6) and comparing each term, Lemma 3.1 implies that each corresponding term is of the same type, which in turn implies that B(s; ) and B ( s; ) are of the same type. Lemma 3.5: Let SA = fA1;A2; ;A g be a set of stochastic matrices with positive diagonal entries. If the graph associated with Ai has a spanning tree, then Ai is SIA. If the union of the graphs of matrices Ai, i = 1; ; , has a spanning tree, then the matrix product i=1Ai is SIA. Proof: The first statement is shown in Corollary 3.5 and Lemma 3.7 in [18]. For the second statement, note that the product of stochastic matrices is still a stochastic matrix. Also note that i=1Ai P i=1 Ai for some > 0 according to Lemma 2 in [14]. Since the union of the graphs of matrices in SA has a spanning tree, it is obvious that the graph associate with P i=1 Ai has a spanning tree. Therefore, it can be seen that the graph associated with the matrix product has a spanning tree, which in turn implies, from the first statement of the Lemma, that the matrix product is SIA. Lemma 3.6: Let C(t) = [cij(t)] 2 Mn(R) be piecewise continuous for t 2 [ ; s], where s > is bounded, cij 0, i 6= j, and P j cij = 0. If the union of the directed graphs of matrix C(t) for t 2 [ ; s] has a spanning tree, then the transition matrix C(s; ) is SIA. Proof: Note that C(s; ) = C(s; t ) C(t ; t 1) C(t1; ), where tj , j = 1; ; , denotes the times when C(t) is discontinuous. From Lemma 3.4, we know that the graph associated with C(t) for each t 2 [ti 1; ti] is a subset of the graph associated with C(ti; ti 1), i = 1; ; +1. In other words, if the union of the directed graphs of matrix C(t) has a spanning tree, so does the union of the directed graphs of the corresponding transition matrices. Also note from Lemma 3.4 that each C(ti; ti 1) is a stochastic matrix with positive diagonal entries. The proof then follows November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 17 from Lemma 3.5. Before moving on, we need the following definition from [30]. Given a stochastic matrix S = [sij ] 2 Mn(R), define (S) = 1 min i1;i2 X j min(si1j ; si2j): Note that (S) 1 for any stochastic matrix S. If (S) < 1, S is called a scrambling matrix. (S) = 0 if and only if the rows of S are identical. The introduction of will be useful for the proof of Theorem 3.2. Lemma 3.7: (See [30].) Let S = fS1; S2; ; Skg be a finite set of SIA matrices with the property that for each sequence Si1 ; Si2 ; ; Sij of positive length, the matrix product SijSij 1 Si1 is SIA. Then for each infinite sequence Si1 ; Si2 ; there exists a column vector such that lim j!1 SijSij 1 Si1 = 1 T : (7) In addition, in the case that S is an infinite set, (W) < 1, where W = Sk1Sk2 SkNt+1 and Nt is defined as the number of different types of all n n SIA matrices. Furthermore, if there exists a constant 0 d < 1 satisfying (W) d, then Eq. (7) also holds. Proof: See Lemma 4 and the concluding remarks in [30]. Proof of Theorem 3.2: From Eq. (1), we see that Pi > 0 is uniformly lower bounded since Qi is uniformly lower bounded. Also noting that Pi[ P j gij(t)(Pj + ij) 1]Pi P2 i =(Pi + ii), we know that Pi is uniformly upper bounded. From Eq. (2), we can see that Kij(t) > 0, 8i 6= j, is uniformly lower and upper bounded. Let t0; t1; be an infinite time sequence corresponding to the times at which graph G(t) switches topology. Since the interaction topology cannot switch infinitely fast, we assume that ti ti 1 tL, 8i = 1; 2; . Note that each interval [ti 1; ti) can be divided into finite or infinite number of subintervals such that the length of each subinterval is greater than or equal to tL but less than or equal to tM = 2tL and the graph on each subinterval is fixed. Relabel these subintervals as s0; s1; . Without transmission or communication noise, Eq. (3) can be rewritten in matrix form as _ = (t) , where = [ 1; ; n]T and (t) = [ ij(t)]. As mentioned above, the solution November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 18 can be denoted as (t) = (t; sj) (sj ; sj 1) (s1; s0) (s0), where is the transition matrix. Noting that ij(t) = gij(t)Kij(t), 8j 6= i, and P j ij(t) = 0, we know that (t) is continuous and satisfies the hypothesis of Lemma 3.4 for t 2 [sj 1; sj ]. Noting that Kij(t) is uniformly lower and upper bounded, we know that each nonzero, that is, positive, entry ij , where i 6= j, satisfies the property that ij 2 [ L; M], which is a compact set. In addition, ii = P j6=i ij , which is also in a compact set. In the case that the interaction topology is switching with time, there are a finite number of possible interaction topologies. For each possible interaction topology, note that matrix (t) has the same structure in the sense that positive, zero, and negative entries are in the same places for t 2 [sj 1; sj ]. From Lemma 3.4, each transition matrix (sj ; sj 1) is a stochastic matrix, where tL sj sj 1 tM, and (sj ; sj 1) is of constant type over this interval, for each possible interaction topology. Combining the above arguments with the fact that (sj ; sj 1) is a continuous function of ij(t) for t 2 [sj 1; sj ], we see that each nonzero entry of (sj ; sj 1) is lower bounded for each possible interaction topology. It is straightforward to see that there are only finitely many types for (sj ; sj 1). We know that there exists a sequence of unions of the directed interaction graphs across some time intervals and each union is uniformly bounded and has a spanning tree. Thus the transition matrix (k) for each union is a product of finitely many matrices (ski ; ski 1). From Lemma 3.1, the type of (k) is uniquely decided by the order and type of each element in its product. Also, from Lemma 3.6, we know that each (k) is SIA. In addition, noting that the graph associated with each (k) has a spanning tree, we see that any number of products of (k) is also SIA according to the second part of Lemma 3.5. Noting that (k) can only have finitely many types, we see that for each type of (k) its nonzero entries are lower bounded. Let W = (j1) (j2) (jNt+1). From the second part of Lemma 3.7, we know that (W) < 1. Note that W can only have finite many types, denoted as Wt. In order to show that (W) d < 1, it is sufficient to show that for each type, there exists a 0 di < 1 such that (W) di. This can be verified by noting that the nonzero entries of W are lower bounded for each type. Let d = maxfd1; d2; ; dWtg. It is obvious that (W) d. From Lemma 3.7, we can show that (t) ! 1 T (0), where is a nonnegative column vector. In previous results on consensus [14], [18], the coefficient matrix C(t) was assumed to be piecewise constant with finite dwell time, and elements drawn from a finite set. The following corollary of Theorem 3.2 shows that these conditions can be relaxed. Corollary 3.8: Let _ = C(t) , where C(t) = [cij(t)] 2 Mn(R) is piecewise continuous, November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 19 cij 0, i 6= j, P j cij = 0, and each nonzero entry cij , i 6= j, is both uniformly lower and upper bounded. Under switching interaction topologies, i achieves consensus if there exist infinite many consecutive uniformly bounded time intervals such that the union of the interaction graph across each such interval has a spanning tree. C. Discrete-time Consensus Theorem 3.9: Given switching interaction topologies and zero transmission or communication noise, the discrete-time Kalman consensus scheme listed in Eq. (4) (5) achieves asymptotic consensus if there exist infinitely many consecutive uniformly bounded time intervals such that the union of the interaction graph across each interval has a spanning tree. Proof: Without transmission or communication noise, Eq. (5) can be written as i[k + 1] = " 1 Pi[k + 1] X j6=i gij [k](Pj [k] + ij) 1 # i[k] + Pi[k + 1] X j6=i gij [k](Pj [k] + ij) 1 j [k] : (8) Note that each weighting factor of is less than or equal to 1 and the sum of the weighting factors of is equal to 1, where 2 I. Letting = [ 1; ; n]T , we can rewrite Eq. (8) as [k + 1] = D[k] [k], where it can be verified that D[k] is a stochastic matrix with positive diagonal entries. In addition, for each possible interaction topology, D[k] is of the same type and its nonzero entries are lower bounded. We know that there exists a sequence of unions of the directed interaction graphs across some time intervals and each union is uniformly bounded and has a spanning tree. Let D(i) be the product of matrices D[k] over the ith union. Note that each D(i) is SIA from Lemma 3.5. As a result, the proof follows the same reasoning as the proof of Theorem 3.2 with D(i) playing the role of (k). IV. CONSENSUS SCHEMES ARE INPUT-TO-STATE STABLE We are primarily interested in the application of consensus algorithms to cooperative control problems. In this section we will explore a control architecture where a consensus algorithm is in cascade with a coordination algorithm, as shown in Figure 5. Our purpose in this section November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 20 Communication Network Consensus Algorithm on Vehicle Coordination Algorithm on Vehicle Vehicle Fig. 5. The control architecture consists of a consensus algorithm in cascade with a coordination algorithm. The consensus algorithm receives information from the communication network to produce a value of the coordination variable i. The coordination algorithm uses the coordination variable i to produce a command to the vehicle ui. We assume that identical consensus and coordination algorithms are implemented on each vehicle. is to derive conditions on the consensus and coordination algorithms that guarantee that the cooperation objective is achieved. Toward that end, rewrite Eq. (3) as _i = Xn j=1 gij(t)Kij ( j i) + Xn j=1 gij(t)Kij ij : (9) Letting xij = i j and x = (x11; x12; : : : ; x1n; x21; : : : ; xnn)T , we get the state-space model x_ = A(t)x + B(t) (10) where is a column vector created by stacking the communication noise terms ij , and the elements of A(t) and B(t) are linear combinations of gijKij(t) and can be easily constructed from Eq. (9). The vector x represents the total consensus error. Theorem 4.1: Under the hypothesis of Theorem 3.2, the Kalman consensus scheme given by Eqs. (1), (2), and (10) is input-to-state stable. The proof of this theorem requires the following two lemmas. Lemma 4.2: Under the hypothesis of Theorem 3.2, if the communication error is zero, then the consensus error x is uniformly stable. Proof: Note that (t) = (t; t0) (t0), where (t; t0) is a stochastic matrix according to Lemma 3.3. As a result, we see that the ith coordination variable i(t) is equal to a weighted average of all agents initial coordination variables communicating with agent i. Since a weighted November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 21 average can never be greater (or smaller) than any one of the components in the average, we know that i(t) 2 [minj j(t0); maxj j(t0)] for all t and i. Then it is straightforward to see that kx(t)k1 kx(t0)k1 ; for t t0: Lemma 4.3: The norm of B(t) in Eq. (10) is bounded. Proof: Since B(t) is composed of linear combinations of Kij(t), if kKij(t)k is bounded for each (i; j), then kB(t)k will also be bounded. kKijk was shown to be bounded in the proof of Theorem 3.2. Proof of Theorem 4.1: By Lemma 4.2, the Kalman consensus error is uniformly stable. By Theorem 3.2, k i jk ! 0 as t ! 1 for all (i; j). Since each element of x ! 0, then kxk ! 0 as t ! 1 and we conclude uniform asymptotic stability. Any linear system that is uniformly asymptotically stable is also uniformly exponentially stable [31]. Additionally, linear uniformly exponentially stable systems with kB(t)k < for finite are bounded-input boundedoutput stable [31]. Since the Kalman consensus error governed by Eq. (10) is a linear uniformly asymptotically stable system with kB(t)k bounded, it is ISS. Corollary 4.4: If the continuous-time consensus schemes presented in [11], [18], [14], and [15] are augmented with communication noise, then the representation of these schemes that is equivalent to Eq. (10) is ISS. Proof: The difference between each of these schemes and Eq. 3 is that the consensus gain Kij(t) is time invariant. Therefore, from the proof of Theorem 4.1 it is clear that they are ISS. Referring to Figure 5 we see that the combination of the communication network and the consensus scheme is an ISS system. It is well known that the cascade combination of two ISS systems is also ISS. Therefore if the feedback loop containing the coordination algorithm and the ith vehicle is ISS from the consensus error to the cooperation objective, then the total system will be ISS from the communication noise to the cooperation objection. This concept is shown schematically in Figure 6 and can be summarized by the following Theorem. Theorem 4.5: If a consensus scheme is ISS from the communication noise to the consensus error and a coordination scheme is ISS from the consensus error to the cooperation objective, then the cascade interconnection of the two (see Fig. 6) is ISS from the communication noise November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 22 Consensus Scheme Coordination Scheme Cooperation Objective Fig. 6. The distributed cooperative control problem can be thought of as a cascade connection between the consensus algorithm and the coordination algorithm. If both are ISS, then the cascade system will be ISS to the cooperation objective. V. ILLUSTRATIVE EXAMPLE - DISTRIBUTED COOPERATIVE TIMING FOR A TEAM OF UAVS Suppose that a team of UAVs, flying at distinct altitudes, is tasked to simultaneously visit a pre-specified location. For simplicity, also assume that paths with appropriate velocities have been precomputed for each UAV as shown in Figure 7. Algorithms that achieve this functionality are described in [21]. 30 20 10 0 10 20 30 10 0 10 20 30 40 50 X position Y position Fig. 7. Cooperative timing scenario with five UAVs. We will also assume that each UAV has autopilot functionality that maintains the UAV on its pre-defined path, but that the velocity along the path can be adjusted to meet the simultaneous arrival objective [32], [33]. We will assume that the velocity hold autopilot has been designed November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 23 such that v_i = i (vc i vi) (11) where i > 0, vi is the velocity, and vc i is the commanded velocity for the ith UAV. Let Li denote the length of the path remaining to the target, then _L i = vi: Given Li and vi, the ith UAV can estimate its expected time-of-arrival as i = Li vi : Therefore _i = vi _Li Liv_i v2 i = 1 i i vc i vi vi : The cooperation objective for this problem is that each UAV arrives at its destination simultaneously, i.e. i j = 0 for each (i; j). The coordination variable for this problem is chosen as the arrival time. Therefore i represents the ith UAVs understanding of the team arrival time. Letting vc i = vi + vi i i ( i i 1) (12) we get that _i = i + i: Note that ( _i _j) = i + i + j j = ( i j) + ( i j) ; and that the system _ = + u is input-to-state stable. In fact we have that j (t)j e (t t0) (t0) + sup t0 t ju( )j : Therefore, from Theorem 4.5, the combination of the consensus strategy given by Eqs. (1) (3) and the velocity controller given by Eq. (12) is input-to-state stable with the input being November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 24 communication noise and the state consisting of both the consensus discrepancy i j and the UAV arrival discrepancy i j . The cooperative timing scenario was simulated with an unreliable switching communication topology. The team is connected in the graph shown in Fig. 8 where each link is only available 70 percent of the time. When an agent receives communication it updates its estimate of using 1 2 3 4 5 Fig. 8. Union of possible communication topologies. the Kalman consensus scheme of Section II-A. In between consensus updates, agents control their velocity using Equation (12). Five agents were given a single target at which to arrive simultaneously. Fig. 7 shows the application scenario, where each red circle represents an agent, the blue circles represent threats, the blue square represents the target, and the green lines are the waypoint paths. In the first case, communication noise was set to zero and each agent started with approximately the same confidence in its estimate of . A plot of for each vehicle is shown in Fig. 9(a) and Fig. 9(b) shows for each vehicle. As can be seen, each agent in the team achieves agreement using consensus, adjusts its velocity to match i, and arrives at the target in approximately 20 seconds. In the second case, significant communication noise is added. is shown for each vehicle in Fig. 10(a) and for each vehicle is shown in Fig. 10(b). As can be seen, each agent in the team achieves approximate agreement using consensus where the error in agreement is due to the communication noise. November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 25 0 2 4 6 8 10 12 14 16 18 20 18 19 20 21 22 23 24 25 26 (a) Estimated team time of arrival, , for each agent 0 2 4 6 8 10 12 14 16 18 20 18 19 20 21 22 23 24 25 26 (b) Actual time of arrival, , for each agent Fig. 9. Cooperative timing with no communication noise. 0 2 4 6 8 10 12 14 16 18 20 18 19 20 21 22 23 24 25 26 (a) Estimated team time of arrival, , for each agent 0 2 4 6 8 10 12 14 16 18 20 18 19 20 21 22 23 24 25 26 (b) Actual time of arrival, , for each agent Fig. 10. Cooperative timing with significant communication noise. VI. CONCLUSION This paper has considered the problem of consensus seeking with relative uncertainty in distributed multi-agent systems. We have proposed discrete-time and continuous-time Kalman filter-like consensus schemes that are appropriate when different agents in the group may have different confidences about their information state. Sufficient conditions have been shown for consensus seeking using the proposed consensus schemes under switching interaction topologies. November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 26 Consensus schemes were shown to be input-to-state stable from the communication noise to the consensus error. This fact was exploited in an application to a UAV distributed cooperative timing scenario. REFERENCES [1] A. Robertson, G. Inalhan, and J. P. How, Formation control strategies for a separated spacecraft interferometer, in Proceedings of the American Control Conference, San Diego, June 1999. [2] R. W. Beard, J. Lawton, and F. Y. Hadaegh, A coordination architecture for formation control, IEEE Transactions on Control Systems Technology, vol. 9, no. 6, pp. 777 790, November 2001. [3] J. Bellingham, M. Tillerson, A. Richards, and J. P. How, Multi-task allocation and path planning for cooperating UAVs, in Cooperative Control: Models, Applications and Algorithms. Conference on Coordination, Control and Optimization, November 2001, pp. 1 19. [4] R. Emery, K. Sikorski, and T. Balch, Protocols for collaboration, coordination and dynamic role assignment in a robot team, in Proceedings of the IEEE International Conference on Robotics and Automation, Washington DC, May 2002, pp. 3008 3015. [5] G. Inalhan, D. M. Stipanovic, and C. J. Tomlin, Decentralized optimization with application ot multiple aircraft coordination, in Proceedings of the IEEE Conference on Decision and Control, Las Vegas, NV, 2002, pp. 1147 1155. [6] W. Kang, N. Xi, and A. Sparks, Formation control of autonomous agents in 3D workspace, in Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, April 2000, pp. 1755 1760. [7] N. E. Leonard and E. Fiorelli, Virtual leaders, artificial potentials and coordinated control of groups, in Proceedings of the IEEE Conference on Decision and Control, Orlando, Florida, December 2001, pp. 2968 2973. [8] P. Ogren, M. Egerstedt, and X. Hu, A control Lyapunov function approach to multiagent coordination, IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 847 851, October 2002. [9] D. J. Stilwell and B. E. Bishop, Platoons of underwater vehicles, IEEE Control Systems Magazine, vol. 20, no. 6, pp. 45 52, December 2000. [10] H. G. Tanner, V. Kumar, and G. J. Pappas, The effect of feedback and feedforward on formation ISS, in Proceedings of the IEEE International Conference on Robotics and Automation, Washington DC, May 2002, pp. 3448 3453. [11] W. Ren, R. W. Beard, and T. W. McLain, Coordination variables and consensus building in multiple vehicle systems, in Cooperative Control: A Post-Workshop Volume 2003 Block Island Workshop on Cooperative Control, V. Kumar, N. E. Leonard, and A. S. Morse, Eds., vol. 309. Springer-Verlag Series: Lecture Notes in Control and Information Sciences, 2004, pp. 171 188. [12] T. W. McLain and R. W. Beard, Coordination variables, coordination functions, and cooperative timing missions, AIAA Journal of Guidance, Control, and Dynamics, (to appear). [13] J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations, IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1465 1476, September 2004. [14] A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, vol. 48, no. 6, pp. 988 1001, June 2003. [15] R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520 1533, September 2004. November 24, 2004 DRAFT IEEE TRANSACTIONS ON AUTOMATIC CONTROL, SUBMITTED FOR REVIEW. 27 [16] L. Moreau, Stability of multi-agent systems with time-dependent communication links, IEEE Transactions on Automatic Control, 2004, (to appear). [17] Z. Lin, M. Broucke, and B. Francis, Local control strategies for groups of mobile autonomous agents, IEEE Transactions on Automatic Control, vol. 49, no. 4, pp. 622 629, 2004. [18] W. Ren and R. W. Beard, Consensus seeking in multi-agent systems under dynamically changing interaction topologies, IEEE Transactions on Automatic Control, (to appear). [19] L. Xiao and S. Boyd, Fast linear iterations for distributed averaging, Systems and Control Letters, vol. 53, pp. 65 78, 2004. [20] P. Chandler, S. Rasumussen, and M. Pachter, UAV cooperative path planning, in Proceedings of the AIAA Guidance, Navigation, and Control Conference, Denver, CO, August 2000, aIAA Paper No. AIAA-2000-4370. [21] R. W. Beard, T. W. McLain, M. Goodrich, and E. P. Anderson, Coordinated target assignment and intercept for unmanned air vehicles, IEEE Transactions on Robotics and Automation, vol. 18, no. 6, pp. 911 922, December 2002. [22] T. McLain and R. Beard, Cooperative rendezvous of multiple unmanned air vehicles, in Proceedings of the AIAA Guidance, Navigation and Control Conference, Denver, CO, August 2000, paper no. AIAA-2000-4369. [23] B. Barshan and H. F. Durrant-Whyte, Inertial navigation systems for mobile robots, IEEE Transactions on Robotics and Automation, vol. 11, no. 3, pp. 328 342, June 1995. [24] M. E. Cannon, Integrated GPS-INS for high-accuracy road positioning, Journal of Surveying Engineering, vol. 118, no. 4, pp. 103 117, November 1992. [25] S. Ronnback, Development of an INS/GPS navigation loop for an UAV, Master s thesis, Lule a University of Technology, 2000. [26] A. H. Jazwinski, Stochastic Processes and Filtering Theory, ser. Mathematics in Science and Engineering. New York, New York: Academic Press, Inc., 1970, vol. 64. [27] F. L. Lewis, Optimal Estimation: With an Introduction to Stochastic Control Theory. New York, New York: John Wiley & Sons, 1986. [28] C. Godsil and G. Royle, Algebraic Graph Theory. New York: Springer Graduate Texts in Mathematics #207, 2001. [29] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 1985. [30] J. Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices, Proceedings of the American Mathematical Society, vol. 15, pp. 733 736, 1963. [31] W. J. Rugh, Linear System Theory, 2nd ed. Englewood Cliffs, New Jersey: Prentice Hall, 1996. [32] D. Kingston, R. Beard, T. McLain, M. Larsen, and W. Ren, Autonomous vehicle technologies for small fixed wing UAVs, in AIAA 2nd Unmanned Unlimited Systems, Technologies, and Operations Aerospace, Land, and Sea Conference and Workshop & Exhibit, San Diego, CA, September 2003, paper no. AIAA-2003-6559. [33] R. Beard, D. Kingston, M. Quigley, D. Snyder, R. Christiansen, W. Johnson, T. McLain, and M. Goodrich, Autonomous vehicle technologies for small fixed wing uavs, AIAA Journal of Aerospace, Computing, Information, and Communication, 2004, (to appear). November 24, 2004 DRAFT