多智能体系统的二部一致性问题研究
Research on Bipartite Consensus Problems of Multi-Agent Systems

作者: 唐 芳 , 韩摩西 :新疆师范大学数学科学学院,新疆 乌鲁木齐;

关键词: 多智能体系统符号图离散系统规范变换结构平衡二部一致Multi-Agent System Signed Graph Discrete-Time System Gauge Transformation Structural Balance Bipartite Consensus

摘要:
本文针对合作与竞争机制并存的一阶离散时间多智能体系统,应用符号图理论、非负矩阵理论和稳定性理论,通过规范变换,建立了无向拓扑及有向拓扑下一阶离散时间多智能体系统的二部一致性理论。

Abstract: For a first-order discrete-time multi-agent system in which cooperation and competition mechanism coexist, we establish its bipartite consensus theories under undirected and directed topology graph based on graph theory, nonnegative matrix theory and stability theory through gauge transformation.

1. 引言

随着科学技术的进步,自然界中的生物群体活动现象开始受到人们的关注,如飞鸟迁徙、鱼群游动、蚂蚁搬家以及蜜蜂采蜜等等。这启发了人们对生物群体行为的探究。我们把具有简单群集现象的个体称为智能体,把这些群集的生物群体看成多智能体系统。这些生物的群体行为是如何形成的?生物体之间又是如何进行信息的有效传递的呢?基于上述问题,研究人员从人工智能、计算机科学数学以及生物学等多方面开展了对于多智能体系统的研究。

一致性问题是多智能体系统中各智能体相互协同合作的基础,20世纪70年代,美国学者Degroot基于统计学与管理学领域,在文献 [1] 中首次提出了该问题。此后,国内外众多学者针对该问题在文献 [2] [3] [4] [5] [6] 中展开了系统研究。

目前,大量学者在对协同控制技术的研究上取得了优秀成果,智能体间通过协同作用进行通信,最终可达到相同的状态值。然而,在现实的社会网络理论中,智能体之间协作与竞争机制并存,我们将其称为具有拮抗作用的网络系统 [7] [8]。通常用符号图来表示智能体之间的通信状态,与之前的研究不同,符号图中的连接边可以是负边,其对应的邻接矩阵中的元素可正可负可为0。在具有拮抗作用的网络中,研究者们最关注的依然是智能体最终能否趋于共同的状态值,即系统能否取得一致性。研究表明,存在一种另类的“一致”现象:所有的智能体状态值的绝对值会收敛到一个相同的数值,称其为二部一致 [9]。

二部一致的概念由学者Altafini在文献 [9] 中首先提出,该文献研究了存在拮抗作用时,符号图中的智能体怎样通过分布式协议实现一致及其可以达到何种程度的一致之后,众多学者也从各个角度出发,对多智能体系统的二部一致性开展了系统深入的研究。文献 [10] 提出了一种基于事件的具有拮抗作用的多智能体系统的二部一致性问题,利用多智能体网络的符号拉普拉斯矩阵的谱性质,分析了系统的二部一致稳定性。文献 [11] 研究了一般情形下多智能体系统的二部一致性,并给出了利用全局状态信息得到的分布式控制率。文献 [12] 研究了连续时间多智能体系统在符号有向图上的二部一致性问题,并应用现有的反馈和输出一致性算法直接求解二部一致性问题。

现有文献大多是研究连续情形下系统取得二部一致的解的问题。本文基于一阶离散模型,研究了其二部一致性问题,即从连续时间到离散时间的二部一致问题的推广。

2. 预备知识

令三元组 G ( V , ε , A ) 表示(加权)符号图G,其中 V = { v 1 , v 2 , , v n } 为节点集, ε V × V 表示边集, A = [ a i j ] n × n 是与符号图G对应的加权邻接矩阵。将邻接矩阵A对应的符号图记为 G ( A ) ,并约定节点间的通信情况,以信息流方向来表示,即 ( v j , v i ) ε 表示 v j 的信息可以到达 v i ,且相应的邻接矩阵A中对应的元素 a i j 0 ,即 ( v j , v i ) ε a i j 0 N i = { v j | ( v j , v i ) ε } 表示节点 v i 的邻居集合。

