Information Consensus and its Application in Multi-vehicle Cooperative Control
In the last two decades, advances in networking and distributed computing have facilitated a paradigm shift from large, monolithic mainframe computers to networks of less expensive, less powerful workstations. One motivation for multi-vehicle systems is to achieve the same gains for mechanically controlled systems as has been gained in distributed computation. Rather than having a single monolithic (and therefore expensive and complicated) machine do everything, the hope is that many inexpensive, simple machines, can achieve the same, or enhanced functionality, through coordination. In essence, the objective is to replace expensive complicated hardware with software and multiple copies of simple hardware. There are numerous applications for multi-vehicle systems including space-based observations, future combat systems, smart homes, enhanced surveillance systems, hazardous material handling systems, and reconfigurable sensing systems.
Information Consensus and its Applications in Multi-vehicle Cooperative Control Wei Ren, Member, IEEE, Randal W. Beard, Senior Member, IEEE, Ella M. Atkins, Member, IEEE In the last two decades, advances in networking and distributed computing have facilitated a paradigm shift from large, monolithic mainframe computers to networks of less expensive, less powerful workstations. One motivation for multi-vehicle systems is to achieve the same gains for mechanically controlled systems as has been gained in distributed computation. Rather than having a single monolithic (and therefore expensive and complicated) machine do everything, the hope is that many inexpensive, simple machines, can achieve the same, or enhanced functionality, through coordination. In essence, the objective is to replace expensive complicated hardware with software and multiple copies of simple hardware. There are numerous applications for multi-vehicle systems including space-based observations, future combat systems, smart homes, enhanced surveillance systems, hazardous material handling systems, and reconfigurable sensing Manuscript submitted for review June, 2005. W. Ren is a research associate in the Space Systems Laboratory, University of Maryland, College Park, MD 20742. R. W. Beard is an associate professor in the Department of Electrical and Computer Engineering, Brigham Young University, Provo, UT 84602. E. M. Atkins is an assistant professor in the Space Systems Laboratory, University of Maryland, College Park, MD 20742. W. Ren is the corresponding author. Email: weiren@ieee.org 1 systems. Cooperative control for multi-vehicle systems can be categorized as either formation control problems with applications to mobile robots, unmanned air vehicles (UAVs), autonomous underwater vehicles (AUVs), satellites, aircraft, spacecraft, and automated highway systems, or non-formation cooperative control problems such as task assignment, payload transport, role assignment, air traffic control, timing, and search. The cooperative control of multi-vehicle systems poses significant theoretical and practical challenges. For cooperative control strategies to be successful, numerous issues must be addressed, including the definition and management of shared information among a group of vehicles to facilitate the coordination of these vehicles. In cooperative control problems, shared information may take the form of common objectives, common control algorithms, relative position information, or a world map. Information necessary for cooperation may be shared in a variety of ways. For example, relative position sensors may enable vehicles to construct state information for other vehicles [1], knowledge may be communicated between vehicles using a wireless network [2], or joint knowledge might be pre-programmed into the vehicles before a mission begins [3]. For cooperative control strategies to be effective, a team of vehicles must be able to respond to unanticipated situations or changes in the environment that are sensed as a cooperative task is carried out. As the environment changes, the vehicles on the team must be in agreement as to what changes took place. A direct consequence of the assumption that shared information is a necessary condition for coordination is that cooperation requires that the group of vehicles reach consensus on the coordination data. In other words, the instantiation of the coordination data on each vehicle must asymptotically approach a sufficiently common value. Convergence to a common value is called information consensus or agreement in the literature [4]. Although information consensus has a history in computer science (e.g. [5]), we will focus on its applications in cooperative control of multi-vehicle systems in this paper. 2 As a distributed solution to multi-vehicle coordination, information consensus has received significant attention in the literature. The main purpose of this paper is to provide a tutorial overview of information consensus in multi-vehicle cooperative control with the goal of promoting research in this area. Theoretical results regarding consensus seeking under both time-invariant and dynamically changing information exchange topologies are summarized. Applications of consensus algorithms to multi-vehicle coordination are investigated. Future research directions and open problems are also proposed. A preliminary version of the current paper was presented at the 2005 American Control Conference [6]. BACKGROUND AND PROBLEM STATEMENT Graph Theory It is natural to model information exchange between vehicles in a cooperative team by directed/undirected graphs (e.g. [7]). A digraph (directed graph) consists of a pair (N; E), where N is a finite nonempty set of nodes and E 2 N2 is a set of ordered pairs of nodes, called edges. As a comparison, the pairs of nodes in an undirected graph are unordered. A directed path is a sequence of ordered edges of the form (vi1 ; vi2); (vi2 ; vi3); , where vij 2 N, in a digraph. An undirected path in an undirected graph is defined analogously, where (vij ; vik) implies (vik ; vij ). A digraph is called strongly connected if there is a directed path from every node to every other node. An undirected graph is called connected if there is a path between any distinct pair of nodes. A directed tree is a digraph, where every node, except the root, has exactly one parent. A spanning tree of a digraph is a directed tree formed by graph edges that connect all the nodes of the graph. We say that a graph has (or contains) a spanning tree if there exists a spanning tree that is a subset of the graph. Note that the condition that a digraph contains a spanning tree is equivalent to the case that there exists a node having a directed path to all the other nodes. Fig. 1 shows a digraph that contains more than one possible spanning trees, but is not strongly 3 connected. @GAFABE1CD + @GAFABE2CD k /G@FAAEB3DC @GAFABE4CD /@GAFABE5CD /G@FAAEB6DC Figure 1. A digraph that contains more than one possible spanning trees, but is not strongly connected. The adjacency matrix A = [aij ] of a weighted digraph is defined as aii = 0 and aij > 0 if (j; i) 2 E where i 6= j. The Laplacian matrix of the weighted digraph is defined as L = [ ij ], where ii = P j aij and ij = aij where i 6= j. For an undirected graph, the Laplacian matrix is symmetric positive semi-definite. As an example of a Laplacian matrix for a weighted digraph, the matrix L = 2 666666666666664 1:5 1:5 0 0 0 0 0:7 0:7 0 0 0 0 0 1:1 1:1 0 0 0 0:8 0 0 0:8 0 0 0 0:2 0 0:3 0:5 0 0 0 0 0 1:2 1:2 3 777777777777775 is a valid Laplacian matrix corresponding to the digraph in Fig. 1. Matrix Theory Below we summarize some notation from nonnegative matrix theory (c.f. [8], [9]) which are important for studying information consensus. LetMn(IR) represent the set of all n n real matrices. Given a matrix A = [aij ] 2 Mn(IR), the digraph of A, denoted by (A), is the digraph on n vertices vi, i 2 I, such that there is a 4 directed edge in (A) from vj to vi if and only if aij 6= 0 (c.f. [9]). A matrix is nonnegative (positive) if all its entries are nonnegative (positive). A vector is nonnegative (positive) if all its elements are nonnegative (positive). Furthermore, if all its row sums are +1, the matrix is said to be a (row) stochastic matrix [9]. A stochastic matrix P is called indecomposable and aperiodic (SIA) if limk!1 Pk = 1 T , where 1 is a column vector of all ones and is a column vector [10]. The well-known Perron-Frobenius Theorem states that if a nonnegative matrix A is irreducible, that is, the digraph of matrix A is strongly connected, then (A) is a simple eigenvalue associated with a positive eigenvector, where ( ) denotes the spectral radius of a matrix. If a nonnegative matrix A is primitive, that is, A is irreducible and (A) is a simple eigenvalue of maximum modulus, then limk!1[ (A) 1Ak] ! w T , where w and are left and right positive eigenvectors of matrix A respectively satisfying wT = 1 [9]. The classical result in Markov chains states that if a stochastic matrix A satisfying Am > 0 for some positive integer m, then limk!1 Ak ! 1 T , where is a positive column vector satisfying that 1T = 1 [11]. In fact, the condition Am > 0 for some positive integer m is equivalent to the condition that A is irreducible and (A) is a simple eigenvalue of maximum modulus. Consensus Algorithms Let xi be the information state of the ith vehicle. The information state represents information that needs to be coordinated between vehicles. The information state may be vehicle position, velocity, oscillation phase, decision variable, and so on. 5 As described in [2], [12], [4], [13], [14], a continuous-time consensus algorithm can be summarized as x_ i(t) = X j2Ji(t) ij(t)(xi(t) xj(t)); i = 1; ; n (1) where Ji(t) represents the set of vehicles whose information is available to vehicle i at time t and ij(t) denotes a positive time-varying weighting factor. In other words, the information state of each vehicle is driven toward the states of its (possibly time-varying) neighbors at each time. Note that some vehicles may not have any information exchange with other vehicles during some time intervals. Continuous-time consensus algorithm (1) can be written in matrix form as x_ (t) = L(t)x(t), where L(t) is the digraph Laplacian at time t and x = [x1; ; xn]T . Correspondingly, a discrete-time consensus algorithm as proposed in [12], [15], [16] can be summarized as xi[k + 1] = X j2Ji[k] S fig ij [k]xj [k]; i = 1; ; n (2) where P j2Ji[k] S fig ij [k] = 1, and ij [k] > 0 for j 2 Ji[k] S fig. In other words, the next state of each vehicle is updated as the weighted average of its current state and the current states of its (possibly time-varying) neighbors. Note that a vehicle simply maintains its current state if it has no information exchange with other vehicles at a certain time step. Discrete-time consensus algorithm (2) can be written in matrix form as x[k + 1] = D[k]x[k], where D[k] is a stochastic matrix with positive diagonal entries. Consensus is said to be achieved for a team of vehicles if kxi xjk ! 0 as t ! 1, 8i 6= j for any xi(0). THEORETICAL ASPECTS OF CONSENSUS ALGORITHMS In this section, we review recent theoretical progress of information consensus in multivehicle systems. 6 Convergence Analysis for A Static Information Exchange Topology Under a time-invariant information exchange topology, it is assumed that if one vehicle can access another vehicle s information at one time, it can obtain information from that vehicle at all times. Given the consensus algorithms described by Eqs. (1)-(2), we first consider the question: Under what conditions do the consensus algorithms converge in the case that the information exchange topology between vehicles is time-invariant? For continuous-time consensus algorithm (1), it is straightforward to see that L1 = 0 and all eigenvalues of the Laplacian matrix L have non-negative real parts from Gershgorin s disc theorem. If zero is a simple eigenvalue of L, it is known that x converges to the kernel of L, that is, spanf1g, which in turn implies that kxi xjk ! 0. Therefore, the previous question is equivalent to the question Under what conditions does the digraph Laplacian matrix have a simple zero eigenvalue? It is well-known that zero is a simple eigenvalue of L if the digraph of L is strongly connected [17]. However, this is only a sufficient condition rather than a necessary one. Consider the following three Laplacian matrices: L1 = 2 66664 1 1 0 0 1:5 1:5 0 0 0 3 77775 L2 = 2 66664 1 1 0 0 1:5 1:5 0 2 2 3 77775 L3 = 2 66664 1 1 0 0 1:5 1:5 2 0 2 3 77775 (3) and their corresponding digraphs as shown in Fig. 2. ?8>91=:<;o ?8>92=:<;o ?8>93=:<; (a) ?8>91=:<;o ?8>92=:<;j *?8>93=:<; (b) ?8>91=:<;o ?8>92=:<;o (?8>93=:<; (c) Figure 2. Digraphs corresponding to L1 (subplot (a)), L2 (subplot (b)), and L3 (subplot (c)). 7 Although L1, L2, and L3 all have one simple zero eigenvalue, the digraph of L1 and L2 are obviously not strongly connected. The common feature of the digraphs of L1, L2, and L3 is that they all contain a spanning tree. We have that zero is a simple eigenvalue of the Laplacian matrix if and only if its digraph contains a spanning tree. This conclusion is shown in [14] by an induction approach while the same result is proven independently in [18] by a constructive approach. Therefore, under a time-invariant information exchange topology, continuous-time algorithm (1) achieves consensus asymptotically if and only if the information exchange topology contains a spanning tree [14]. For discrete-time consensus algorithm (2), it can be shown that all eigenvalues of D that are not equal to one are within the open unit circle from Gershgorin s disc theorem. If one is a unique eigenvalue of maximum modulus for matrix D, it is known that limk!1 Dk ! 1 T . This implies that kxi xjk ! 0. The well-known Perron-Frobenius theorem states that one is a simple eigenvalue of a stochastic matrix if the digraph of the matrix is strongly connected. Similar to the continuoustime case, this is only a sufficient condition rather than a necessary condition. We again have that one is a unique eigenvalue of modulus one for a stochastic matrix with positive diagonal entries if and only if its digraph contains a spanning tree. [16] shows that for a nonnegative matrix with identical positive row sums, the row sum of the matrix, i.e. the spectral radius, is a simple eigenvalue if and only if the digraph of the matrix contains a spanning tree. In other words, a matrix may be reducible but retains its spectral radius as a simple eigenvalue. Furthermore, if the matrix contains a spanning tree and positive diagonal entries, it is shown that the spectral radius of the matrix is the unique eigenvalue of maximum modulus. As a result, under a time-invariant information exchange topology, discrete-time algorithm (2) achieves consensus asymptotically if and only if the information exchange topology contains a spanning tree [16]. 8 Equilibrium State Under a Time-invariant Topology Now that we know under what conditions the consensus algorithms converge, the next step is to find the equilibrium state to which the consensus algorithms converge. In the case that the information exchange topology contains a spanning tree, we know that limt!1 e Lt ! 1 T and limk!1 Dk ! 1 T , where and are column vectors with nonnegative components j and j satisfying P j = P j = 1. As a result, x(t) ! P jxj(0) and x[k] ! P jxj[0]. In fact, and are left eigenvectors of L and D corresponding to eigenvalues 0 and 1 respectively. That is, the final equilibrium state is a weighted average of each vehicle s initial condition. However, it is not clear whether each vehicle will contribute to the final equilibrium state. As an example, for continuous-time consensus algorithm (1), let Li, where i = 1; 2; 3, be given by Eq. (3). It can be verified that x(t) ! 1x3(0), x(t) ! 1(0:5714x2(0) + 0:4286x3(0)), and x(t) ! 1(0:4615x1(0) + 0:3077x2(0) + 0:2308x3(0)) for x_ = Lix, where i = 1; 2; 3, respectively. Note that not each vehicle s initial condition contributes to the final equilibrium state. Observing the digraphs of Li shown in Fig. 2, we can see that vehicle 3 is the only one having a directed path to all the other vehicles in the team in subplot (a), either vehicle 2 or 3 has a directed path to all the other vehicles in subplot (b), and each vehicle has a directed path to all the other vehicles in subplot (c). In the case that the information exchange topology is strongly connected, we know that each j and j are positive [9]. Therefore, each vehicle s initial condition contributes to the final consensus equilibrium in this case. Furthermore, if i = j and i = j , where i 6= j, the final consensus equilibrium will be the average of each vehicle s initial condition, which is called average consensus in [4]. As shown in [4], average consensus is achieved if the information exchange topology is both strongly connected and balanced. In Fig. 3, we show 9 how consensus is achieved for x_ = L3x (subplot (a)) and x_ = diagfwgL3x (subplot (b)), where w = [w1;w2;w3]T is the positive left eigenvector of L satisfying that wT1 = 1. As shown in subplot (a), each vehicle s initial condition contributes to the final equilibrium state since the digraph of L3 is strongly connected. However, the final equilibrium is not an average consensus since the digraph is not balanced. As a comparison, average consensus is achieved in subplot (b) with a modification to the consensus algorithm. This can be verified by noting that diagfwgL3 is strongly connected and balanced. 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0.2 0.3 0.4 0.5 0.6 0.7 time (sec) (a) x1 x2 x3 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0.2 0.3 0.4 0.5 0.6 0.7 time (sec) (b) x1 x2 x3 Figure 3. Consensus for (a) x_ = L3x and (b) x_ = diagfwgL3x. As a comparison, in the case that the information exchange topology contains a spanning tree, the final consensus value is equal to the weighted average of initial conditions of those vehicles that have a directed path to all the other vehicles [14]. While the requirement of having a spanning tree is less stringent than being strongly connected and balanced, the final consensus value may be in favor of some vehicles and may not be an average consensus. Convergence Analysis for Dynamic Information Exchange Topologies Although information consensus is significantly simplified by assuming a time-invariant information exchange topology, the information exchange topology between vehicles may change 10 dynamically in reality. For instance, communication links between vehicles may be unreliable due to disturbances and/or subject to communication range limitations. If information is being exchanged by direct sensing, the locally visible neighbors of a vehicle will likely change over time. Many research efforts on the coordination of multiple autonomous vehicles under switching information exchange topologies are motivated by Viscek s model [19]. Motivated by biological systems, Viscek et al. proposed a simple discrete-time model of a system of self-driven particles, where each particle moves with a constant absolute velocity but updates its heading to be the average of its own heading and headings of its (time-varying) set of neighbors. Viscek s model can be thought of as a special case of a distributed behavioral model proposed in [20], where computer animations are used to generate the aggregate motions of a group of animals. Fig. 4 shows a scenario where each vehicle can only communicate with or sense nearest neighbors that are within a communication or sensing range R of the current vehicle. Note that each vehicle s set of nearest neighbors may be time-varying as vehicle positions change. A natural question is Under what conditions do the consensus algorithms converge in the case of switching information exchange topologies? One approach to tackle switching topologies is the algebraic graph approach, which typically associates graph topologies with the algebraic structure of the corresponding matrices of those graphs. Notice that the solution of the discrete-time and continuous-time consensus algorithms can be written as x[k] = D[k]D[k 1] D[1]D[0]x[0] and x(t) = (t; 0)x(0) respectively, where (t; 0) is the transition matrix corresponding to L(t). Consensus can be reached if limk!1 D[k]D[k 1] D[1]D[0] ! 1 T and limt!1 (t; 0) ! 1 T , where and are column vectors. In the special case that L(t) is piecewise constant with dwell times j = tj+1 tj , consensus can be reached if limt!1 e L(tj )(t tj )e L(tj 1) j 1 e L(t0) 0 ! 1 T . Equivalently, we can study the property of infinite products of stochastic matrices. 11 R Figure 4. An illustrative example of time-varying nearest neighbors. The classical result in [10] demonstrates the property of the infinite products of certain categories. The main result of [10] can be summarized as follows. 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 limj!1 SijSij 1 Si1 = 1 T . From the concluding remarks in [10], we see that in the case that S is an infinite set, (W) < 1, where W = Sk1Sk2 SkNt+1, (W) = 1 mini1;i2 P j min(wi1j ;wi2j), 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 the above limit result of an infinite sequence also holds. In the case that the union of undirected information exchange graphs across a bounded time interval is connected, the product of D matrices across such an interval is SIA [12]. Using the above result for finite S in [10], [12] provides a theoretical explanation for consensus of the heading angles of a group of vehicles using nearest neighbor rules under undirected switching information exchange topologies. It is shown that consensus is achieved asymptotically if the union of the information exchange graphs for the team is connected most of the time as the 12 system evolves. This result is further discussed in [21] and [22]. Taking into account the fact that sensors may have a limited field of view, the authors in [13] use digraphs to derive consensus seeking results under switching information exchange topologies. It is shown that consensus using continuous-time consensus algorithm (1) can be achieved if in each uniformly bounded time interval there exists at least one piecewise constant switching topology that is strongly connected. [16] further extends the previous results to the case that consensus can be achieved asymptotically if the union of the directed information exchange graphs for the group contains a spanning tree sufficiently frequently as the system evolves. A common feature in the above analysis is that L(t) is assumed to be piecewise constant for the continuous-time consensus algorithm. However, it is possible that L(t) may be timevarying to reflect the relative confidence of each vehicle about its information state, that is, the weighting factors ij may be time-varying. In fact, in the case that L(t) is piecewise continuous and each nonzero entry ij , where i 6= j, is uniformly lower and upper bounded, consensus is reached asymptotically using the continuous-time consensus algorithm if there exist infinitely many consecutive uniformly bounded time intervals such that the union of the information exchange graph across each such interval contains a spanning tree [23]. In addition, [4] uses a common Lyapunov function to study average consensus under switching interaction topologies. [24] derives conditions for consensus under switching interaction topologies by studying products of row stochastic matrices in the lower-triangular structure. In contrast to the algebraic graph approach, nonlinear analysis tools are used by some other researchers to study consensus algorithms. For the discrete-time consensus algorithm, a set-valued function V is defined as V (x1; ; xn) = (convfx1; ; xng)n; where convfx1; ; xng denotes the convex hull of xi, i = 1; ; n [15]. It is shown that 13 under some conditions V is non-increasing over time and V indeed approaches a singleton set x1(t) = = xn(t) = constant, which implies that consensus is reached. Using set-valued Lyapunov theory, [15] shows that discrete-time consensus algorithm (2) is uniformly globally attractive with respect to the collection of equilibrium solutions x1(t) = = xn(t) = constant if and only if there exists a T 0 such that there is a node that has a directed path to all the other nodes across each interval of length T. Note that the condition that a node has a directed path to all the other nodes is equivalent to the existence of a spanning tree. For continuous-time consensus algorithm (1), a Lyapunov function candidate is proposed as V (x) = maxfx1; ; xng minfx1; ; xng in [25]. It is shown that V (x) decreases over a sufficient length of time intervals. In the case that L(t) is piecewise continuous and each nonzero entry ij , where i 6= j, is uniformly lower and upper bounded, the equilibrium set x1 = = xn = constant is uniformly exponentially stable if there is an index k 2 f1; ; ng and an interval length T > 0 such that for all t the digraph of R t+T t ( L(s))ds has the property that node k has a directed path to all the other nodes. Note again that the property that node k has a directed path to all the other nodes is equivalent to the existence of a spanning tree with node k being the root. In addition, in [26], nonlinear contraction theory is used to study synchronization and schooling applications, which are related to information consensus. In particular, the continuoustime consensus algorithm is analyzed under undirected switching information exchange topologies. It is shown that consensus is reached asymptotically if there exists an infinite sequence of bounded intervals such that the union of the graphs across each interval is connected, which is identical to the result shown in [12]. 14 Communication Delays and Noise In the case that information is exchanged between vehicles through communications, time delays of the communication channels need to be considered. Let ij denote the time delay for information communicated from vehicle j to vehicle i. The continuous-time consensus algorithm is now denoted by x_ i = X i2Ji(t) ij [xj(t ij) xi(t ij)]: In the simplest case where ij = and the communication topology is fixed, undirected, and connected, average consensus is achieved if and only if 2 [0; 2 max(L) ), where L is the digraph Laplacian matrix [4]. Consider another case where the time delay only affects the information state that is being transmitted. The continuous-time consensus algorithm is denoted as x_ i = X i2Ji(t) ij [xj(t ij) xi(t)]: In the case where ij = and the communication topology is directed and switching, the consensus result for switching topologies described previously is still valid for an arbitrary time delay [25]. More generally, [27] studies discrete-time information consensus in an asynchronous framework, where time delays are allowed to be time-varying and link-dependent. In addition to time delays, information exchange between vehicles is often affected by random noise. Therefore, it is critical to decide the robustness of the consensus algorithms to information exchange noise. In fact, the continuous-time and discrete-time consensus algorithms converge to the consensus values uniformly exponentially, which in turn implies that the continuous-time and 15 discrete-time consensus algorithms are input-to-state stable to information exchange noise [28]. Consensus Synthesis In the above discussions, we analyze the properties of consensus algorithms. Occasionally, one may want to generate consensus algorithms that satisfy certain properties or optimize some performance criteria. For example, in a network with a large number of vehicles, it may be desirable to solve the fastest distributed linear averaging (FDLA) problem defined as follows [29]: Let W = [Wij ] 2 Mn(IR) such that Wij = 0 if there is no information exchange between vehicle i and vehicle j. Given x[k + 1] = Wx[k], find W to minimize rasym(W) subject to the condition that limt!1Wk = 1 n11T , where rasym(W) = supx[0]6= x limt!1 kx[k] xk x[0] x 1=k with x = 1 n11T x[0]. In other words, the FDLA problem is to find the weight matrix W that guarantees the fastest convergence speed to the average consensus value. In contrast to discretetime consensus algorithm (2), the weighting factors Wij above are allowed to be negative. In fact, as shown in [29], the optimal weighting factors may sometimes be negative. With an additional constraint that Wij = Wji, the FDLA problem can be simplified as a semi-definite program and solved accordingly [29]. In addition, [30] focuses on designing consensus algorithms for a team of vehicles with single-integrator dynamics given by x_ i = ui and arbitrary linear observations given by yi = Gix, where x = [x1; ; xn]T and Gi 2 IRmi n. The control input of vehicle i is designed in the form of ui = kiyi + zi, where ki is a row vector with mi elements and zi is a scalar. More generally, consider an interconnected network of n vehicles with dynamics given by x_ i = Xn j=1 Aijxj + B(1) i wi + B(2) i ui; i = 1; ; n 16 where xi 2 IRn denotes the state, wi 2 IRm denotes the disturbance, and ui 2 IRr denotes the control input with i = 1; ; n. Letting x, w, and u be column stacks with elements xi, wi, and ui respectively, the dynamics of x can be denoted as x_ = Ax + B1w + B2u; where A, B1, B2 can be obtained correspondingly. [31] focuses on synthesizing a state feedback controller that guarantees consensus for the closed loop system without disturbance as well as synthesizing a state feedback controller that achieves not only consensus but optimal H2 performance for disturbance attenuation. Necessary and sufficient convex conditions are derived for the existence of such state feedback controllers. Other Issues Under certain circumstances, it is desirable to construct nonlinear consensus algorithms as shown in [4], [32], [26]. Information agreement is also studied from a stochastic point of view in [33], which relies on graph theoretic results developed in [34]. In addition, second order consensus algorithms are studied in [35] in the context of unidirectional information exchange. Consensus algorithms accounting for relative confidence/reliability of each vehicle are introduced in [23]. Connectedness issue is studied in [36], where appropriate weights are added to graph edges such that the interaction graph is guaranteed to stay connected. Furthermore, dynamic consensus algorithms are studied in [37], which focuses on how to achieve and analyze tracking of linear consensus on time-varying inputs. Other work related to consensus algorithms includes the stability analysis of swarms in [38], [39], to name a few. DESIGN OF COORDINATION STRATEGIES VIA CONSENSUS SCHEMES In this section, we investigate how consensus schemes can be applied to design multivehicle coordination strategies. 17 Vehicle Formations Consensus schemes have been extensively applied to achieve vehicle formations. For formation stabilization, if each vehicle in a group can reach consensus on the center point of the desired formation and specify a corresponding desired deviation from the center point, then vehicle formations can be achieved. In Fig. 5, we show a scenario where six vehicles need to preserve a hexagon formation. Here the formation center is x0 and each vehicle s deviation from the formation center is denoted by r0j . As long as consensus on the formation center can be reached and each vehicle knows its desired deviation from that center, formation shape can be preserved. x0 r0j xj Figure 5. Formation stabilization through consensus on the formation center. As a simple application of Fig. 5, consensus algorithms can be applied to guarantee that kx0i x0jk ! 0, where x0i is the ith vehicle s understanding of the formation center, while single vehicle stabilization strategies can be employed to guarantee that kxj (x0j + r0j)k ! 0. In [2], information exchange techniques are studied to improve stability margins and formation performance for vehicle formations, where an information flow filter provides each 18 vehicle with the formation center so that this information can be used by each vehicle as a reference. [18] studies the formation stabilization problem of multiple unicycles using a consensus scheme, where results are given for formation stabilization of the unicycles to a point, a line, and a general formation pattern. In addition, the simplified pursuit strategy for wheeled-vehicle formations in [40] can be considered as a special case of continuous-time consensus algorithm (1), where the information exchange topology is a uni-directional ring. Furthermore, [41] designs feedback control laws using relative information between neighboring vehicles to stabilize vehicle formations. Rendezvous Problem The rendezvous problem requires that all vehicles arrive at a location simultaneously. Fig. 6 shows a simple coordination framework for multi-vehicle rendezvous. In Fig. 6 a consensus manager applies distributed consensus schemes to guarantee that each vehicle reaches consensus on a rendezvous objective such as rendezvous time or a rendezvous location. Based on the output of the consensus manager, each vehicle uses local control laws to drive itself to actually achieve the rendezvous objective. Consensus Manager Local Control Local Control Figure 6. A simple coordination framework for multi-vehicle rendezvous. As a simple application of Fig. 6, multiple UAVs are controlled to converge on the 19 boundary of a radar detection area simultaneously to maximize the element of surprise in [28], where consensus is reached on time-over-target for the whole team while each vehicle adjusts its velocity to guarantee that it arrives at the target according to the common time-over-target. Assume that each UAV has autopilot functionality that maintains the UAV on its predefined path, but that the velocity along the path can be adjusted to meet the simultaneous arrival objective [42]. Also assume that the velocity hold autopilot has been designed such that v_i = i (vc i vi) where i > 0, vi is the velocity, and vc i is the commanded velocity for the ith UAV. Let i represent the ith UAVs understanding of the team arrival time and Li denote the length of the path remaining to the target. In [28], a continuous-time consensus algorithm using only local interactions is applied to guarantee that j i j j ! 0 in the presence of unreliable communication channels and random data losses while the commanded velocity vc i is designed as vc i = vi + vi iLi ( Li ivi vi) ; where > 0. With a combination of the consensus algorithm and the local control law, each UAV is guaranteed to converge to a common time-over-target, that is, jLi vi Lj vj j ! 0. In addition, consensus seeking ideas are applied to a rendezvous problem for a group of mobile autonomous vehicles in [43], where both the synchronous case and the asynchronous case are considered. Behavioral Approach to Formation Maneuvers and Flocking Multi-vehicle formation maneuvers can be performed by means of a behavioral approach, where different behaviors like goal seeking, formation keeping, and collision avoidance can be 20 specified [44]. In Fig. 7, we show a scheme where formation maneuvers and flocking are achieved by a combination of different behaviors. + + Formation Maneuver / Flocking + Formation Keeping Obstacle Avoidance Goal Seeking Figure 7. Behavioral approach to formation maneuvering and flocking. Consensus schemes can be applied to preserve formation keeping among vehicles. For example, in [45], a mobile robot dynamic model is feedback linearized as a double integrator system given by h i = i; where hi denotes the hand position off the wheel axis of the ith mobile robot. Assuming a bi-directional ring communication topology between robots, the control law i is designed as i = Kg hi Dg_hi Kf ( hi hi 1) Df (_hi _hi 1) Kf ( hi hi+1) Df (_hi _hi+1); where Kg and Kf are symmetric positive definite matrices, Dg and Df are symmetric positive semi-definite matrices, and hi = hi hd i with hd i denoting the desired location of the hand position of the ith robot. In the above control law, the first two terms are used to guarantee that hi approaches hd i , the second two terms guarantee that hi and hi 1 as well as _hi and _hi 1 reach consensus respectively, and the last two terms guarantee that hi and hi+1 as well as _hi and _hi+1 21 reach consensus respectively. If consensus can be reached for each hj , desired formation shape is guaranteed to be preserved. Similarly, consider rigid body attitude dynamics given by _ ^q i = 1 2 !i ^qi + 1 2 qi!i _ qi = 1 2 !i ^qi Ji!_ i = !i (Ji!i) + i; where qi = [^qT i ; qi]T is the unit quaternion of the ith rigid body, !i is the angular velocity, and Ji and i are inertia tensor and control torque. The control torque i can then be designed as [46], [47] i = kG dqd i qi DG!i kS\q i+1qi DS(!i !i+1) kS\q i 1qi DS(!i !i 1); where kG > 0 and kS 0 are scalars, DG is a symmetric positive definite matrix, DS is a symmetric positive semi-definite matrix, and ^q represents the vector part of the quaternion. With the above control law, a group of rigid bodies can reach their desired attitude, and attitude alignment among a group of rigid bodies is maintained relative to two adjacent neighbors via a bi-directional ring communication topology. Flocking of multiple animals is a well observed phenomenon in biology. This phenomenon has motivated the study of flocking of multi-vehicle systems. Consider vehicle dynamics given by r_i = vi; v_i = ui; where ri and vi are the position and velocity of vehicle i respectively, and ui denotes its input. In [48], [49], the control input ui is designed as ui = X j2Ji(t) (vi vj) X j2Ji(t) @Vij @ri 22 where Vij is a potential function satisfying the following conditions (i) Vij(kri rjk) ! 1 as kri rjk ! 0, and (ii) Vij attains its unique minimum if kri rjk is equal to a desired value. Note that the first term in the above control law guarantees that each vehicle s velocity reaches consensus and the second term guarantees collision avoidance between neighboring vehicles and the team approaches a configuration that locally minimizes the potential Vi = P j2Ji(t) Vij(kri rjk) for each vehicle i. Lyapunov techniques are applied in [48], [49] to show that the above control law allows a group of mobile vehicles to align their velocities, move with a common speed, and achieve desired inter-vehicle distances while avoiding collisions with each other under an undirected fixed topology and undirected switching topologies respectively. These results extend some results reported in [50]. In [51], the control input ui is defined as ui = @V (r) @ri + X j2Ji(t) aij(r)(vj vi) + f i ; where the first term is applied to guarantee collision avoidance, the second term is applied to guarantee that each vehicle reaches consensus on velocity, and the third term is applied to achieve group objective. It is shown that flocking can be achieved using the above control law. Consensus in Cascade with Cooperation Schemes Suppose that the communication links are corrupted by noise. Then continuous-time consensus algorithm (1) becomes x_ i(t) = X j2Ji(t) ij(t)(xi(t) (xj(t) + ij)); (4) where ij is the noise on the communication channel from vehicle j to vehicle i. Letting ij = xi xj and = [ 11; 12; : : : ; 1n; 21; : : : ; nn]T , we get the state-space model _ = A(t) + B(t) (5) 23 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 ij(t) and can be easily constructed from Eq. (4). The vector represents the total consensus error. It has been shown in [28] that Eq. (5) is input-to-state stable from the communication noise to the consensus error. This result suggests that the control architecture shown in Figure 8 is appropriate for cooperative control strategies based on consensus. If the cooperation algorithm is input-to-state stable from the consensus Figure 8. 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 xi. The coordination algorithm uses the coordination variable to produce a command to the vehicle ui. error to the cooperation objective, than the cascade system will be input-output stable from the communication noise to the cooperation objective. This idea has been used in [28] to design a decentralized cooperative timing algorithm, and in [52] to design a decentralized cooperative perimeter tracking algorithm. 24 CONCLUSIONS AND FUTURE DIRECTIONS We have reviewed consensus algorithms in the current literature. Since much research on information consensus is ongoing, this overview is by no means complete. In the current literature, most consensus algorithms are studied in the context of single integrator dynamics. Some results from single integrator dynamics imply that the same results may be extended to double integrator dynamics or more complicated dynamics. As a result, the same framework of consensus-seeking for single integrator dynamics may be applied to decentralized robot, spacecraft, and UAV formation flying scenarios, where the communication topologies between robot/spacecraft/UAV could be switching with time. The study of information consensus for a team of vehicles with more complicated nonlinear dynamics and a team of heterogenous vehicles is an interesting topic for future research. Most research in information consensus assumes that the final consensus value to be reached is inherently constant, which may not be the case in the sense that the information state of each vehicle may be dynamically evolving in time according to some inherent dynamics, as happens in some formation control problems where the formation is moving through space. It will be interesting to study information consensus where the final consensus value evolves with time or as a function of vehicle/environmental dynamics. The input-to-state properties of consensus algorithms allow a cascade architecture between consensus and cooperative control algorithms. There are also many applications where the cooperation objective may be fed back directly to the consensus algorithm. Convergence results for the feedback case also need to be explored. Most of the research activities have focused on the theoretical study of consensus algorithms and most of the results are demonstrated via simulations. Experimental implementation of consensus schemes for multiple vehicle systems is a key element of research in the future. 25 Furthermore, issues like disturbance rejection, time-delay, communication/sensor noise, and model uncertainties should also be taken into account. REFERENCES [1] J. R. Carpenter, Decentralized control of satellite formations, International J. of Robust and Nonlinear Control, vol. 12, pp. 141 161, 2002. [2] J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations, IEEE Trans. on Automatic Control, vol. 49, pp. 1465 1476, September 2004. [3] T. Balch and L. E. Parker, eds., Robot Teams: From Diversity to Polymorphism. Natick, Massachusetts: A. K. Peters, Ltd., 2002. [4] R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays, IEEE Trans. on Automatic Control, vol. 49, pp. 1520 1533, September 2004. [5] N. A. Lynch, Distributed Algorithms. San Francisco, California: Morgan Kaufmann Publishers, Inc., 1996. [6] W. Ren, R. W. Beard, and E. M. Atkins, A survey of consensus problems in multi-agent coordination, in Proc. of ACC, (Portland, OR), pp. 1859 1864, June 2005. [7] G. Royle and C. Godsil, Algebraic Graph Theory. New York: Springer Graduate Texts in Mathematics #207, 2001. [8] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences. New York: Academic Press, INC., 1979. [9] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 1985. [10] J. Wolfowitz, Products of indecomposable, aperiodic, stochastic matrices, Proceedings of the American Mathematical Society, vol. 15, pp. 733 736, 1963. [11] E. Seneta, Non-negative Matrices and Markov Chains. New York: Springer-Verlag, 1981. 26 [12] A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. on Automatic Control, vol. 48, pp. 988 1001, June 2003. [13] Z. Lin, M. Broucke, and B. Francis, Local control strategies for groups of mobile autonomous agents, IEEE Trans. on Automatic Control, vol. 49, no. 4, pp. 622 629, 2004. [14] W. Ren, R. W. Beard, and T. W. McLain, Coordination variables and consensus building in multiple vehicle systems, in Cooperative Control (V. Kumar, N. E. Leonard, and A. S. Morse, eds.), vol. 309, pp. 171 188, Springer-Verlag Series: Lecture Notes in Control and Information Sciences, 2004. [15] L. Moreau, Stability of multi-agent systems with time-dependent communication links, IEEE Trans. on Automatic Control, vol. 50, pp. 169 182, February 2005. [16] W. Ren and R. W. Beard, Consensus seeking in multiagent systems under dynamically changing interaction topologies, IEEE Trans. on Automatic Control, vol. 50, pp. 655 661, May 2005. [17] F. R. K. Chung, Spectral graph theory, in Regional Conference Series in Mathematics, American Mathematical Society, 1997. [18] Z. Lin, B. Francis, and M. Maggiore, Necessary and sufficient graphical conditions for formation control of unicycles, IEEE Trans. on Automatic Control, vol. 50, no. 1, pp. 121 127, 2005. [19] T. Vicsek, A. Czirok, E. Ben-Jacob, I. Cohen, and O. Schochet, Novel type of phase transitions in a system of self-driven particles, Physical Review Letters, vol. 75, pp. 1226 1229, 1995. [20] C. W. Reynolds, Flocks, herds, and schools: A distributed behavioral model, Computer Graphics, vol. 21, pp. 25 34, 1987. [21] A. Jadbabaie, On coordination strategies for mobile agents with changing nearest neighbor sets, in IEEE Mediterranian Conference on Control and Automation, (Rhodes, Greece), 27 June 2003. [22] A. V. Savkin, Coordinated collective motion of groups of autonomous mobile robots: Analysisof vicsek s model, IEEE Trans. on Automatic Control, vol. 49, pp. 981 983, June 2004. [23] W. Ren, R. W. Beard, and D. B. Kingston, Multi-agent Kalman consensus with relative uncertainty, in Proc. of ACC, (Portland, OR), pp. 1865 1870, June 2005. [24] Z. Qu, J. Wang, and R. A. Hull, Products of row stochastic matrices and their applications to cooperative control for autonomous mobile robots, in Proc. of ACC, (Portland, OR), pp. 1066 1071, June 2005. [25] L. Moreau, Stability of continuous-time distributed consensus algorithms, in Proc. of CDC, 2004. [26] J.-J. E. Slotine and W. Wang, A study of synchronization and group cooperation using partial contraction theory, in 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. [27] L. Fang and P. J. Antsaklis, Information consensus of asynchronous discrete-time multiagent systems, in Proc. of ACC, (Portland, OR), pp. 1883 1888, June 2005. [28] D. B. Kingston, W. Ren, and R. W. Beard, Consensus algorithms are input-to-state stable, in Proc. of ACC, (Portland, OR), pp. 1686 1690, June 2005. [29] L. Xiao and S. Boyd, Fast linear iterations for distributed averaging, Systems and Control Letters, vol. 53, pp. 65 78, 2004. [30] S. Roy, A. Saberi, and K. Herlugson, A control-theoretic perspective on the design of distributed agreement protocols, in Proc. of ACC, (Portland, OR), pp. 1672 1679, June 2005. [31] G. A. de Castro and F. Paganini, Convex synthesis of controllers for consensus, in Proc. of ACC, (Boston, MA), pp. 4933 4938, 2004. 28 [32] L. G. Dario Bauso and R. Pesenti, Distributed consensus protocols for coordinating buyers, in Proc. of CDC, (Maui, Hawaii), pp. 588 592, December 2003. [33] Y. Hatano and M. Mesbahi, Agreement over random networks, in Proc. of CDC, 2004. [34] M. Mesbahi, State-dependent graphs, in Proc. of CDC, (Maui, Hawaii), pp. 3058 3063, December 2003. [35] W. Ren and E. Atkins, Second-order consensus protocols in multiple vehicle systems with local interactions, in Proc. of AIAA GNC, (San Francisco, CA), August 2005. Paper No. AIAA-2005-6238. [36] M. Ji and M. Egerstedt, Connectedness preserving distributed coordination control over dynamic graphs, in Proc. of ACC, (Portland, OR), pp. 93 98, June 2005. [37] D. P. Spanos, R. Olfati-Saber, and R. M. Murray, Dynamic consensus on mobile networks, in IFAC World Congress, (Prague, Czech Republic), 2005. [38] V. Gazi and K. M. Passino, Stability analysis of swarms, IEEE Trans. on Automatic Control, vol. 48, pp. 692 696, April 2003. [39] Y. Liu, K. M. Passino, and M. M. Polycarpou, Stability analysis of m-dimentional asynchronous swarms with a fixed communication topology, IEEE Trans. on Automatic Control, vol. 48, pp. 76 95, January 2003. [40] J. A. Marshall, M. E. Broucke, and B. A. Francis, Formations of vehicles in cyclic pursuit, IEEE Trans. on Automatic Control, vol. 49, pp. 1963 1974, November 2004. [41] J. S. Caughman, G. Lafferriere, J. J. P. Veerman, and A. Williams, Decentralized control of vehicle formations, Systems and Control Letters. (to appear). [42] 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. [43] J. Lin, A. S. Morse, and B. D. O. Anderson, The multi-agent rendezvous problem, in 29 Proc. of CDC, (Maui, Hawaii), pp. 1508 1513, December 2003. [44] T. Balch and R. C. Arkin, Behavior-based formation control for multirobot teams, IEEE Transactions on Robotics and Automation, vol. 14, pp. 926 939, December 1998. [45] J. R. Lawton, R. W. Beard, and B. Young, A decentralized approach to formation maneuvers, IEEE Transactions on Robotics and Automation, vol. 19, pp. 933 941, December 2003. [46] J. R. Lawton and R. W. Beard, Synchronized multiple spacecraft rotations, Automatica, vol. 38, no. 8, pp. 1359 1364, 2002. [47] W. Ren and R. W. Beard, Decentralized scheme for spacecraft formation flying via the virtual structure approach, AIAA J. of Guidance, Control, and Dynamics, vol. 27, pp. 73 82, January-February 2004. [48] H. G. Tanner, A. Jadbabaie, and G. J. Pappas, Stable flocking of mobile agents, part i: Fixed topology, in Proc. of CDC, (Maui, Hawaii), pp. 2010 2015, December 2003. [49] H. G. Tanner, A. Jadbabaie, and G. J. Pappas, Stable flocking of mobile agents, part ii: Dynamic topology, in Proc. of CDC, (Maui, Hawaii), pp. 2016 2021, December 2003. [50] N. E. Leonard and E. Fiorelli, Virtual leaders, artificial potentials and coordinated control of groups, in Proc. of CDC, (Orlando, Florida), pp. 2968 2973, December 2001. [51] R. Olfati-Saber, Flocking for multi-agent dynamic systems: Algorithms and theory, IEEE Trans. on Automatic Control, 2004. (in review). [52] D. W. Casbeer, R. W. Beard, T. W. McLain, S.-M. Li, and R. Mehra, Forest fire monitoring using multiple small unmanned air vehicles, in Proc. of ACC, (Portland, OR), June 2005. 30