网络动态智能体的趋同协议

网络动态智能体的趋同协议摘要：本文介绍了网络动态智能体的线性和非线性趋同协议，趋同协议允许智能体以分布和协同的方式一致。考虑了存在时间延迟和信道的网络通信，这里涉及了滤波影响的情况。找到了最大固定时滞的紧的上界，该上界在网络中是允许的。结果显示网络的连通性是得到趋同协议的关键。通过分析一类非线性协议的收敛性，研究了存在有界输入的一致性情况。通过引入一个Lyapunov函数量化网络节点间全局的不一致性。最后给出了网络中具有时滞通信和限制输入的趋同协议的仿真结果。1.引言目前，在多节点或者多智能体系统协调的背景下经常出现的一个重要问题是一组一致性或者趋同问题[1-3]。多智能体系统在很多应用中广泛的出现，包括无人驾驶飞机的编队飞行(UAV)，卫星群，飞行器的控制，自动高速公路系统和通信网络中的拥塞控制[4-8]。上述应用证明了设计和分析趋同协议的重要性，以便研究网络中通信的动态智能体的一致性问题[9-11]。这些动态智能体可能或者不能代表物理系统。假设这些动态智能体是物理模型，那么系统输入的限制必须考虑。这很自然地指引我们设计和分析非线性趋同协议[12-16]。趋同问题在分布式系统的背景下很有意义[1]，并且在计算机科学领域有很长的发展历史。在文献[2]中，人们已经认识到Laplacian图、代数图理论中的著名矩阵[3]和趋同问题特殊情况的关系非常重要。在已有文献中，所有的智能交通是线性动力系统并且网络具有理想的连接(即连接的传递函数是1)。此外，某些Nyquist图对于传真等多节点的编队稳定性的分析非常有用。对于编队稳定性的一个更合适的代替是将编队表示成刚性的和能够扩展的图或者结构[4]。在本文中，利用标准的多变量频域对线性趋同协议的收敛性进行分析。本文的两个创新点是研究了带有时滞的网络和有界输入的动态系统。在文献[5]中，Laplacian图已经出现在多航天器的编队中(即一个特殊的一致性问题)。关于3-D空间中飞行的动态智能体编队问题的一个非正式算法最早由Reynolds在1987年给出，但是没有收敛性的证明[6]。在文献[7]中，作者试图在2R中对Reynolds的集成型动态智能体编队算法的收敛性在修改后进行证明，证明中的关键假设是适时地对图保持连通提供高概率平均值。2.预备知识：代数图论令(,)GVE表示具有顶点的集合V和边的集合E的图。每个点记为ivV，或者:{1,2,,}iIn。每条边记为(,)ijevv或者eij。定义iv和jv分别为边(,)ijvv的尾和头。假设本文中所有的图都是无向图。图的方向是对每条无向边头和尾的选择。固定方向的图中边的集合记为0E。因此，0E包含两条边,ijjiE中的一条。令||nV和0||mE。点i的邻居的集合记为{:}iNjijE。点iv的度是它的邻居||iN的个数并记为deg()iv。矩阵的度是一个nn矩阵，定义为(){}ijG，这里deg(),:0,iijvijij。令A表示图G的邻接矩阵。G的Laplacian矩阵定义为LA。L的一个重要的性质是L的所有行和为0，所以0(1,1,,1)TneR是L的对应于特征值0的特征向量。定义关联矩阵是个nm矩阵为[]ijCc，这里1,,:1,,0,ikikikvecve如果是边的头如果是边的尾其他。Laplacian矩阵满足TLCC。众所周知，不管图G的方向如何选择，该性质都成立[3]。令ix表示指定的iv的实值标量。则1(,)Tnxxx表示图G的状态。定义图的Laplacian势为1()2TGxxLx。引理1(Laplacian势)图的Laplacian势是半正定的并且满足下面的性质：02()TijijExLxxx。进一步，给定一个连通图，当且仅当ijxx，,ij有()0Gx。证明由于2||||TTTTxLxxCCxCx，Laplacian势是半正定的。此外，如果02()ijijExx0，则对于所有的边0ijE，0ijxx。如果图是连通的，则所有节点的值相等。反之很显然，即如果所有节点的值是相等的，则()0Gx。定义1(一致性)令ix表示节点iv，iI的值。当且仅当ijxx时，称节点iv和jv是一致的。类似地，当且仅当ijxx时，称节点iv和jv不是一致的。根据引理1，图G的Laplacian势是所有节点不一致性的量测。如果G的至少两个邻居节点是不一致的，则()0Gx。因此，使()Gx最小化等价于达到趋同。定义2(趋同)令所有节点的值x是下列微分方程()xfx，0(0)nxxR(1)的解。此外，令:nRR是多输入1(,)Tnxxx的单输出映射，并且有()yx。当且仅当图的所有节点是一致的且对于有限时间0T有()((0))ixTx，iI，则称所有节点关于是趋同的。类似地，令xx是(1)的全局或局部渐近稳定平衡点。当且仅当((0))ixx，iI，则称初值为0ix的图的所有节点关于是全局或局部渐近趋同的。例1运算的几个常用例子如下11()()niixAvexxn12()()=max{,,,}nxMaxxxxx12()()=min{,,,}nxMinxxxx这些算法的趋同分别表示为平均趋同，最大趋同和最小趋同。对于运算的一致性问题成为趋同。引理2(连通图和Laplacian图[3])假设图G有c个连通的部分，则rank()rank()LCnc。特别地，对于连通图，即1c，有rank()1Ln。在引理2的基础上，当且仅当图是连通的，L的0特征值的代数重数是1。此外，对于非连通图，G的所有其它特征值都是正实数。3.线性趋同协议在这一部分，给出两个存在或者不存在时滞通信的积分器网络的线性趋同协议。定理1令G是连通图并且假设G的每个节点应用下列分布式线性协议()iijijNuxx。则节点的值向量x是与Laplacian势()Gx相应的梯度系统的解，即()GxLxx，(0)nxR。此外，图的所有节点渐近地达到平均趋同，即令lim()txxt，则ijxx((0))Avex，,ij，ij。证明令x是系统xLx的平衡点。则0Lx并且x是对应于Laplacian矩阵L的零特征值10的特征向量。另一方面，得到1()()02TGxxLx且由G的连通性可得ijxxa，,ij，即(,,)Txaa，aR。注意到10niiu，所以()xAvex是不变量，即0x，得到()((0))AvexAvex。但是()Avexa，因此对于所有节点iI，有((0))ixAvex。注意到L的所有特征值除了单零特征值之外都是负的。因此，系统的所有解在对应于10的特征空间中渐近收敛于点x。这意味着所有节点全局渐近地达到平均趋同。分析定理1中协议收敛的一个基本方法是使用如下的Laplace变换xLx。得到0()()(0)XsGsx，这里0()Gs是多输入多输出传递函数10()()nGssIL。这里0()Gs的下标0表示没有时滞通信。下面的结果给出了网络中两个节点在时滞通信的非保守结合下仍能达到平均趋同。定理2假设连通图G的所有节点iv在固定的时滞0之后从它的邻居节点收到信息(即jx)，并且应用下列线性协议(()())iijijNuxtxt。则节点的值是下列线性时滞微分方程()xLxt，(0)nxR的解。此外，当且仅当下列两个等价条件(i)(0,)，2n，max()nL，(ii)()sses的Nyquist图在1k，1k附近存在零包围成立，则图的所有节点全局渐近地达到平均趋同。进一步，对于，系统在频率n下有全局渐近稳定的振动解。证明可参见[8]中定理2的证明。4.行为图和非线性协议机器人和航天器的姿势列队问题是趋同问题的一种特殊情况。对于这些物理系统，假设它们姿势的取值范围无界是没有意义的，即输入力矩是有界的。这表明趋同协议的发展保证了每个节点的所有输入保持有界性。这自然地导致非线性趋同协议的设计和分析。首先，介绍行为图的概念，这是非线性趋同协议的一般设计工具。令(,)VE表示具有节点的集合V和边的集合E的图。图(,)VE被行为函数的集合增大，该函数的元素:ijRR与图的边(,)ijijevvE对应，称为行为图，记为(,,)GVE。在本文中，假设行为函数()x满足下列性质：(i)()x连续且满足局部Lipschitz条件，(ii)()00xx，(iii)()()xx，xR，(iv)()(()())0xyxy，xy。令0()()xijijxsds，则()ijx与ijeE对应，称为边成本。定义边成本的集合为{:(,)}ijijvvE，则(,,)GVE称为成本图。注2显然，对于任意的行为图和行为函数，存在成本图。反之成立说明连续微分凸函数在0x处有全局最小值。特别地，当所有边的行为函数都等于时，我们用(,,)GVE表示行为图，并称之为单向行为图。本文的重点是单向行为图的应用，它为网络动态系统提供了趋同协议和算法。考虑动态图，这里每个节点是一个动态系统(,)iiixfxu，iI。假设每个节点是一个积分器，即iixu，iI。定理3(非线性趋同协议)考虑有积分器节点的动态行为图(,,)GVE，假设(,)VE是连通图。假设所有的行为边是对称的ijji并且每个节点提供下列输入()iiijjijNuxx，iI，这里{:}iNjIijE。则由行为图的所有节点得到的全局渐近性可推出决定值((0))xAvex存在。证明令()Avex，注意到由于10niiu，是一个不变量，即0并且对于所有的0t，()((0))tAvex。可将x写成x1δ，这里(1,,1)T1，δ是不一致向量。注意到0ii并且xδ，由于jixxji，,ij，所以该不一致向量满足下列的不一致动态方程()iiijjijN，1,,in。(2)定义不一致函数族为2()||||Vδδ，得到1(,)()2()()()iiijjiiijjijjiijijNijEVδ(,)()()0jiiijjiij。注意到对于所有的边(,)ijE，由()0Vδ得到ij。因为图是连通的，对于所有的,ijI得到ij。由δ的定义，0ii，所以对于所有的i，0i。也就是说，由于δ0有()0Vδ，因此不一致函数族()Vδ对于不一致动态方程是有效的Lyapunov函数。所以δ0对于(2)是全局渐近稳定的，即当t时，x1，并且可得到平均趋同是全局渐近的。5.仿真结果考虑解决图1中aG和bG的平均趋同问题，为具有信息流bG的网络给出了非线性趋同协议的仿真结果。显然，一致性是在有界输入下得到的。图2给出时滞通信为，节点数为10n的网络的状态轨迹，这里0，max0.5，maxmax2()0.266aG是有初始条件的零均值随机集合。显然，在图2(a)和(b)中对于max的情况可得到一致性结果。图1：用于研究协同问题的无向图(a)aG和(b)bG时间-时滞=0(秒)时间(秒)(a)图2：图1中带有时滞通信bG的趋同问题：(a)0和(b)max0.5时间-时滞=0.133(秒)时间(秒)(b)参考文献[1]N.A.Lynch.DistributedAlgorithms.MorganKaufmannPublishers,Inc.,1997.[2]A.FaxandR.M.Murray.Informationflowandcooper