在无向图中,节点之间没有顺序,边 ( v j , v i ) ε 表示节点 v i v j 可进行信息交流并且信息流没有方向性。若从顶点 v i v j 有路径,则称 v i v j 是连通的。若图中任意两个点都是连通的,我们把这个图称为连通图。在有向图中,若对每一对顶点 v i v j ,既存在从 v i v j 的路径,又存在从 v j v i 的路径,则称此有向图为强连通图。

在本文中我们不考虑自环,即对任意 i = 1 , 2 , , n a i i = 0 。如果一个环(半环)包含偶数条负边,即 a i 1 , i 2 a i 2 , i 3 a i p , i 1 > 0 ,则此环为正环;若 a i 1 , i 2 a i 2 , i 3 a i p , i 1 < 0 ,则此环为负环。在有向图中,我们把共享相同节点的一对边 ( v i , v j ) , ( v j , v i ) ε ,称为二边形(digon)。对于一个这样的有向图,我们始终假设 a i j a j i 0 ,这说明所有的二边形不能有相反的符号,我们也把它称为二边符号对称(digon sign-symmetry)。 G ( A ) 中的有向路径P是 ε 中的(有向)边的串接, B = { ( v i 1 , v i 2 ) , ( v i 2 , v i 3 ) , , ( v i m 1 , v i m ) } ε ,其中所有节点 v i 1 , v i 2 , , v i m 是不同的,P的长度为 m 1 G ( A ) 中的有向环是指一条具有相同起点和终点的有向路径,即 v i m = v i 1

对于矩阵 M = [ m i j ] n × n ,如果对任意的 i , j = 1 , 2 , , n m i j 0 ,我们称M是一个非负矩阵。若非负矩阵M的行(或列)和是1,则称矩阵M是行(或列)随机矩阵,特别地,我们把既是行随机又是列随机的矩阵称为双随机矩阵。如果以非负矩阵M为邻接矩阵的有向图是强连通的,则M是不可约矩阵。对于一个不可约随机矩阵M,如果M只含有一个具有最大模 ρ ( A ) 的特征值,则M是本原矩阵。

3. 无向拓扑图下的一阶离散系统的二部一致性

考虑一个一阶离散系统

x i ( k + 1 ) = x i ( k ) + u i ( k ) (1)

设计控制协议

u i ( k ) = ε j N i | a i j | ( x i ( k ) sgn ( a i j ) x j ( k ) ) (2)

其中 ε > 0 表示步长, sgn ( ) 表示符号函数, a i j > 0 表示第i个智能体与第j个智能体相互之间存在合作关系, a i j < 0 表示第i个智能体与第j个智能体相互之间存在竞争关系, a i j = 0 表示第i个智能体与第j个智能体之间不存在信息交流。

对于一个给定的带符号(对称)邻接矩阵A, L = [ l i h ] n × n 表示与通信拓扑图 G ( A ) 相对应的Laplacian矩

