等价划分下多智能体系统能控性的一种判定方法

纪志坚

(1. 青岛大学 自动化学院 系统科学研究院,山东 青岛 266071;2. 山东省工业控制技术重点实验室,山东 青岛 266071)

1 引言

能控性是现代控制理论的一个基本概念,也是多智能体系统性能分析的一个核心问题,该问题的研究有助于认识系统的基本结构特性,促进建立多智能体动力学系统的性质与系统结构的关系,而等价划分是智能体间信息交换网络图拓扑结构的一个典型划分方法,是系统结构分解的一个重要方面,对它的研究,是深入理解系统动态演化规律的一个不可忽视的途径,这是文章研究等价划分下系统分布式能控性的主要原因。能控性概念最早是由卡尔曼(R.E.Kalman)等人在20世纪60年代初首次提出的[1],作为系统的一个基本性质,多智能体系统的能控性在近年来得到了越来越多的关注和研究,相关成果不断涌现[2-5, 31-35]。其中,得到最多研究的一个能控性定义如下:对系统中的部分节点(个体)施加外部控制输入,通过个体间的信息传递规则(即协议),在一定的时间内,将系统的全部节点从任意的初始状态转移到任意指定的终端状态,其中,被施加控制输入的节点被称为领航者(leader),其余节点则被称为跟从者(follower)。该定义借鉴了传统能控性的定义方式,它反映了将所有节点的状态驱动到任何所期望状态的能力。多智能体系统的能控性定义在网络辨识、队形控制、分布估计和生物网络等研究中均有所应用[6-13]。在2004年,Tanner首先提出了领航者-跟从者框架下的分布式能控问题,并给出了单积分器系统能控的代数充要条件,文中还指出,代数条件在图论意义上的解读是问题进一步解决的关键,这也为之后的科研工作者指出了一个重要的努力目标[14]。例如,Ji和Egerstedt基于拓扑图的等价划分给出了系统能控的一个必要条件[15]。此外,Ji等人首次证明了多智能体系统能控性只需在连通图上进行研究,这不仅揭示了多智能体系统能控性由图拓扑结构唯一决定这一事实,而且还提出了能控性基于特征向量进行判定的充要条件,从而为通过特征向量确定领航者数量和位置提供了一个方法[16]。

从领航者选取和协议设计等角度对能控性问题进行研究,可以得到能控性与拓扑结构之间关系的一些新的理解。例如,Ji等人提出了多智能体系统能控性的一种统一认识方法,表明了能控性作为系统内在性质的价值所在,并给出了非能控拓扑结构的一种构造方法[17]。Cai等人则在Laplacian矩阵结构的基础上建立了系统能控的条件,并给出了基于路形拓扑的一种能控标准型[18]。Zhao等人通过领航者数量的调整以及边权重的选取,提高了系统的能控性能,这种做法可以被认为是一种改变信息传递图拓扑结构的另一种方式[19]。

信息交换图的拓扑结构划分是拓扑结构分解的一个主要形式,它是能控性研究的一个重要途径。Lou等人研究了权重-平衡划分下的能控性问题[20];Zhang和Guan等人基于拓扑图的距离等价划分研究了多智能体分布式系统的能控子空间[21,22];Ji等人通过引入坐标划分研究了能控性的特征结构属性[23],并通过拓扑结构的另一种形式的划分,即将两类图以适当的形式进行衔接,形成一种新的具有能控性的拓扑结构,从而提出了一种构造能控拓扑图的方法[24]。除此之外,等价划分和松驰等价划分也是研究分布式能控的常用方法[15, 25-28]。例如,Martin 等人在研究中运用了能控性分解,并通过松弛等价划分给出了能控性的图论刻画[29];Su等人结合自同构给出了等价划分下多智能体系统能控性的技术改进方法[30]。本文基于等价划分研究了多智能体系统能控性的判定问题,并给出了能控性的一种确定方法。在智能体之间信息交换图的基础上,通过分析平凡或(和)非平凡胞腔进入领导者节点集合时的情形,探讨了多智能体系统能控性会发生何种变化,给出了分块矩阵的主子阵的构造方法,并得到了通过选取合适的领航者使得系统能控的方法。文中通过识别领航者使得系统不可控,清楚地给出了使多智能体能控的领航者选择方法,为判定多智能体系统的分布式能控性提供了一个可供借鉴的新方法。

2 问题描述

多智能体系统描述为

(1)

式中N和l分别表示跟从者和领航者的数量,xi表示第i个智能体的状态,i=1,…,N+l。设Ni为vi的邻居集合,即Ni={j|vi～vj;j≠i},且协议定义为

(2)

使xN+1,…,xN+l扮演领航者角色,并将这些智能体重命名为

