0 引言

在系统控制领域, 一致性协议是对多个体(智能体)系统实施分布式协调控制的重要协议之一^[1].一致性协议可以实现多个体系统中个体状态(或输出)的分布式同步以及外界控制输入在多个体系统中的有效扩散.如果一个多个体系统中的个体遵循一致性协议, 则称该多个体系统为一致性网络.一致性网络同时受到来自物理学、社会科学和计算机科学等领域学者的广泛关注, 例如振子网络的同步、社会网络的舆论演化和网络上的扩散或传播过程等^[2-3].一致性问题可以追溯到1974年Degroot对社会网络舆论演化的研究^[4].随后, 一致性问题被转化为对随机矩阵无穷次乘积的收敛性问题的讨论^[5].对自然界中鱼群、鸟群等社会性生物的群集现象的建模也是一致性问题重要的研究方向^[6].在此基础上, 由Olfati-Saber提出了群集算法并给出了系统稳定的理论保证^[7].在群集行为模型的基础上, 逐渐催生了多个体系统的编队、覆盖和围堵等分布式控制算法^[8-9].

在针对一致性问题研究的很长一段时间里, 大多假设网络中个体间相互作用的权重由非负实数刻画, 然而很多实际网络拓扑结构中的连边可能出现负权重的情形.连边权重既有正值也有负值的网络被称为符号网络^[10].符号网络中连边权重的正负可以描述例如朋友与敌人、合作与竞争以及吸引与排斥等关系.网络中负权重的存在是有理论意义和应用价值的.例如, 在分布式机器人系统中, 个体间的排斥力是保证避免碰撞的重要手段; 同样的, 振子网络中个体间的排斥力在抑制不利同步现象中发挥着重要作用; 值得注意的是, 在一致性网络中个体间适当地以负权重进行相互作用是实现快速一致性问题的最优解^[11].事实上, 多个体系统中的个体只要遵循满足一定条件的“吸引-排斥”的相互作用协议, 则该系统中个体状态就会呈现出聚集特性, 这一定程度上成为群体系统稳定性的基础^[12].因此, 对符号网络上一致性问题的研究有重要的理论意义和应用价值.

符号网络上的一致性问题近期成为一个研究热点^[13-14].然而, 在网络含有负权重相互作用的情形下, 多个体系统中的个体通过通常的一致性协议相互作用甚至难以保证整个多个体系统的全局稳定性^[15].由于对普通一致性协议在符号网络上演化的稳定性还没有明确的拓扑条件刻画, 此类研究多停留在稳定性保证条件方面^[15-16].为了解决这一问题, Altafini率先提出了一种运行于符号网络上的二分一致性协议, 证明了二分一致性与符号网络的结构平衡性有密切联系^[17].然而, 现有对符号网络上二分一致性问题的研究多考虑的是自治二分一致性网络, 即没有外界输入干预网络中个体状态的演化.在对网络个体一致状态有限制的情形下, 自治二分一致性网络常常无法满足控制需求.与通常的一致性网络的牵制控制不同, 一致性符号网络的牵制控制需要考虑控制输入权重的符号选择.事实上, 即使对于结构平衡的符号网络, 任意选择输入权重的符号也可能无法实现一致性符号网络的有效控制.

鉴于结构平衡, 符号网络中个体可以被分成两簇, 且满足每一簇内部个体间连边为正权重而两簇个体之间连边为负权重.本文在领导-跟随框架下给出通过外界输入控制二分一致性网络的定量理论结果, 即如果外界输入只控制其中一簇的部分个体, 则当外界输入作用为正(负)权重时, 受到外界输入直接影响的一簇个体的状态收敛到外界输入(外界输入的相反数), 另一簇个体状态收敛到外界输入的相反数(外界输入); 如果外界输入以相反的权重符号分别控制两簇中的部分个体, 则由正(负)权重外界输入控制的一簇个体状态收敛到外界输入(外界输入的相反数), 另一簇个体状态收敛到外界输入的相反数(外界输入).本文的主要贡献是为符号网络下二分一致性的牵制控制及其进一步应用提供了理论保证.

