组合连通拓扑下基于事件触发的多智能体快速一致性算法

2018-04-23陈世明管俊杰高彦丽裴惠琴邱昀

自动化学报 2018年12期

陈世明管俊杰高彦丽裴惠琴邱昀

近年来,群系统的分布式协同控制因其极强的实际应用背景已成为控制工程、生物学、物理学等学科广泛关注的一个重要问题.例如多航体集结[1−2]、编队控制[3−4]、蜂拥[5−6]、姿态校整[7−8]等. 这些协同控制任务都可以统一到多智能体系统的信息一致性这一理论框架内.一致性理论的基本思想是每一个智能体基于自己和其邻居的信息状态更新自身信息,从而使得所有个体的最终信息收敛到一个共同的值,即达到一致.

一致性问题的研究可追溯到1995年Vicsek等[9]基于数学方程的描述方式,用网络建立个体之间的信息交互,提出了一个简单的离散多智能体系统模型(Vicsek模型).2003年Jadbabaie等[10]针对Vicsek模型进行了更深入的研究,利用图论和矩阵论给出Vicsek模型的理论解释,从本质上揭示了多智能体系统的群集现象.Olfati-Saber等[11]在此基础上建立多智能体系统的理论框架并提出了经典的一致性协议.之后,Ren等[12]研究了一阶连续和离散多智能体系统的一致性问题,提出在通信拓扑具有生成树的情况下,所有节点的状态能达成一致.

为改善一致性收敛速度,文献[13]阐述了预测控制在多智能体系统中的应用,提出分布式模型预测控制策略,有效解决了存在有界控制输入的多智能体系统一致性问题.文献[14]研究了多智能体系统一致性的收敛速度问题,提出一种具有状态预测器的一致性控制协议,在该控制协议下多智能体系统能以更快的速度达到一致.文献[15]研究了二阶多智能体系统一致性的收敛速度问题,提出一种快速分布式平均一致性算法,在每次控制输入都加入基于邻居状态信息的线性预测量,加快了多智能体系统状态值收敛到平均值的速度.

在实际应用中,智能体自身的能量和通信信道的带宽都是有限的,一般而言,控制任务中的测量、通信和控制协议更新都是周期性执行的,即周期采样控制方法[16−17].为了保证所有执行点的性能,采样时间常数通常取一个保守值,这通常会造成通信和计算资源的浪费.随着研究的深入及解决实际应用中控制器周期性执行任务导致的计算资源和通信资源浪费问题,基于事件触发的多智能体控制策略研究得以开展和应用.在事件触发控制策略下,控制任务只按需执行,从而达到节约系统的资源包括智能体的计算能力、通信能力、能源储备等目的.目前,基于事件触发控制的多智能体系统一致性已取得不少有意义的研究成果.在固定拓扑下,文献[18]提出了一阶系统的事件触发控制协议,并针对其设计了一种与智能体系统状态有关的事件触发条件,证明不存在Zeno行为,结果表明事件触发控制在具有期待性能的同时减少了采样次数.文献[19]提出了一个与时间有关的触发函数.文献[20]研究了二阶多智能体系统的事件触发控制.

在时变拓扑下,文献[21]研究了切换拓扑下的事件触发控制一致性问题,假设每个切换区间里的多智能体通信拓扑是强连通的,设计了一个事件触发控制策略并解决了切换拓扑下的一致性问题.文献[22]研究了领导跟随系统在切换拓扑结构下的事件触发一致性问题,基于邻居个体的状态估计值设计了一个反馈控制器,在该反馈控制器和事件条件共同作用下,系统能在有效节约通信资源的同时很好地实现切换拓扑下的领导跟随一致性.文献[23]研究了切换拓扑下线性异质多智能体系统的协同输出调节问题,设计了一个基于事件触发的观测器,并在此基础上提出基于输出反馈的输出调节控制策略,使得异质多智能体系统能在抑制干扰的同时实现对外部系统信号的渐近跟踪一致.

以上时变拓扑研究需要保证时变拓扑是连通的或是强连通的.但实际中,由于系统通信带宽有限,环境干扰等因素,时变拓扑并不能保证一直连通.文献[24]研究了组合连通拓扑结构下的一致性问题,设计了一个静态事件触发函数使得分歧向量渐近趋于状态平均值附近的有界区域.文献[25]提出一个与触发时刻状态相关的触发函数使得组合连通拓扑下的多智能体系统达成一致性.