式中y是所有yi的堆栈向量,z是所有zj的堆栈向量,u是所有uN+j的堆栈向量,j=1,…,l。然后,在式(2)下,跟从者的动态方程为

(3)

式中F为G的拉普拉斯矩阵L删除最后l行和l列后得到的矩阵。R是由被删除列的前N个元素组成的N×l阶子矩阵。

定义1如果系统(3)在控制输入z下是能控的,那么称在领航者xN+j,j=1,…,l和固定拓扑下的多智能体系统(1)是能控的。

多智能体系统分布式能控的几个模型的讨论和最新结果,可参阅[31]和[32]。

3 一种能控性的判定方法

本节研究了信息交换图G的等价划分,当平凡或(和)非平凡胞腔属于领航者节点集合时,系统的能控性会发生什么变化。

胞腔C⊂V是节点集的一个子集。图的划分是指将其节点集分组为不同的胞腔。接下来,回顾一下等价划分的定义。

定义2(等价划分)对于任意的i,j,如果Cj中的每个节点在Ci中都有相同数量的邻居,则称Vg的r-划分π是等价划分,其中π中的胞腔为C1,…,Cr。在这种情况下,Ci中任意节点在Cj中的邻居数用bij表示,且用r=|π|表示划分π的基数。

在文献[15,25]中,提出了利用信息交换图的等价划分来处理多领航者条件下的能控性问题。根据这个概念,下面的结论给出了系统不能控的图理论特征。

引理1[25]给定一个信息交换图G和诱导子图Gf,如果在G和Gf上分别存在非平凡等价划分π和πf,则系统(3)是不能控的,此时π的所有非平凡胞腔都包含在πf中。

结果表明,等价划分是理解多智能体能控性的一个很有效的概念。这促使本文考虑以下问题:给定信息交换图G的一个等价划分π,当领航者来自平凡或(和)非平凡胞腔的一部分时,系统能控性如何?下面给出了两个相关的性质。

设C1,…,Cr表示与等价划分π相关的所有平凡胞腔,其中1≤γ≤r-1,表示为Γi1,…,ij≜Ci1∪…∪Cij,∀i1,…,ij∈{1,…,γ},1≤j≤γ。可以看到Γi1,…,ij是一个节点集,包含C1,…,Cr中任意j个胞腔中的节点。

命题1 如果从Γi1,…,ij中选择任意一个节点作为领航者,则多智能体系统(1)是不能控的。

证明 为了简化命题1,不失一般性,本文假设i1=1,…,ij=j。在这种情况下,领航者从Γi1,…,ij中选择,因此,跟从者子图Gf是由节点集Cj+1,…,Cγ组成的诱导子图。因为C1,…,Cj是同时从原始的信息交换图G中移除的,Gf中的胞腔Cj+1,…,Cγ被保存得很好。因此,Ck中的每个节点在Ck′中都有相同数量的邻居,其中∀k,k′∈{j+1,…,γ}。也就是说,Cj+1,…,Cγ是Gf的一个等价划分。因为C1,…,Cj都是平凡胞腔,所以G和Gf共享胞腔集{Cj+1,…,Cγ}中的所有非平凡胞腔。根据引理1可得,这个系统是不能控的。

注释1命题1表明,当从非平凡胞腔中选择领航者时,多智能体系统是不能控的。

在命题1中,是从Γi1,…,ij的一组平凡胞腔中选择领航者。在后续讨论中,本文考虑领航者也可以从非平凡胞腔中选取的情况。要继续研究,此时需要回忆起两个结果。

引理2[15,25]如果图G有一个非平凡等价划分(NEP)π,所对应的特征矩阵为P,则拉普拉斯矩阵L相似于对角块矩阵

(4)

引理3[15,25]设Gf为跟从者子图,Lf是Gf的拉普拉斯矩阵L的对角子矩阵。如果Gf中有一个非平凡等价划分(NEP)πf,并且G中有一个划分π,这个πf中的所有非平凡胞腔也是π中的胞腔,那么

(5)

式中Tf是上面定义的矩阵。

引理4[15]假设信息交换图G是连通的,当且仅当L和F不共享任何共同的特征值时,多智能体系统是能控的。

对于信息交换图G的一个等价划分π,设C1,…,Cl为非平凡胞腔,Cl+1,…,Cr为平凡胞腔。设{i1,…,ih}是{1,…,l}的任意子集,其中1≤i1≤…≤ih≤l,1≤h≤l-1。并且,{i1,…,ih}中的元素个数最多为l-1个。设{j1,…,js}是{l+1,…,r}的任意子集,其中l+1≤j1≤…≤js≤r,1≤s≤r-l。并且,s的最大值为r-l。在这种情况下,{j1,…,js}的最大集合与{l+1,…,r}重合。这与{i1,…,ih}不同,{i1,…,ih}始终是{1,…,l}的一个子集。对于一个任意的固定索引集{i1,…,ih}和{j1,…,js}。表示为