1 符号网络上的二分一致性模型

考虑一个含有n∈N个个体的有向网络, 其中和分别表示个体集合与有向连边集合; 网络的邻接矩阵A=[a_ij]∈R^n×n满足a_ij=1当且仅当, 否则a_ij=0.本文仅考虑不含有自环的网络, 即对任意有a_ii=0.记网络中个体的状态为x_i(t)∈R, 则网络整体的状态可以由向量x(t)= [x₁(t), x₂(t), ..., x_n(t)]^T来表示.网络中个体的邻居集合记为, 则表示个体i的邻居数量.称有向边集合为一条有向路且称个体i₁和个体i_p由有向路相连, 其中个体i₁, i₂, ..., i_p ∈两两互不相同.有向网络被称为是强连通的, 如果其中任意两个节点之间都有一条有向路相连.记网络的权重矩阵为W=[w_ij]∈R^n×n, 其中w_ij表示边(i, j)∈ε的权重且满足w_ij\not=0当且仅当(i, j)∈ε.与以往不同的是, 本文中符号网络连边的权重允许为负值, 同时本文假设所讨论的网络都为有向强连通网络.记符号网络的伴随网络满足和; 伴随网络的权重矩阵满足.通常意义下符号网络的拉普拉斯矩阵^[18]记为, 其中

由于网络中连边负权重的存在, 可以定义符号网络的符号拉普拉斯矩阵为, 其中

注意到, 如果网络中所有连边权重为非负实数, 则符号拉普拉斯矩阵与拉普拉斯矩阵是相等的.设多个体系统中个体的状态演化服从如下二分一致性协议

(1)

则多个体系统整体状态演化可以表示为

(2)

其中符号函数sgn(·)满足

为了表述方便, 称式(2)为一致性符号网络.由于本文主要关注的是网络的符号特性, 在接下来的讨论中, 不失一般性地假设个体之间连边的权重值是1或者-1.可以注意到符号网络的拉普拉斯矩阵是不定矩阵, 因此其稳定性无法得到保证; 而符号拉普拉斯矩阵是主对角占优矩阵, 因而是半正定(正定)的.事实上, 符号拉普拉斯矩阵的半正定(正定)与符号网络的结构平衡性有密切联系.

定义1   记的节点集合的一组子集, 其中.如果满足以及, 则称为的一个划分.

定义2^[19]   设符号网络的权重矩阵为, 若存在一个节点集合的二元划分和, 使得对任意两个不同的节点i, j满足:如果, 则有w_ij≥0, 其中k∈ {1, 2};如果且.则有w_ij≤0, 则称是结构平衡的.

下列引理给出了符号网络的结构平衡性与符号拉普拉斯矩阵特征值的关系.

引理1^[17]   符号网络是结构平衡的当且仅当其符号拉普拉斯矩阵有零特征根.

当符号网络的个体遵循二分一致性协议(1)时, 个体状态演化实现二分一致性, 即存在α>0使得

的充分必要条件为是结构平衡的^[17].符号网络的结构平衡性是一个重要的拓扑性质, 最早由社会学领域提出并研究, 在社会网络演化分析方面扮演着重要角色^[20-21].近期, 结合符号网络的结构平衡性质, 二分一致性模型被应用在社会网络中观点动力学演化分析和多智能体系统协同控制^{[16, 22-24]}等领域.对于结构平衡的符号网络, 有如下的Gauge变换联系的符号拉普拉斯矩阵与其伴随网络拉普拉斯矩阵的特征值与特征向量.

定义3 ^[17]   记向量, 其中σ_i∈{1, -1}, i∈{1, 2, ..., n}.称对角矩阵D=diag{σ} ∈R^n×n为Gauge变换.

引理2   如果一个符号网络是结构平衡的, 则存在一个Gauge变换D, 其伴随网络的拉普拉斯矩阵和符号网络的符号拉普拉斯矩阵之间满足.

可以看出, 符号网络的符号拉普拉斯矩阵与其伴随网络的拉普拉斯矩阵是同构的, 因此它们具有相同的特征值.同时, 两者的特征向量可以通过Guage变换进行转换, 这一性质实际上已成为对结构平衡的一致性符号网络进行牵制控制的基础.