考虑当前组合连通拓扑下多智能体系统基于事件触发一致性控制研究成果,大都集中于控制协议设计或触发条件的选取,没有兼顾系统的收敛速度,而系统的收敛速度是一致性问题研究的一项重要性能指标.本文围绕组合连通拓扑下多智能体系统基于事件触发的一致性问题展开研究,提出一种新的具有状态预测器的事件触发一致性控制协议,并为智能个体给出了基于系统状态信息的事件触发条件.在每个事件触发时刻,每个智能体都对其邻居智能体的未来状态作出预测,再通过通信将预测的状态和触发时刻的状态传递给它的邻居个体,经所提一致性协议计算使系统快速达成一致性.基于Lyapunov稳定性理论和代数图论证明了所提事件触发控制策略能有效实现组合连通拓扑下的平均一致性,并且不存在Zeno行为.最后通过仿真实验验证了所提控制策略在节约通信资源和收敛速度方面的优越性.

1 问题描述

1.1 代数图论

代数图论是多智能体系统建模和分析过程中非常重要的数学工具,智能体之间的通信关系可用图G=(V,E) 来表示. 其中V={V1,V2,···,VN}表示系统中智能个体节点的集合,E={eij=(Vi,Vj):Vi,Vj∈V}表示智能个体之间相互通信的边集.用一个非空序列J=ViEikVk···Vj表示图G中Vi到Vj的一条路径,如果在图G中任意顶点对Vi和Vj之间存在一条途径[Vi,Vj],则称Vi和Vj是连通的.如果图G中任意顶点对之间存在一条路径,则称图G为连通图.用邻接矩阵A=[aij]∈RN×N表示网络中节点之间的连接关系,若节点i能够收到节点j的信息,则aij=1,否则aij=0.如果aij=aji则称图G为无向图.在多智能体网络中用Ni={Vj∈V:(Vi,Vj)∈E}表示节点i的邻居节点集合.在无向图中图G的度矩阵D=diag{di}表示节点i的度所构成的对角矩阵,有向图中D=diag{di}表示节点i的入度所构成的对角矩阵.图G的Laplacian矩阵L表示为L=D−A.对无向图而言Laplacian矩阵L是一个半正定的对称矩阵,有一个零特征值,其对应的特征向量为1n=(1,1,···,1)T,其他所有非零特征值都是正实数.Laplacian矩阵L的特征值表示为λ1,λ2,···,λn,并且 0=λ1≤λ2≤···≤λn,第 2 个特征值λ2称为图G的代数连通度.

1.2 组合连通拓扑

实际应用中,往往由于系统通信带宽有限、外界环境存在干扰等因素导致通信拓扑时变且不连通,对组合连通定义如下.

定义1.设图G1,G2,···,Gm具有相同的顶点集V,记它们的并集为G1−m,它的节点集也为V,边集是所有图G1,G2,···,Gm的边的并集.如果并图G1−m是连通的则称图G1,G2,···,Gm是组合连通的.

当多智能体系统通信拓扑随时间变化时,用函数σ(t):[0,∞)→{1,2,···,m}表示切换信号来决定通信拓扑.Gσ(t)表示t时刻智能体的通信拓扑图,Lσ(t)为对应的Laplacian矩阵,Niσ(t)为智能体i的邻居节点集.

考虑一组非零、不重叠、无限严格递增的连续时间区间[tk,tk+1),k=0,1,2,···且tk+1−tk=T常数T>0.在时间区间[tk,tk+1)中存在有限个非重叠时间子区间,其中且满足.

引理1[26].对于一个Laplacian矩阵为L的无向图G且有非零向量x满足1Tx=0则有.

1.3 系统模型

考虑有N个智能体的一阶多智能体系统,智能体的动力学方程表示为

其中,xi(t)∈Rn是智能体i的状态变量,ui(t)∈Rn表示控制输入.

常用一致性控制协议如下:

系统的闭环动力学方程可表示为

其中,x(t)=[x1(t),x2(t),···,xN(t)]T为智能体的状态向量,L为通信拓扑图的拉普拉斯矩阵,相应的u(t)=[u1(t),u2(t),···,uN(t)]T为智能体控制输入向量.

引理2[11].对于类似于式(1)的多智能体系统,收敛速度与Laplacian矩阵的最小非零特征值λ2相关,一般λ2越大,多智能体收敛到平衡状态的速度越快.

2 组合连通拓扑下基于事件触发的多智能体快速一致性算法

