多智能体分布式控制讲义

所需积分/C币:46 2019-01-19 21:15:44 1011KB PDF

DISC课程:多智能体的分布式控制,包括图论、矩阵轮、系统论介绍,多智能体一致性算法的介绍和推导等
Lecture 1 In this lecture, we first introduce some background and preliminaries related to dis tributed control of multi-agent systems including graph theory, matrix theory, linear sys tems theory, and nonlinear systems theory We then overview recent research on distributed control of multi-agent systems. We finally introduce some fundamental results in distributed consensus for agents with single-integrator dynamics 1 Background and Preliminaries The materials in this subsection are adopted from the appendices in 27 1.1 Algebraic Graph Theory It is natural to model information exchange among agents by directed or undirected graphs Suppose that a tean consists of p agents. a directed graph is a pair(Vp, Ep), where Vp f1,.,p is a finite nonempty node set and Epc vp x vp is an edge set of ordered pairs of nodes, called edges. The edge(i,,) in the edge set of a directed graph denotes that agent can obtain information from agent i, but not necessarily vice versa. Self-edges(i, i)are not allowed unless otherwise indicated. For the edge(i,n), i is the parent node and j is the child node. In contrast to a directed graph, the pairs of nodes in an undirected graph are unordered, where the edge(i,,) denotes that agents i and. can obtain information from each other. Note that an undirected graph can be viewed as a special case of a directed graph, where an edge (i j) in the undirected graph corresponds to edges(i, j) and (, i)in the directed graph. If an edge(i,DEEp, then node i is a neighbor of node j. The set of neighbors of node i is denoted as Mi. a weighted graph associates a weight with every edge in the graph. In this book, all graphs are weighted. The union of a collection of graphs is a graph whose node and edge sets are the unions of the node and edge sets of the graphs in the collection a directed path is a sequence of edges in a directed graph of the form(i1, i2), (i2, i3) An undirected path in an undirected graph is defined analogously. In a directed graph, a cycle is a directed path that starts and ends at the same node. a directed graph is strongly connected if there is a directed path from every node to every other node. An undirected graph is connected if there is an undirected path between every pair of distinct nodes. A directed tree is a directed graph in which every node has exactly one parent except for one node, called the root, which has no parent and which has a directed path to every other node. Note that a directed tree has no cvcle because every edge is oriented away from the root. In undirected graphs, a tree is a graph in which every pair of nodes is connected by exactly one undirected path A subgraph (vs, &s)of (Vp, &p)is a graph such that Vs c vp and epc xvs). A rooted) directed spanning tree(vs, Es)of the directed graph(Vp, &p) is a subgraph of such that(v,, &s)is a directed tree and vis=vp. An undirected spam ning tree of an undirected graph is defined analogously. The graph(Vp, Ep) has or contains a directed spanning tree if a directed spanning tree is a subgraph of (vp, ip). Note that the directed graph(Vp, Ep) has a directed spanning tree if and only if(vp, Ep) has at least one node with a directed path to all other nodes. In undirected graphs, the existence of an undirected spanning tree is equivalent to being connected. However, in directed graphs, the existence of a directed spanning tree is a weaker condition than being strongly connected. Figure 1 shows a directed graph that contains more than one directed spanning tree but is not strongly connected Nodes 1 and 2 are both roots of directed spanning trees because both have directed paths to all other nodes. However, the graph is not strongly connected because nodes 3, 4, 5, and 6 do not have directed paths to all other nodes Figure 1: Directed graph among six agents. An arrow from node i to node i indicates that agent i receives information from agent i. This directed graph contains two directed spanning trees with root nodes 1 and 2 but is not strongly connected because nodes 3, 4, 5 and 6 do not have directed paths to all other nodes The adjacency matrix Ap=[] E RPxp of a directed graph(Vp, Ep) is defined such that aii is a positive weight if ( i)E Ep, and aii=0 if ( i) Ep. Self-edges are not allowed (i.e, aii=0)unless otherwise indicated. The adjacency matrix of an undirected graph is defined analogously except that a for all i≠ Decause (,)∈8 implies(,j) Note that aii denotes the weight for the edge (j, i)E Ep. If the weight is not relevant, then a; is set equal to1i(,)∈£, a graph is balanced if∑-1a P -1 ii, for all 2.上Or an undirected graph, Ap is symmetrical, and thus every undirected graph is balanced Define the matrix lp=2i E RPxp ∑ 产j j=1,j Note that if (, i) Ep then lij==aij=0. Matrix Lp satisfies ≤0,≠,∑ For an undirected graph, Lp is symmetrical and is called the Laplacian, matri r :. However, for a directed graph, Lp is not necessarily symmetrical and is sometimes called the nonsymmetrical Laplacian matri. c 2 or directed Laplacian matris [15 Remark 1.1 Note that Lp in(1) can be equivalently defined as Lp=d-Ap, where D 可∈ RPxP is the in- egree matri m given as di=0.≠, and dia=∑ Also note that for directed graphs, the definition of the nonsymmetrical Laplacian matric given by(1)is different from the common definition of a Laplacian matric for a directcd graph in the graph theory literature(e. g, 92). However, we adopt the definition given by(1)for directed graphs due to its relevance to consensus algorithms In both the undirected and directed cases, because Ln has zero row sums, 0 is an eigen value of Lp with the associated eigenvector lp, the p x 1 column vector of ones. Note that L is diagonally dominant and has nonnegative diagonal entries. It follows from Theorem 1.2 that, for an undirected graph, all nonzero eigenvalues of Lp are positive(Cp is positive semidefinite), whereas, for a directed graph, all nonzero eigenvalues of Lp have positive real parts. Therefore, all nonzero eigenvalues of -Cp have negative real parts. For an undirected graph, 0 is a simple eigenvalue of Lp if and only if the undirected graph is connected [16, p 147. For a directed graph, 0 is a simple eigenvalue of Lp if the directed graph is strongly con nected[7, Proposition 3, although the converse does not hold. For an undirected graph, let 2(Cp) be the ith eigenvalue of lo with x1(C)≤A2(Cp)≤…≤入2(Cp), so that x1(Cp)=0. For an undirected graph, A2(Cp) is the algebraic connectivity, which is positive if and onl if the undirected graph is connected [ 16, p. 147. The algebraic connectivity quantifies the convergence rate of consensus algorithms [I Given a matrix S=[SiJE rPxP, the directed graph of S, denoted by r(S), is the directed aph with node set Vp=(1,.,p such that there is an edge in r(S)from j to i if and if Siif019, p. 357. In other words, the entries of the adjacency matrix satisfy ai;>0 ifs;≠0anda1=0ifsi=0 1.2 Matrix Theory We need the following definitions, lemmas, and theorems from matrix theory Theorem 1.2 9, Theorem 6.1.1 (Gershgorin's disc theorem), p. 344 Let A=aiiE Rnxn and let (A)=∑ =1,)≠ denote the deleted absolute row sums of A. Then all eigenvalues of A are located in the union. of n discs ∪=∈c:|2-al≤r(4}=G( 讠=1 Furthermore, if a union of k of these n discs forms a connected region that is disjoint from all of the remaining n-k discs, then there are precisely h eigenvalues of a in this region emma 1.1 9, Lemma 8.2.7 part(i), p. 498/ Let A E Rnxn be given, let aec be given and suppose a and y are vectors such that (i) A c=A.c,(2i)A y=Xy, and(iii a y=1 If=P(A)>0, where p(a) denotes the spectral radius of A, and X is the only eigenvalue of A with noduLus PlA), then limm-oo(X-A)mIy The matrix A E Rnxn is reducible if either (i)n=l and A=0, or(ii)n2 2 and there exists a permutation matrix P E Rmxm such that p aP is in block upper triangular form A matrix is irreducible if it is not reducible Theorem 1.3 9, Theorem 6.2.24, p. 362/ The matrit A E Rnxn is irreducible if and only if r(a)is strongly connected A vector or matrix A is nonnegative(respectively, positive): denoted as 20(respec- tively, s >0) or A20(respectively, A>0). if all of its entries are nonnegative(respectively, positive). For nonnegative matrices, A>B (respectively, A> B) implies that A-B is a nonnegative(respectively. positive) matrix. Two n x n nonnegative matrices P and Q are of the same type if they have zero entries and positive entries in the same locations(see [ 37) We use the notation Pn Q to denote that P and Q are of the same type Theorem 1. 49, Theorem 8.8.1, p. 508/If A E Rnxn is nonnegative, then p(a)is an eigenvalue of A and there is a nonnegative vector 20, 2f0, such that A c-P(a).C Theorem 1. 5 9, Perron - s theorem, p. 508/If A E Rnxn is irreducible and non negative, then (i)p(a)>0,ii)p(a)is an eigenvalue of A,(iii) there is a positive vector such that A c=P(A)a, and (iv) p(a)is an algebraically(and hence geometrically) simple eigenvalue of a A square nonnegative matrix is primitive if it is irreducible and has exactly one eigenvalue of maximum modulus, which is necessarily positive. A square nonnegative matrix is row stochastic if all of its row sums are 1 9, p. 526. Every row-stochastic matrix has 1 as an eigenvalue with an associated eigenvector 1n. The spectral radius of a row-stochastic natrix is 1 because 1 is an eigenvalue and Theorern 1.2 implies that all of the eigenvalues are contained in a closed unit disc. The row-stochastic matrix A is indecomposable and aperiodic (SIA)if limk-xo A=lnv where v is a column vector 37. Given a row-stochastic matrix S=Siil E Rnxn, define the matrix function Note that x(S)<1 for every row-stochastic matrix S. If x(s)<1, S is a scrambling matrix Also note that x(S)=0 if and only if the rows of S are identical [37 Theorem 1.6 9, Theorem 8.5.1, p. 516/ 1fAE rnxn is nonnegative and primitive, then imk→[(4)-14小]→vr, where a=p(4),A=p(A)v,>0,>0,mndr=1 Theorem 1.7 9, Theorem 8.5.2, p. 510/ IfAE RXn is nonnegative, then A is primitive if and only if am>0 for some positive integer m Because the spectral radius of a row-stochastic matrix is 1, Theorem 1.6 implies that if A is row stochastic and primitive: then limk-o0 A=lnv, where Av=1,v>0,and Lemma1.28/ Suppose that u∈R,V∈Rx,X∈R,mdY∈Rx.The following arguments are valid ()(UV)(X8Y)=UX⑧VY (i)(U⑧V)=U⑧V liii) Suppose that u and v are invertible. Then(U&v)-=u-l8v-I (iv) ifU and v are symmetrical, so is U& V (U) If U and v are symmetrical positive definite (respectively, positive semidefinite), so is UOV 1.3 Linear and nonlinear systems theory Consider the linear state equation (t)=A(t)](t)+b(ta(t),ato ()=C(t)x(t)+D(t)u(t) where a(ter is the state vector, u(t)E Rm is the input signal, y(t)E RP is the output signal,A(t)∈ IR,B(t)∈Rxmn,C(t)∈RP"n,andD(t)∈Rp×m. The linear state equation 3)is linear time invariant (LTI) if all of the matrices A, B, C, and D are constant and is linear time varying(LTV otherwise The solution of the state is given by x(t)-(,to)o+/Φ(t,o)B(o)u(o)do,t≥to, where (t, to) is transition matri.c defined as t 1 (t60)n+/A(1)don+/4(a1)/A()dm2don+… For an LTI system, (t, to)=eA(t-to). The solution of the output is given by 0(0)=C()重(,0)0+/C)重(,o)B()(o)+D()(),t≥1o to Consider the autonomous system where f: D-Rn is a locally Lipschitz map from a domain DC Rn into Rn Theorem 1.8/12, Thcorem 4.2 Let c=0 be an equilibrium point for(4). Let V: R>R be a continuously differentiable function such that (0)=0amdV(x)>0,Vx≠0 cl‖→∞→V(x)→ (x)<0,Vx≠0 Then =0 is globally asymptotically stable Definition 1. 9 12, p. 127 A set m is said to be an invariant set with respect to(4 )if (0)∈ M implies(t)∈M,Mt∈R. A set m is said to be a positively invariant set if lies x(t)∈M,t≥0 Theorem 1.10 33, Theorem 3. 4 Local Invariance Set Theorem)/ Consider the autonomous system(4). Let V: Rh-IR be a continuously differentiable function. Assume that ●fors0meC 0, the region Sc defined by v(r)<c is bounded V(x)<0,x∈ let e be the set of all points in Q where V()=0, and let m be the largest invariant set in E. Ther euery solutioN. c(t) starting in Qc approaches M, as t-+00 Theorem 1.11 33, Theorem 3.5(GLobaL Invariance Set Theorem )/ Con sider the autonorno1s system(4). Let V: R-R be a continuously differentiable function. Assume that V(x)<0.Vx∈R V(x)→∝as|l→∞,1 Let e be the set of all points where V(a)=0, and let m be the largest invariant set in E Then all solutions globally asymptotically converge to M, as t-00 Lemma 1.3 33, Lemma 4. 2(Barbalat)/ If the differentiable function f(t) has a finite limit, ast→∞,anf(t) is uniformly continuous,2 then f(t)→0,ast→o Lemma 1.4/33, Lemma 4.3 (Lyapinou-like Lemma) If a scalar function V(a, t)satisfies the following conditions (a, t)is lower bounded . V(a, t) is negative semidefinite is uniformly continuous in t; then v(x,t)→0,ast→.3 Definition 1. 1212, Defnition 4. 2, p. 144/ A continuous function a: 0, a)0, oo) is said to belong to class K if it is strictly increasing and c(0)=0. It, i s said to belong to cla. s Coo if a-∞mnda(r)→∞,Osr→∞ Definition 1.13 12, Defnition 4.3, p. 144/ A continuous function B 10,o)is said to belong to class kl if, for each fi.ced s, the mapping B(r, s) belongs to class K with respect to r and, for each fi ced r, the mapping B(r, s)is decreasing with respect to s andB6(r,s)→0,ass→∝ 2 Overview of recent Research in Distributed Control of Multi-agent systems The reading materials for this subsection are [19, 28. See also the slides I A function satisfying this condition is said to be radially unbounded 2A sufficient condition for a differentiable function to be uniformly continuous is that its derivative is bounded BLemma 1.4 follows from Lemma 1.3 3 Fundamental results in Distributed consensus for Agents with Single-integrator Dynamics The reading materials for this subsection are 3, 5, 11, 17, 20, 26, 31, 30 Consider information states with single-integrator dynamics given by where Si e rm is the information state and w; E Rm is the information control input of the ith agent. A continuous-time consensus algorithm is given by a(+(52-5;) where aii (t)is the (i, j) entry of the adjacency matrix An(t)E Rnxn at time t. Note that (t)>0if (, i)c En at time t and ai,(t)=0 otherwise, V,+i. Intuitively, the information state of each agent is driven toward the information states of its neighbors. Equations(5) and(6) can be written in matrix form as 5=-[Cn(t)②I]5 where S=5i.., 5n, Cn(t Ernxn is the nonsymmetrical Laplacian matrix at time t and denotes the Kronecker product. With(6), consensus is achieved or reached by the team of agents if, for all i(0) and all i,=1,,n,‖s(t)-5(t)‖→0,ast→∞ When interaction among agents occurs at discrete instants, the information state is up- dated using a difference equation. a discrete-time consensus algorithm is given by [k+1 ∑ dk]5,[ (8) rhere e 1O, 1,.. is the discrete-time index; di,[k] is the(i,j) entry of a row-stochastic matrix Dn=[dii] E RXm at the discrete-time index k with the additional assumption that diik>0 for all i=1, ……,7land d,>0,V≠j,i(;,)∈ En and di=0 otherwise Intuitively, the information state of each agent is updated as the weighted average of its current state and the current states of its neighbors. Equation( 8)can be written in matrix orin as 5[+1-(Dn⑧Lm)k With(8), consensus is achieved or reached by the team of agents if, for all $i 0 and all 一5k‖→0,ask The main results of 31, 36 will be introduced by the instructor in the class Key result from [11] (1)Main result: Algorithm( 9) achieves average consensus if undirected graph gn(t)is con- nected jointly. (2)Approach: algebraic graph theory, matrix theory Key property used in the proof: Let S1, S2, .. Sk ERan be a finite set of SIA matrices with the property that for each sequence Siu, Si,..., Si, of positive length, the matrix prod- uct Si is siA. Then, for each infinite sequence Si, Six, .,. there exists a column vector y such that limi-oo Sii Si (see[37). More detailed pi roo e main result of ll will be shown by the instructor in the class Key result from 20: (1) Main result: Suppose that An is constant. Algorithm(G)achieves average consensus if and only if directed graph Gn is strongly connected and balanced or undirected graph gr is connected. Suppose that An(t)is switching. Algorithm(6) achieves average consensus if directed graph gn is strongly connected and balanced at each time instant (2)Approach: algebraic graph theory, Lyapunov theory, matrix theory Key properties used: If directed graph gn is strongly connected and balanced, then L has a simple zero eigenvalue with an associated right eigenvector In and an associated left eigenvector ln, and all other eigenvalue have positive real parts. more detailed proof of the main result of 20 will be shown by the instructor in the class Key result from [17 Main result: Algorithm( 9)achieves consensus if and only if there exists K>0 such that the union of directed graphs gn(t) has a directed spanning tree across each interval of ength Kh, where is the sample time (2)Approach: algebraic graph theory, set-valued Lyapunov theory Key technique used in the proof: a set-valued Lyapunov function V is defined as v(a1,., an (conv(31,., nD", where conv, .., n denotes the convex hull of 21,..., an, and Xn≌ⅹ×…xX. More detailed proof of the main result of17 will be shown by the instructor in the class Key result from 26: (1)Main result: Suppose that An is constant. Algorithm(6) achieves consensus if and only if directed graph gn has a directed spanning tree. Suppose that An(t)is switching Algorithm(6) achieves consensus if directed graph gn(t) has a directed spanning tree jointly 2)Approach: algebraic graph theory, matrix theory Key technique used in the proof: The nonsymmetric Laplacian matrix Ln has a simple zero eigenvalue and all other eigenvalues have positive real parts if and only if n has a directed spanning tree. In addition, there exist In satisfying LIn=0 and a nonnegative vector pE Rn satisfying p Lm =0 and p ln=1. That is, In, and p are, respectively, right and eft eigenvectors of Lm associated with the zero eigenvalue. If g has a directed spanning tree, then p is unique. More detailed proof of the main result of [26 will be shown by the instructor in the class Key result from 5 (1)Main result: Algorithm(9)achieves consensus if and only if there exists K>0 such that the composition of directed graphs gn (t) has a directed spanning tree across each interval of ength Kh, where is the sample time (2)Approach: A graph composition operation is defined which is used to discuss the con- nectivity of a sequence of graphs More detailed proof of the main result of 5 will be shown by the instructor in the class

...展开详情
img
LAMYY

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源