2 一致性符号网络的牵制控制

控制多个体系统的群体行为是复杂网络控制的基本问题之一^[25-26].牵制控制被广泛应用于对复杂网络同步行为的控制, 其基本思想是通过控制网络中的部分个体, 利用网络个体动力学行为的相互关联特性实现将全部个体状态调节到设定状态的目的^[27].接下来, 给出利用牵制控制控制一致性符号网络的数学描述.

记外界输入集合为.定义输入矩阵B=[b_il]∈R^n×m满足b_il∈{1, -1}, 当且仅当个体受到输入u_l∈ U的影响.应注意到输入矩阵中的b_il可以为负数.本文假设一致性符号网络中每个个体最多受到一个外部输入的影响.在多个体系统研究中, 受到外界输入直接控制的个体被称作领导个体, 而其余个体被称为跟随个体.因此, 牵制控制问题也常常被称为“领导与跟随”问题^[28].领导个体集合可以记为

跟随个体集合记为.在外界输入的控制下, 一致性符号网络中个体动力学行为可以描述为

(3)

在受控二分一致性协议(3)下, 系统的整体动力学行为可以描述为

(4)

其中.称式(4)为受控二分一致性网络.

对于任意输入向量, 如果对任意i≠ j∈{1, 2, ..., p}满足u_i=u_j, 则称输入为同质的, 否则称输入为异质的.本文假设外界输入为时不变的, 可以将其视为网络中的顽固个体, 其状态满足, 因此有如下动力学方程刻画网络中个体状态的演化:

(5)

其中

下面给出在外界输入的影响下, 二分一致性网络中个体的演化情形.

引理3^[28-29]   设一致性符号网络的拉普拉斯矩阵与符号拉普拉斯矩阵相同, 且, 其中u₀∈R为常数, 则式(5)满足

其中1_n+m∈R^n+m为元素全为1的向量.

首先, 给出一个例子来说明一致性符号网络在同质外界输入情形下的演化情况.在如图 1所示(其中实线表示正权重边, 虚线表示负权重边)的一致性符号网络中, 个体3, 7和8分别受到外界输入u₁=0.5, u₂=0.5和u₃=0.5的影响, 影响权重分别是b₃₁, b₇₂和b₈₃.在外界输入影响权重为b₃₁=-1, b₇₂=1和b₈₃=1时, 网络中个体状态演化轨迹分别如图 2(a)所示; 在外界输入影响权重为b₃₁=1, b₇₂=1和b₈₃=-1时, 网络中个体状态演化轨迹分别如图 2(b)(轨迹上的数字表示个体编号)所示.与只有非负权重的一致性网络不同, 一致性符号网络在上述两种权重选择情形下, 网络中个体状态均未出现个体状态达到一致并收敛到外界输入的情况, 且个体状态演化由于难以定量描述而无法提前预知.

然后, 给出能够实现一致性符号网络二分一致性的外界输入权重符号选择定理.当外界同质输入仅以相同的权重符号控制结构平衡符号网络中的一簇个体时, 其对应二分一致性的演化由如下定理所述.

定理1   设结构平衡的一致性符号网络的节点集合的二元划分为和.设的领导集合中的个体在同质输入u₀∈R的控制下按照协议(3)演化, 其中u₀为常数.记对应领导集合的输入矩阵为, 则有:

1) 如果且对任意满足b_il=1, 则对任意满足, 对任意满足;

2) 如果且对任意满足b_il=-1, 则对任意满足, 对任意满足.

证明   注意到式(4)的解满足

由于符号网络是结构平衡的, 存在一个Gauge变换, 其中σ=[σ₁, σ₂, ..., σ_n]^T∈Rⁿ, σ_i∈{1, -1}, i∈{1, 2, ..., n}, 满足:对于任意有σ_i=1, 对于任意有σ_i=-1;且的符号拉普拉斯矩阵与其伴随网络的拉普拉斯矩阵之间满足.记矩阵A=[a_ij]∈ R^n×n的绝对值为其每个元素的绝对值, 即|A|=[|a_ij|]∈ R^{n× n}.注意到BB^T是对角矩阵, 因此有DBB^TD=BB^T, 故有