假设1.由智能体组成的通信拓扑图的集合在时间区间[tk,tk+1),k=0,1,2,···是组合连通的.

通常事件条件可用一个数学不等式来表示.因此,当不满足不等式时事件触发即执行通信任务.用表示第i个智能体的第k次触发瞬间,表示第k次触发间隔.用rk表示多智能体系统的事件触发时刻,易知时间序列{rk}包括智能体i的所有事件触发时刻.

为了解决切换拓扑下基于事件触发控制协议的收敛速度问题,本文提出在每个事件触发时刻,每个智能体都能对其邻居智能体的未来状态作出预测,并用这个预测的状态构造控制协议,从而使得多智能体系统可以更快地收敛到平衡状态.

将误差向量e(t)=[e1(t),e2(t),···,eN(t)]T和状态向量x(t)=[x1(t),x2(t),···,xN(t)]T写成矩阵形式:

注1.式(5)中x(rk)不是x(t)在t=rk时的值,而是向量. 其中为智能体i最近的触发时刻.

由于在拓扑图中孤立的点没有控制输入,本文只关注有邻居节点的顶点.根据拓扑图中连通部分对顶点进行分类,对任意一个图Gp,定义为图中包含至少两个节点的部分,S0=为图中只有一个节点的部分,即孤立顶点,其中1≤q≤Q≤N.令为的顶点集,.经过重新排列所有智能体的顺序,图Gp的Laplacian矩阵Lp可以写成Lp,其中是连通部分的Laplacian矩阵.易知当l=1,···,p时,有简单零特征值;l=q+1,···,Q时,=0.

注2.每个在的节点都没有控制输入,因此只要完善属于Sc中的节点的事件触发控制策略即可.为便于分析,定义属于的节点的状态向量,对应.令,可得的分歧向量另外一个分歧向量,易知是一个不变量,并且.定义el(t),有.

注3.类似于x(rk)的定义,,,其中为智能体i最近的触发时刻,具有相同性质.

对每个智能体设计事件触发条件,给出组合连通拓扑结构下的事件触发条件如下:

定理1.考虑多智能体系统(1)在假设1下,r0=0对每个分支,事件触发条件为

证明.考虑闭环系统(6),选择Lyapunov函数V(t)=(1/2)δT(t)δ(t). 易知V(t) 为连续函数,除在切换拓扑瞬间和事件触发瞬间rk外连续可微,定义V(t)在和rk瞬间的导数为正.

若多智能体系统在t时刻的通信拓扑为Gp,重新排列所有智能体的顺序,可得新的Laplacian矩阵,这里是连通部分的Laplacian矩阵.因此系统(6)的Lyapunov函数V(t)关于时间t的导数为

对任意y,z∈Rn考虑不等式.

易知

由引理1,有

回顾之前定义的ti,有无穷序列V(ti),i=0,1,···.根据柯西收敛准则可知,对于任意的ε>0,总存在正整数Kε,使得当k≥Kε时,有.即当k≥Kε时,.

因为切换拓扑后的q不同,用qj表示在时间区间内q的值.

可推得

下面分析系统是否存在触发间隔的下界,即是否不存在Zeno行为.事件触发控制策略中,在每个触发时刻,系统将会依据各状态的实际值更新控制输入,并且在下一触发时刻前保持该控制输入不变.一旦到达下一触发时刻,系统用于控制输入的状态值将被更新,这时.根据以上稳定性方面作出的分析,只要满足式(7),系统都将是稳定的,可以不用更新控制输入.从而在不更新控制输入的情况下,|eli(t)|将不断增大,直到不满足该不等式.如此,消除了Zeno行为.(t)始终负定,系统的稳定性将得到保证,如果系统在该控制协议下存在Zeno行为,那么系统将不可能满足式(7)且达到渐近稳定.在接下来的定理中将证明所提控制策略中不存在Zeno行为,也就是说时间rk和rk+1之间的间隔应严格大于零.

定理2.对于多智能体系统(1),在假设1的前提下,通过控制协议(4)和事件触发条件(7)可以使系统达成一致并且不存在Zeno行为.

证明.使用反证法,如注1所述,只考虑属于集合Sc的顶点.假设存在Zeno行为,即在有限的时间内会触发无数次的事件.分两种情况.

情况1.智能体li在第k次触发间隔内通信,其中c为与状态预测量相关的常数,则拓扑图固定的,并且它的邻居个体也没有触发事件.则以及触发条件式(7)的右侧都是常数.定义eli(t)在时刻的导数是右导数.由于,且.由式(7)可知,第k+1次触发时有