Xh,s≜(Ci1∪…∪Cih)∪(Cj1∪…∪Cjs)。

接下来陈述以下结果。

定理1 如果节点集Xh,s中所有的智能体都被选为领航者,那么可以构造出引理2和引理3中的正交矩阵T和Tf,使LfQ和LfP分别是LQ和LP的主子矩阵,其中LQ、LfQ、LP和LfP分别为式(4)和(5)中介绍的对角块矩阵。

证明 为了简化陈述,本文对一个特殊的情况进行证明。一般的情况也可以用同样的方式来证明。

假设信息交换图G有一个包含非平凡胞腔C1、C2、C3和平凡胞腔C4、C5、C6的等价划分π。现在,选择胞腔C3和C6中的所有智能体作为领航者。在这种情况下,i1=3,j1=6,X1,1≜Ci1∪Cj1。

跟从者子图Gf由胞腔C1、C2、C4和C5组成。此外,从等价划分的定义可知,C1、C2、C4和C5构成了Gf的一个等价划分πf。

对于等价划分πf={Cf1,Cf2,Cf3,Cf4},其中Cf1=C1,Cf2=C2,Cf3=C4,Cf4=C5,πf的特征矩阵为Pf=[pf1,pf2,pf3,pf4]nf×rf,其中nf代表Gf中的节点个数,rf代表πf中的胞腔个数。基于上述论证,πf中的所有非平凡胞腔也是π中的胞腔,因此,根据引理3,可以构造出一个正交矩阵Tf使式(5)成立。

结合Gf的划分πf,本文将G的等价划分π重新标记为Cl1≜C1,Cl2≜C2,Cl3≜C4,Cl4≜C5,Cl5≜C3,Cl6≜C6,也就是说,G和Gf共同的胞腔C1、C2、C4和C5在π中以更高的优先级重新标记。于是,π的特征矩阵为P=[p1,…,p6]n×r,其中pi对应于Cli,n代表G中的节点数,r代表π中的胞腔数,i=1,…,6。

(6)

这是因为C1,C2都是π和πf的非平凡胞腔。由于p3和p4分别对应于平凡胞腔C4和C5,pf3和pf4也是如此,所以得到

(7)

(8)

(9)

式中1∈Rni-1是每个元素都是1的向量,ni是胞腔Cfi中的节点数。记

式中LQ是引理2中引入的矩阵。根据式(9),

即,LfQ是LQ的一个主子矩阵。

为了证明LfQ是LP的一个主子矩阵,需要重新回顾式(8)。记

既然

由此得出

即,LfP是LP的一个主子矩阵。

例1 下面这个例子被用来验证定理1的证明思路。假设G的等价划分π的胞腔为C1,…,C5,其中C1={v1,v2},C2={v3,v4},C3={v5,v6},C4={v7},C5={v8}。选择胞腔C3={v5,v6}中的节点为领航者。特征矩阵P和Pf分别为

可以看出

由上述矩阵之间的关联,可以看到,定理1成立。

注释2给定G的等价划分π,是否存在一种识别领航者的方法,从而使相关的多智能体系统不是能控的。定理1提出了一种方法来处理这个问题。例如,可以利用定理1来讨论下面推论1中的能控性问题。此外,定理1的证明是构造性的,在证明过程中,蕴含了网络图拓扑结构的划分、领航者的选取和能控性是否成立这三者之间的重要关系,这为将来构造或设计能控或不能控的拓扑结构提供了一个值得借鉴的尝试途径。这也是定理1提出来的方法的一个主要优势。

推论1 当节点集Xh,s中的所有智能体都被选为领航者时,如果G和Gf上分别存在等价划分π和πf,使得π和πf共享所有的非平凡胞腔,则多智能体系统是不能控的。

可得到

然后,再结合式(4)和(5),就意味着,L和Lf有共同的特征值。根据引理4可得,多智能体系统是不能控的。

注释3与引理1不同,推论1清楚地给出了使多智能体能控的领航者选择方法。

4 结论

在本文中,我们主要研究了图划分下的多智能体系统能控性的判定问题。基于等价划分,文中得到了多智能体系统能控性的一种判定方法。在智能体之间信息交换图的基础上,分析了当平凡或(和)非平凡胞腔进入领航者节点集合时,多智能体系统能控性的变化情况。此外,我们还给出了分块矩阵的主子阵的构造方法,进而得到了通过选取合适的领航者使得系统能控的方法。文中通过识别领航者使得系统不可控,清楚地给出了使多智能体能控的领航者选择方法,为判定多智能体系统的分布式能控性提供了一个可供借鉴的新方法。