阵,定义如下: L = C A ,其中 l i h = { j N i | a i j | , h = i a i h , h i C = d i a g { j N 1 | a 1 j | , j N 2 | a 2 j | , , j N n | a n j | }

与一般的一致问题不同,本文中邻接矩阵A中的元素 a i j 可正可负可为0,拉普拉斯矩阵L也不再是行和为零的对角占优矩阵。与非负邻接矩阵的一般理论的主要区别在于此时的L可以是正定的。

为了解决矩阵A不是非负矩阵这一问题,我们引入了规范变换。

定义1 [9] :规范变换(Gauge Transformation):规范变换是n维实数空间 R n 中的一种正序变换,通过矩阵 D = d i a g { σ 1 , σ 2 , , σ n } σ i { ± 1 } , i = 1 , 2 , , n 改变 R n 中矩阵的数值符号,用 D * = { D = d i a g { σ 1 , σ 2 , , σ n } , σ i { ± 1 } } 表示 R n 中所有规范变换的集合。

x ( k + 1 ) = [ x 1 ( k + 1 ) x 2 ( k + 1 ) x n ( k + 1 ) ] T ,则

x ( k + 1 ) = x ( k ) ε L x ( k ) = ( I ε L ) x ( k ) = P ^ x ( k ) (3)

其中 P ^ = I ε L ,I是单位矩阵。

对系统(4),令

z ( k ) = D x ( k ) , D D * (4)

因为 D 1 = D ,所以 x ( k ) = D z ( k ) ,由(3) (4)可得

z ( k + 1 ) = D x ( k + 1 ) = D P ^ x ( k ) = D P ^ D 1 z ( k ) = D ( I ε L ) D 1 z ( k ) = ( I ε D L D 1 ) z ( k ) = ( I ε L D ) z ( k ) = P d z ( k ) (5)

其中 P d = I ε L D ,我们把带有参数 ε 的矩阵 P d 称为Perron阵。 L D = D L D 1 = D L D 是矩阵L在规范变换下对应的新的Laplacian矩阵, L D 中的元素 l D , i h 可表示为:

l D , i h = { j N i | a i j | , h = i σ i σ h a i h , h i (6)

下面给出了结构平衡的定义及其相关等价条件。

定义2 [9] :对于符号图 G ( A ) ,如果存在两个集合 V 1 V 2 ,使得 V 1 V 2 = V 1 V 2 = V ,并且对任意 v i , v j V q , q { 1 , 2 } ,有 a i j 0 ;对任意 v i V q v j V r q r q , r { 1 , 2 } ,有 a i j 0 ,则 G ( A ) 是结构平衡的。

引理1 [9] :连通的符号图 G ( A ) 是结构平衡的当且仅当下列任意一个等价条件成立:

(1) G ( A ) 的所有环是正环;

(2) 存在 D D * ,使得 D A D 是非负矩阵,且在规范变换下得到的新的Laplacian矩阵

L D = [ j N 1 | a 1 j | | a 12 | | a 1 n | | a 21 | j N 2 | a 2 j | | a 2 n | | a n 1 | | a n 2 | j N n | a n j | ] 是行和为零的对角占优矩阵。

(3) 0是L的特征值。

由引理1知,对连通的结构平衡图 G ( A ) 来说,若 ε ( 0 , 1 / Δ ) ,则系统(3)的二部一致性就等价于系统(5)的一致性。

由结构平衡的等价条件,我们有:

推论1 [9] :当且仅当下列任一条件成立时,连通的符号图 G ( A ) 不是结构平衡的:

(1) G ( A ) 有一个或多个环是负的;

(2) 不存在 D D * ,使得 D A D 是非负的;

(3) L的所有特征值大于零,即 ϕ ( x ) > 0

在结构平衡的情形下,经过规范变换后的新的Laplacian矩阵有什么样的性质呢?

定义3 [13] :若有向图 G ( A ) 对应的邻接矩阵A中的元素 a i j 满足对任意 i = 1 , 2 , , n j i a i j = j i a j i ,则 G ( A ) 是一个平衡图。

定义4 [14] :设 A = [ a i j ] n × n ,记 R i = | a i 1 | + | a i 2 | + + | a i , i 1 | + | a i , i + 1 | + + | a i n | ,称圆域

G i = { s | | s a i i | R i , s C } i = 1 , 2 , , n 为矩阵A的第i个Gershgorin圆,并称 R i 为Gershgorin圆的半径。

引理2:设是(强)连通的结构平衡图,表示图的最大入度,如果

Perron矩阵的参数,则矩阵具有如下性质:

(1)是一个非负行随机矩阵,并且有一个平凡特征值1;

(2)的所有特征值均在一个单位圆内;

(3) 若是平衡的,则是一个双随机矩阵;

(4) 若,则是一个本原矩阵。

证明:(1) 因为是(强)连通的结构平衡图,又由引理1可得,是行和为零的对角占优矩阵,且非对角元素均为非正元素,所以的0特征值对应的特征向量,,可得的行和为1且有一个特征值为1,另外:

(7)

由引理1可知,是非负矩阵,又有,因此是非负矩阵。当时,的对角元为,此时是非负的。而两个非负矩阵的和还是非负矩阵,因此是一个非负行随机矩阵。

(2) 令的第j个特征值,则的第j个特征值为。由Gershgorin定理,的所有特征值在圆内,令,则有,即的所有特征值均在一个单位圆内。

(3) 若是一个平衡图,则的左特征向量,即,可得,这说明的列和为1。又由(1)知,是一个非负行随机矩阵,所以是一个双随机矩阵。

(4) 若是强连通的,则是一个不可约矩阵。对任意,令,将圆映射到严格位于单位圆内的圆,其中,这说明在时只有一个模长为1的单特征值,可得是一个本原矩阵。

引理3 [13] :令是一个本原矩阵,其左、右特征向量分别为

满足,则

定义5 [9] :若,系统(1)可取得二部一致。

定理1:若连通的符号图是结构平衡的,则系统(1)在协议(2)下可以获得二部一致的解。此外,

是规范变换中使得非负的矩阵,则系统(1)的二部一致的解为。若不是结构平衡的,则对

证明:若是结构平衡的,则由引理1,存在使得非负且是行和为零的对角占优矩阵。由于符号图是无向连通图,可得分别是的0特征值对应的左特征向量与右特征向量,即,因而。由引理2 (4)可知,是一个本原矩阵,令,则由引理3,有:

(8)

(9)

,得:

(10)

不是结构平衡的,则为严格对角占优矩阵。由引理1 (2)知,此时的所有特征值均在一

个单位圆内,则,可得

4. 有向拓扑图下一阶离散系统的二部一致性

定义6 [9] :给定一个符号图,记为A的行连接矩阵,是A的列连接矩阵。若是无向图,则。一般而

言,若,则符号图是加权平衡的。

对于有向图,记为邻接矩阵A对应的行Laplacian矩阵。若A是二边符号对称的,

则可在无向图下定义一个对称的邻接矩阵。注意,一般与是不同的,这里。当且仅当结构平衡时,有

下面给出了有向图中结构平衡与结构不平衡的相关引理。

引理4 [9] :一个强连通且二边符号对称的有向图是结构平衡的,当且仅当下列等价条件成立:

(1)是结构平衡的;

(2)的所有环是正环;

(3) 存在,使得是非负矩阵;

(4) 0是L的特征值。

引理5 [9] :一个强连通且二边符号对称的有向图不是结构平衡的,当且仅当下列等价条件成立:

(1)不是结构平衡的;

(2)至少有一个负有向环;

(3) 不存在,使得是非负矩阵。

是结构平衡的,令v是的一个非零左特征向量,且满足,结合定理1建立有向拓扑下的二部一致性理论。

定理2:对于强连通且二边符号对称的有向图,设,若是结构平衡的,则系统(1)可以获得二部一致的解。此外,若系统(1)在协议(2)下可达二部一致,则其二部一致的解为

。若是加权平衡的,则。若不是结构平衡的,则对.

证明:由引理4知,是结构平衡的等价于是结构平衡的,对于矩阵与矩阵

,显然对应的符号图是一个无向连通图,则由定理1类似可得,系统(1)可获得二部一致性。引理4 (3)保证了D的存在,由定理1知,,由

,可得:

(11)

是加权平衡的,则,因此A为对称矩阵,此时A对应的符号图是无向图,系统(1)在协议(2)下取得的二部一致的解即为定理1中的结果.若不是结构平衡的,由引理1 (2)知,此

的所有特征值均在一个单位圆内,因此。由,有:.

5. 有向拓扑图下一阶离散系统的二部一致性

本文对合作与竞争机制并存的一阶离散时间多智能体系统,建立了其在无向拓扑及有向拓扑的二部一致性的理论框架。本文的核心思想是对系统进行规范变换,在此变换下会得到一个新的Laplacian矩阵,并经由这个新的Laplacian矩阵的性质来研究系统的一致性问题。未来,我们将研究具有时延或采样的多智能体系统的二部一致性问题。

文章引用: 唐 芳 , 韩摩西 (2019) 多智能体系统的二部一致性问题研究。 应用数学进展, 8, 1745-1752. doi: 10.12677/AAM.2019.811204

参考文献

[1] DeGroot, M.H. (1974) Reaching a Consensus. Journal of the American Statistical Association, 69, 118-121.
https://doi.org/10.1080/01621459.1974.10480137

[2] Li, B., Li, J. and Huang, K.W. (2013) Modeling and Flocking Consensus Analysis for Large-Scale UAV Swarms. Mathematical Problems in Engineering, 2013, Article ID: 368369.
https://doi.org/10.1155/2013/368369

[3] Shi, H., Wang, L. and Chu, T. (2009) Flocking of Multi-Agent Systems with a Dynamic Virtual Leader. International Journal of Control, 82, 43-58.
https://doi.org/10.1080/00207170801983091

[4] Benediktsson, J.A. and Swain, P.H. (1992) Consensus Theoretic Classification Methods. IEEE Transactions on Systems Man & Cybernetics, 22, 688-704.
https://doi.org/10.1109/21.156582

[5] Reynolds, C.W. (1987) Flocks, Herds and Schools: A Distributed Behavioral Model. ACM Siggrapy Computer Graphics, 21, 25-34.
https://doi.org/10.1145/37402.37406

[6] Vicsek, T., Czir, D.K.A., Ben-Jacob, E., et al. (1995) Novel Type of Phase Transition in a System of Self-Driven Particles. Physical Review Letters, 75, 1226-1229.
https://doi.org/10.1103/PhysRevLett.75.1226

[7] Jiang, Y., Zhang, H. and Chen, J. (2016) Sign-Consensus of Linear Multi-Agent Systems over Signed Directed Graphs. IEEE Transactions on Industrial Electronics, 64, 5075-5083.
https://doi.org/10.1109/TIE.2016.2642878

[8] Hu, J. and Zhu, H. (2015) Adaptive Bipartite Consensus on Coopetition Networks. Physica D: Nonlinear Phenomena, 307, 14-21.
https://doi.org/10.1016/j.physd.2015.05.012

[9] Altafini, C. (2012) Consensus Problems on Networks with Antagonistic Interactions. IEEE Transactions on Automatic Control, 58, 935-946.
https://doi.org/10.1109/TAC.2012.2224251

[10] Zhou, Y. and Hu, J. (2013) Event-Based Bipartite Consensus on Signed Networks. IEEE International Conference on Cyber Technology in Automation, Control and Intelligent Systems, Nanjing, 26-29 May 2013, 326-330.
https://doi.org/10.1109/CYBER.2013.6705467

[11] Yang, D., Ren, W., Liu, X., et al. (2016) Decentralized Event-Triggered Consensus for Linear Multi-Agent Systems under General Directed Graphs. Automatica, 69, 242-249.
https://doi.org/10.1016/j.automatica.2016.03.003

[12] Zhang, H. and Chen, J. (2017) Bipartite Consensus of Multi-Agent Systems over Signed Graphs: State Feedback and Output Feedback Control Approaches. International Journal of Robust and Nonlinear Control, 27, 3-14.
https://doi.org/10.1002/rnc.3552

[13] Olfati-Saber, R., Fax, J.A. and Murray, R.M. (2007) Consensus and Cooperation in Networked Multi-Agent Systems. Proceedings of the IEEE, 95, 215-233.
https://doi.org/10.1109/JPROC.2006.887293

[14] Franklin, J.N. (2012) Matrix Theory. Courier Corporation, North Chelmsford.

分享
Top