情况2.与情况1相反,在时刻发生切换拓扑或智能体i的邻居个体有事件触发,从而使得.由于按情况1有,所以, 其中.

两种情况下事件触发间隔都存在正下界,然而触发无数次具有触发间隔下界的事件只会发生在无限长时间间隔内,这与假设相悖.所以不存在Zeno行为.□

3 仿真实例

考虑多智能体系统由6个智能体节点组成,假设可能的通信拓扑图{G1,G2,G3,G4}如图1所示.由图1可知,每个拓扑图都是不连通的,但拓扑图的并图G1∪G2∪G3∪G4是连通的.此外还假设拓扑图的切换顺序为G1→G2→G3→G4→G1···.

将第2节所提具有状态预测器的多智能体事件触发一致性控制策略与文献[24−25]中的事件触发策略进行比较,以验证本文所提控制策略的性能.文献[24−25]中的控制协议相同,都为

文献[24]中的静态事件条件为

文献[25]中关于触发时刻状态的事件条件为

图1 拓扑图Fig.1 Topological graph

假设初始状态为x(0)=[−2−1 0 2 3 1]设置拓扑切换时间间隔τ=0.5s,由通信拓扑易知图中所有的连通部分,并且将它们归类到集合Sc和S0中,对于控制策略(7),取ρ=0.95,γ=0.3.对控制策略(9)和(10),仍按原文中取ρ=0.95,a=1,c0=0.03.

图2是τ=0.5s时,状态xi,i=1,2,3,4,5,6在控制策略(9)(图2(a))、控制策略(10)(图2(b))和控制策略(7)(图2(c))下的运动轨迹.由图可知,三种事件触发控制策略都能达成一致性,且在控制策略(7)下系统更快地收敛到了平衡状态.

图2τ=0.5s时,三种控制策略下的状态轨迹Fig.2 The state trajectory under three kinds of control scheme whenτ=0.5s

图3τ=0.5s时三种控制策略下的分歧向量范数Fig.3 The Euclidean norm of disagreement vectorunder three kinds of control scheme whenτ=0.5s

图4对比了加状态预测器的控制策略(图4(a))在τ=0.5s时,状态xi(i=1,2,3,4,5,6)的轨迹.未加状态预测时系统收敛到平衡状态需要21.16s,文中所提策略下仅需10.89s,表明设计的状态预测器能有效地提升系统收敛速度.

图4 有无状态预测控制策略下状态轨迹对比图Fig.4 The comparison diagram between predictive control scheme and common control scheme

图5是每个智能体在相应控制策略下的触发间隔图.系统在控制策略(7),(9)和(10)下的平均触发时间间隔分别为1.1474s,0.9461s和0.7209s.显然多智能体系统在控制策略(7)下比在控制策略(9)和(10)下有更长的平均触发时间间隔,因此本文所提的事件触发条件在节约通信和计算资源方面具有更好的性能.

进一步研究拓扑切换时间间隔τ对平均触发时间间隔的影响.保持参数ρ,a,c0,γ的取值不变,分别设置拓扑切换间隔τ为0.4s,0.5s和0.6s.表1给出了系统在各事件条件,不同切换拓扑时间τ下的平均触发间隔时间.由表1可知,平均触发时间间隔随着拓扑切换周期变长而增加,并且在控制策略(7)下系统始终具有较长的平均触发时间间隔.这进一步表明本文所提的事件触发控制策略在节约通信和计算资源方面的性能.

4 结论

本文研究了在组合连通拓扑下基于事件触发的多智能体系统平均一致性问题.提出一种新的具有状态预测器的事件触发一致性控制协议,通过分析拓扑图中的连通部分,为每个智能体给出了基于系统状态信息的触发条件.在每个事件触发时刻,每个智能体都对其邻居智能体的未来状态作出预测,再通过通信将预测的状态和触发时刻的状态传递给它的邻居个体,经所提一致性控制协议使系统达成一致性.在该控制策略下多智能体系统可在节约通信和计算资源的同时具有更快的收敛速度.基于Lyapunov稳定性理论和代数图论,证明所提事件触发控制策略能够有效实现组合连通拓扑结构下的平均一致性,并且不存在Zeno行为.最后通过与已有文献中基于事件触发的一致性控制策略比较,仿真验证了所提控制策略在节约通信资源和收敛速度方面的优越性.