多智能体一致性基础

ConsensusProtocolsforNetworksofDynamicAgents鲁家欢2015.4.9内容框架•1.引言：主要介绍多智能体一致性问题的发展历史；•2.问题描述：2.1.代数图论基础2.2.一致性的定义•3.线性一致性协议：3.1.无时滞的线性一致性协议3.2.有时滞的线性一致性协议•4.动态图与非线性协议•5.仿真部分1.引言：近几年来，随着计算机技术、网络技术和通信技术的飞速发展，人们对于基于网络的多智能体系统的交互和协调控制的研究越来越多。特别是，多智能体系统在无人驾驶飞行器的编队控制、分布式传感器网络、卫星的姿态控制、分布式计算以及通讯网络的拥塞控制等各个领域的广泛应用，推动着多智能体系统建模与分析的研究逐步深入。而在对多智能体系统的深入研究中，一致性问题也得到了迅速的发展。从最初的Reynolds提出的模仿动物集结的计算机模型到后来的Olfati-Saber和Murry系统提出和解决了多智能体网络系统的一致性协议的理想框架，一致性问题已经得到了丰硕的成果。2.问题描述：2.1.代数图论基础：令表示一个图，其中表示n个节点的集合，它的边集合为E。节点的下标集合为。每条边表示为或者，其中表示边的头，表示边的尾。另外，这篇文章中假定所有的图都是无向图。节点的邻居节点的集合表示为。节点的度数就是其邻居节点的个数并且表示为。度数矩阵是一个的矩阵，表示为，其中（1）令为图G的邻接矩阵，其中矩阵元素表示节点与之间有信息传递（没有特殊说明的情况下，），否则。},,{1nvvVE}{V,G},{1,2,n）（jivve,ijeivjviv}:{EijjNiiv)deg(ivnn}{)(ijGjijiviij,,0)deg(][ijaA0ijaivjv0ija1ija此时定义图的拉普拉斯矩阵为：（2）拉普拉斯矩阵的一个重要的性质是它的行和全为0，因此有一个向量是属于特征值的特征向量。如果给无向图G固定好方向，并且令边集为。定义一个的关联矩阵，其中（3）因此拉普拉斯矩阵满足特性，不管图G的方向是如何选择的，这个特性同样成立。令为节点的状态值，则图G的状态表示为。下面定义图的拉普拉斯势能函数为：（4）ALTe)1,,1,1(00},,,{21meeeEmn][ijcCotherwise,,edgetheoftailtheisif,edgetheofheadtheisif011kikiikevevcTCCLixivTnxxxx),,,(21LxxTxG21)(通过前面对图的拉普拉斯矩阵的定义，下面对拉普拉斯势能函数的特性做一介绍：引理：图的拉普拉斯势能函数是正半定的，并且满足下面的等式：（5）此外，考虑一个连通图（即图中的每个节点都可以通过有效路径链接到任意其它节点），若，当且仅当时成立。2.2.一致性的定义：令所有节点的状态值是下面微分方程的解：（6）另外，令是一个多输入单输出的函数，当输入状态值时，产生一个决策值。如果说图的所有节点达到一致性，也就是说在有限时间内，当且仅当所有节点状态一致并且。EijjiTxxLxx2)(0)(xGjixxji,,xnRxxxfx0)0(),(RRn:)(xyx0TIixTxi)),0(()(关于函数，下面给出了一些常用的例子：　　　　　　　　　　　　　　　　　　　　　　　　（7）上面提到的这些一致性分别叫作平均一致性，最大一致性和最小一致性。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　},,,min{)()(},,,max{)()(1)()(21211nnniixxxxMinxxxxxMaxxxnxAvex3.线性一致性协议3.1.无时滞的线性一致性协议：定理1：令G是一个连通图，并且假设G中的每个节点都满足下面的分布式线性协议：（8）同时，所有节点的状态值是关于拉普拉斯势能函数的梯度系统的解，既是：（9）另外，图的所有节点全局渐进地达到平均一致性，也就是说：令，于是。iNjijitxtxtu))()(()(x)(xGnxGRxLxx)0(,)()(limtxxtjijixAvexxji,,)),0((3.2.有时滞的线性一致性协议：定理2：假定一连通图的每个节点都能够在固定的通讯时延后接收到其邻居节点的信息，并且满足下面的线性协议：（10）于是，所有节点的状态值是下面时滞微分方程的解：（11）另外，图的所有节点都全局渐进地达到平均一致性，当且仅当下面两个等价条件中任意一个满足的时候：然而，当时，系统有一个震荡解，这个震荡频是。ixjx0iNjijitxtxtu))()(()(nRxtLxx)0(),()(,2with)(0,)maxLinn1,/1/)()karoundntencirclemezeroahassesofplotNyquistTheiiksn4.动态图与非线性协议机器人、太空飞行器的姿态调整是一致性问题的特殊案例，对于这些物理系统，假定它们的姿态可以无限地变化是不可能的，也就是说它们的输入扭矩是有界的。这就要求一致性协议的发展来保证所以节点的输入仍保持有界，这自然地导致了非线性一致性协议的设计与分析。首先介绍一下通常用来分析非线性一致性协议的工具—动态图的概念：令表示一个图，其中表示n个节点的集合，它的边集合为E。而一个动态图则表示为，这是图G与边作用函数相结合的图。中的元素是与图的边相关联的。现假定满足下面的特性：E}{V,G},,{1nvvV}E,{V,GRRij:Evvejiij),()(x,(x))Lipschitzlocallyandcontinuousisi,00)()xxii,),()()Rxxxiii.,0))()()(()yxyxyxiv考虑一个动态图，当中的每个节点的动态方程为：（12）现在开始，假定每个节点都是一个积分器，既：。定理3：考虑一个动态图，并且所有节点都是积分器模型，同时它是连通图。现假定图的边作用都是对称的（），并且每个节点都满足下面的输入方程：（13）其中，。从而存在一个决策值使得动态图中的每个节点都能达到全局渐进稳定。Iiuxfxiii),,(Iiuxii,}E,{V,GE}{V,GjiijiNjijijiIixxu),(}:{EijIjNi))0((xAvex定理1的证明：令是系统的一个平衡点，从而有，并且是拉普拉斯矩阵关于特征值的特征向量。另外，我们可以得到：同时，根据G的连通性，有，既。注意到，因此是一个不变量，既。这意味着，但是，因此对所有都成立。另外注意到的所有特征值都是负的，除了单个零特征值，因此系统的任何解都渐进收敛于平衡点，这就说明了图的所有节点全局渐进达到平均一致性。xLxx0LxxL010)(21LxxxTG）（jiaxxji,,RaaaxT，),,(01niiu)(xAvex0x))0(()(xAvexAveaxAve)())0((xAvexiIiLx定理3的证明：令，因为，是一个不变量，既。并且对所有都满足。下面可以将表示成：（14）其中，同时称为不一致向量。注意到以及，因此不一致向量满足下面的动态方程：（15）由于，对所有成立，定义下面的李氏函数：（16）于是，可以得到：（17）)(xAve01niiu0))0(()(xAvet0tx1xT），，（1110iix.,,1,)(niiNjijijiijijxxji,2)(V0)()()()()(2)(),(),(1ijijjiijEjijijijijijiijijiNjiiV注意到，当时，意味着，因为图是连通的，所以对所有都成立。通过对定义，，因此对所有都满足。换句话说，意味着，因此建立的李氏函数是关于不一致向量的标志的李氏泛函。总的来说，是（15）的一个全局渐进稳定点。既当时，，平均一致性可以全局渐进达到。0)(VjijiIji,0ii0ii00)(V)(V0t1)(tx