因为Gauge变换D满足对任意有σ_i=1, 故DB=B.因此, 若输入矩阵B中非零元素全部为1, 则结合引理3有

类似地, 若输入矩阵B中非零元素全部为-1, 则有

定理1得证.

当外界同质输入以相反的权重符号控制结构平衡符号网络中的两簇个体时, 其对应二分一致性的演化由如下定理所述.

定理2   设结构平衡的一致性符号网络)的节点集合的二元划分为和.设的领导集合中的个体在同质输入u₀∈R的控制下按照协议(3)演化, 其中u₀为常数.记对应领导集合的输入矩阵为.设, 其中, 且, 如果对任意满足b_il=1(b_il=-1)且对任意满足b_il=-1(b_il=1), 则对任意, 对任意满足.

证明   由于式(4)的解满足

且符号网络是结构平衡的, 存在一个Gauge变换D=diag{σ}∈R^n×n, 其中σ=[σ₁, σ₂, ..., σ_n]^T∈Rⁿ, σ_i∈{1, -1}, i∈{1, 2, ..., n}, 满足:对于任意有σ_i=1, 对于任意有σ_i=-1;且的符号拉普拉斯矩阵与其伴随网络的拉普拉斯矩阵之间满足.应注意到BB^T是对角矩阵, 因此DBB^TD=BB^T且有

因为, 其中且, 对任意满足b_il=1以及对任意满足b_il=-1, 故DB=|B|.因此, .反之, 若, 其中且, 且对任意满足b_il=-1以及对任意满足b_il=1, 故DB=-|B|.因此, .

定理1和定理2分别给出了同质输入在两种控制模式(同号权重单簇控制和异号权重两簇控制)下, 一致性符号网络的二分一致性与外界输入的关系.

3 仿真实例

下面通过仿真实例来说明本文的主要结论.考虑如图 3 (实线表示正权重边, 虚线表示负权重边)所示的结构平衡的一致性符号网络, 其中个体3, 7和8分别受到输入u₁=0.5, u₂=0.5和u₃=0.5的影响.外界输入u₁, u₂和u₃的影响权重分别同时为1时(b₃₁=1, b₇₂=1, b₈₃=1), 网络中个体演化轨迹如图 4(a)所示; 外界输入u₁, u₂和u₃的影响权重分别同时为-1时(b₃₁=-1, b₇₂=-1, b₈₃=-1), 网络中个体演化轨迹如图 4(b)所示.

图 3中的符号网络的伴随网络的拉普拉斯矩阵为

对应的符号拉普拉斯矩阵为

由于图 3中的符号网络是结构平衡的, 即存在如下的Guage变换:

使得成立.对应于图 3中控制输入u=[u₁, u₂, u₃]^T的拓扑结构的输入矩阵为

其中: δ₁=δ₂=δ₃, δ_i∈{1, -1}, i∈{1, 2, 3}.

考虑如图 3所示的结构平衡的一致性符号网络, 其中个体2, 7和8分别受到输入u₁=0.5, u₂=0.5和u₃=0.5的影响.外界输入u₁, u₂和u₃的影响权重分别为b₂₁=-1, b₇₂=1, b₈₃=1时, 网络中个体演化轨迹如图 5(a)所示; 外界输入u₁, u₂和u₃的影响权重分别为b₂₁=1, b₇₂=-1, b₈₃=-1时, 网络中个体演化轨迹如图 5(b)所示.

4 结论

本文研究了一致性符号网络在“领导-跟随”框架下, 实现网络中个体跟踪外界输入的输入权重选择规则, 证明了在结构平衡的一致性符号网络中, 由结构平衡性划分的两簇个体的状态在单簇同号权重控制情形和两簇异号权重控制情形下演化的稳态值与输入权重符号的关系.本文的主要结论能够为有效控制一致性符号网络及其进一步的应用提供一定的理论保证.