0 引言

多智能体系统应用广泛, 如多机器人编队系统、智能交通系统、微电网分布式控制与优化调度等^[1-5], 因此围绕多智能体系统的分布式协调控制与决策问题受到越来越多研究者的广泛关注与研究^[6].一致性问题是分布式控制与决策问题中的一个基础研究问题, 其目标是使得一智能群体仅通过各自与自己邻居之间的局部信息交换实现整体系统的一致性.当进一步考虑到多智能体系统代价或成本函数时, 分布式优化问题也得到了广泛的关注.

分布式优化问题的目标是用分布式算法实现系统目标函数的最小化或者最大化, 例如微电网中的优化调度问题、优化投资问题和资源的优化分配问题.系统的目标函数通常是系统中每个智能体的目标函数之和.在多智能体协调算法的启发下, 分布式优化方法得到了广泛的研究和应用^[7-19].分布式优化算法大致可分为两类:连续算法^{[10-11, 16-18]}和离散迭代算法^{[7-9, 12-15]}.文献[19]给出了两种分布式混杂算法以解决无线网络中的优化聚类问题.上述文献中的方法需要智能体连续地或者快速周期性地更新控制并进行相邻节点间的通信.在实际多智能体系统中, 每个智能体通常采用嵌入式数字微控制器, 其能量存储、计算能力和通信能力均有限, 因此高速的运行和通信对实际系统依然是一种挑战.然而, 事件驱动算法可以在很大程度上减少计算负担和通信负担, 并且能有效降低系统的功耗^[20].受文献[20]启发, 文献[21-22]将事件驱动机制应用于求解多智能体一阶系统一致性问题, 有效减少了控制器的更新次数, 然而邻居节点之间仍需连续通信; 文献[23]针对多智能体系统的聚合问题, 利用联合测量方法设计了事件触发条件并有效避免了对邻居状态的连续检测, 进而避免了邻居间的连续通信; 文献[24]提出了一种自适应一致性算法, 并采用事件触发的通信策略有效解决了连续通信的问题.

凸优化问题分布式算法的设计本身就是一个复杂的问题, 现有的成果多是分布式连续算法或者周期迭代离散算法.结合事件驱动方法来设计凸优化问题的分布式事件驱动算法, 既要解决凸优化问题, 又要最大程度地降低控制器输出的更新频率以减少控制器的功耗, 同时还要减少智能体系统对通信网络带宽的要求, 即降低智能体之间的数据通信量.在多个控制目标下, 凸优化问题的分布式事件驱动算法设计相较于分布式连续算法或者周期迭代离散算法的设计更加困难.目前, 基于事件驱动机制的分布式优化算法的相关成果还很有限^[25-27], 文献[25-27]研究了无约束下的优化问题.

受文献[23-24]启发, 本文针对含有等式约束的二次凸优化问题, 给出一种分布式事件驱动算法, 采用李雅普诺夫函数方法设计两种不同的事件触发条件.不同于连续优化算法以及离散迭代算法, 本文的算法可有效地降低控制器的更新次数以及邻居间的通信次数.从理论上证明算法渐近收敛于优化解, 且保证每个智能体相邻事件触发时刻的时间间隔大于0, 不会持续事件触发.

1 预备知识及问题描述 1.1 代数图论

多智能体系统可以由图G=(V, E, A)来描述.其中: V={v₁, v₂, ..., v_n}为智能体节点集合; E∈{V× V}为边的集合, (v_i, v_j)∈ E表示节点j可以接收到节点i的信息; 矩阵A∈ R^{n× n}为图G的邻接矩阵.如果(v_i, v_j)∈ E, 则A的元素a_ij=1, 否则a_ij=0.本文不考虑存在自环的情况, 因此a_ii=0.图的入度矩阵D定义为diag{d₁, d₂, ..., d_n}, 其中.矩阵L=[l_ij]_{n× n}为图G的拉普拉斯矩阵, 它的对角元素为, 非对角元素为l_ij=-a_ij.邻接矩阵A、入度矩阵D与拉普拉斯矩阵L之间满足L=D-A.

对于无向图G, (v_i, v_j)∈ E代表(v_j, v_i)∈ E也成立, 同时a_ij=a_ji=1.因此, 无向图的邻接矩阵A和拉普拉斯矩阵L均为对称矩阵.无向图中, 如果两个不同节点间存在一条路径相连, 则称两个节点是连通的.如果任意两个不同节点均是连通的, 则称图是连通图.如果图G是连通的, 则0是拉普拉斯矩阵L的简单特征根.矩阵L的最大特征根λ_n(L)满足λ_n(L) < 2d_max, 其中d_max=max{d_i, i=1, 2, ..., n}且d_max≤ n-1.

1.2 问题描述与分析

本文研究如下等式约束下的二次凸优化问题:

(1)

(2)

其中: f_i(z_i)为智能体i的成本函数, z_i为智能体i成本函数f_i(z_i)的自变量; 式(2)为等式约束, .

假设1   多智能体系统中, 智能体i仅可获取其自身私有信息f_i(x_i(t))和D_i.

假设2   假设f_i(z_i)为二次凸函数, 即

(3)

其中α_i, β_i, γ_i为智能体i的成本参数且均为正常数.

对于优化问题(1)和(2), 存在很多种传统集中式求解方法.然而, 集中式控制需要一个中央控制器控制整个系统, 同时需要更加复杂的通信网络来获取系统的全局信息.中央控制器一旦出现故障会导致整个系统崩溃, 也不利于系统的扩展.相较于集中式控制, 分布式控制就有较好的可靠性和可扩展性.由于分布式系统中每个智能体都装备了一个控制器, 系统不再需要中央控制器, 使得系统不会因为个别智能体故障影响到整个系统, 具有更好的可靠性; 同时智能体之间只需与邻居间进行局部信息交换就可以实现整体的控制目标, 不再需要系统的全局信息, 因此系统避免了复杂通信网络, 同时也增强了系统的可扩展性.因此, 本文的目标是通过设计分布式事件驱动一致性算法求解优化问题(1)和(2).

基于拉格朗日乘子法可以得到问题(1)和(2)的一个等价解集, 即

(4)

其中η^*为对应于优化解集的正常数.由式(3)可进一步得到

(5)

由式(2)和(5)可得

(6)

对应的优化值z_i^*为

(7)

本文的目标是设计分布式事件驱动算法求解出问题(1)和(2)的优化解z_i^*.

2 主要结果

定义变量x_i(t)和变量ξ_i(t), 其中x_i(t)是对问题(1)和(2)的优化解z_i^*的估计变量, 且满足x_i(0)=D_i.变量ξ_i(t)定义为.由式(5)可得, 当下式成立时, x_i(t)=z_i^*:

(8)

由式(8)可知, 问题(1)和(2)可以转化为关于ξ_i(t)的一致性问题.

2.1 控制算法

对于每个智能体定义一个事件触发函数φ_i(t)，事件触发时刻t_kⁱ(k=1, 2, ...)为φ_i(t)>0对应的时刻.因此, 每个智能体事件触发时刻为一个单调递增的时间点列, 即t₀ⁱ, t₁ⁱ, ..., t_kⁱ, ..., k∈N.

本文设计的优化算法如下:

(9)

(10)

其中: 为当前最新事件触发时刻的状态值, a_ij为多智能体系统通信拓扑图对应邻接矩阵A的元素.

令 式(9)可进一步写成

(11)

2.2 事件触发条件1

设计事件触发函数为

(12)

其中

(13)

(14)

这里ψ_i为待设计的正参数.

事件触发条件为

(15)

智能体i检测事件触发条件(15)是否成立, 若不成立, 则没有进一步动作, 反之智能体i触发事件, 此刻智能体i更新触发时刻状态值并发送给其邻居节点, 同时更新自己的控制律并将e_i(t)设置成0, 智能体i的邻居节点接收到智能体i最新触发时刻状态值并更新自己的控制律.因此, 每个智能体只在自己及其邻居事件触发时刻更新控制律并进行通信.

定理1  假设图G为无向连通图.如果参数ψ_i满足, 则算法(9)和(10)在事件触发条件(15)下可以求解优化问题(1)和(2).

证明   定义变量δ_i(t)=ξ_i(t)-η^*, 构造李雅普诺夫函数

(16)

显然V(t)≥0.当且仅当ξ_i(t)=η^*时V(t)=0.

对V(t)求导可得

(17)

由可得

(18)

进而有

(19)

由于图G为无向连通图, 由L矩阵的对阵性可得

(20)

由式(20)可知, (19)可转化为

(21)

将式(21)写成向量形式

(22)

由式(13)可知, (22)可表示为

(23)

其中e(t)=[e₁(t), e₂(t), ..., e_n(t)]^T.进而可得

(24)

由于, 且有

(25)

其中a为正常数, 可以得到

(26)

选择a=λ_n(L), 可得

(27)

由可得

(28)

当事件触发条件(15)不满足(即φ_i(t)≤0)时, 可得

(29)

将式(29)代入(28), 可得

(30)

其中.当Δ_i>0时, 0.因此当时, ≤0.由拉塞尔不变集原理可以得到当 = 0时, 有

(31)

其中c为未知常数.由式(13)和(31), 可得

(32)

由式(14)和(31)可知

(33)

由式(12)以及条件φ_i(t)≤0可得e_i(t)=0.由式(31)可知, 当时间t→∞时, 有

(34)

由式(9)可得

(35)

对式(35)两边求和可得

(36)

由矩阵L的对称性可得

(37)

由式(36)和(37)可得

(38)

由式(38)可得

(39)

由式(10)可得

(40)

由式(34)和(40)可得

(41)

进一步可得

(42)

由可得

(43)

定理1证明完毕.

注1  由式(39)和可得, 对于任意时间t, 有

(44)

即算法可以保证系统实时满足等式约束.

注2   从上述证明分析过程中可以看出, 本文算法需要利用拉普拉斯矩阵L的对称性, 因此本文算法(9)和(10)仅适用于通信网络为无向连通图的情况.

定理2   假设图G是无向连通图, 对于智能体i(i=1, 2, ..., n), 事件触发条件(15)可以保证其任意两个连续的事件触发时刻t_k+1ⁱ-t_kⁱ>0, 即智能体i不会持续事件触发.

证明   分两种情况进行讨论.

1) 在[t_kⁱ, t_k+1ⁱ)时间内, 智能体i的邻居节点没有事件触发, 即

(45)

恒成立.当t=t_kⁱ时, |e_i(t_kⁱ)|=0.当t=t_k+1ⁱ时, 有

(46)

由式(9)和(13)可得

(47)

当时, 有

(48)

因此有

(49)

即

(50)

当时, 有

(51)

因此, 智能体i不会触发事件.

2) 在[t_kⁱ, t_k+1ⁱ)时间内, 智能体i的邻居节点有事件触发.例如智能体j的事件触发时刻为t_k'^j, 则有

(52)

然后可得

(53)

在第1)种情况下, 智能体i的相邻触发时刻的下界为, 因此第1)种情况下智能体i不可能持续事件触发.要使智能体i持续事件触发只可能在邻居事件触发状态的影响下发生.通过反证法证明在邻居事件触发状态的影响下也不会出现智能体i持续事件触发现象.

假设智能体i受邻居触发状态影响持续事件触发, 触发时刻为t=t_kⁱ(k=0, 1, ...).在触发时刻t=t_kⁱ可能存在两种情形: ⅰ) ω_i(t_kⁱ)=0; ⅱ) ω_i(t_kⁱ)≠ 0.

ⅰ)当ω_i(t_kⁱ)=0时, 可知当t∈[t_kⁱ, t_k+1ⁱ)时, 有, 进而得到.因此.在下一触发时刻t=t_k+1ⁱ, 有, 即与矛盾.

ⅱ)当ω_i(t_kⁱ)≠0时, 可知当t∈[t_kⁱ, t_k+1ⁱ)时, 有, 进而得到.在下一触发时刻t=t_k+1ⁱ, 当时, 有

(54)

为保证式(54)成立, 必存在一个严格正的常数ε_i使得t_k+1ⁱ-t_kⁱ≥ε_i>0.然而, 存在严格正的常数ε_i与假设存在智能体i持续事件触发矛盾.在下一触发时刻t=t_k+1ⁱ, 当ω_i(t_k+1ⁱ)=0时, 即与ω_i(t_kⁱ)=0时的情况一致, 可得出t=t_k+2ⁱ时刻智能体i不会出现智能体i持续事件触发, 因此与假设智能体i持续事件触发矛盾.

综合上述分析, 智能体i(i=1, 2, ..., n)任意两个连续的事件触发时刻t_k+1ⁱ-t_kⁱ>0, 智能体i不会持续事件触发.

注3   由定理1可知, 参数ψ_i的上界与矩阵L的最大特征根λ_n(L)有关.由拉普拉斯矩阵的性质可知λ_n(L)满足λ_n(L)≤ 2d_max≤2(n-1), 因此可以得到.

2.3 事件触发条件2

定义一个新的事件触发函数以避免智能体对全局信息的需要.新的事件触发函数如下:

(55)

其中

(56)

这里ψ'_i为待设计的正参数.

触发条件为

(57)

定理3  假设图G为无向连通图.如果参数ψ'_i满足, 则算法(9)和(10)在事件触发条件(57)下, 可以求解优化问题(1)和(2).

证明   构造与定理1相同的李雅普诺夫函数.由式(24)可得

(58)

其中b为满足b < 1的正常数.进一步可得

(59)

由触发函数(55)和触发条件(57)可得

(60)

其中.当Δ'_i>0时, , 即当时, .

由于0 < b < 1, 容易得到当b=0.5时, b(1-b)取最大值0.25.因此可得

(61)

后续的证明过程类似于定理1的证明过程.

定理4   假设图G是无向连通图.对于智能体i(i=1, 2, ..., n), 事件触发条件(57)可以保证其任意两个连续的事件触发时刻满足t_k+1ⁱ-t_kⁱ>0, 即智能体i不会持续事件触发.

证明  下面同样分两种情况进行讨论.

1) 在[t_kⁱ, t_k+1ⁱ)时间内, 智能体i的邻居节点没有事件触发, 即

(62)

恒成立.当t=t_kⁱ时, |e_i(t_kⁱ)|=0.当t=t_k+1ⁱ时, 有

(63)

由式(62)可得

(64)

由式(9)和(13)可得

(65)

当时, 有

(66)

由式(65)可得

(67)

进一步, 由触发条件(57)可得

(68)

由

(69)

可得

(70)

即

(71)

当时, 有

(72)

(73)

因此, 智能体i不会触发事件.

2) 在[t_kⁱ, t_k+1ⁱ)时间内, 智能体i的邻居节点有触发事件, 例如智能体j事件触发时刻为t_k'^j, 则有

(74)

进而可得

(75)

接下来的证明过程与定理2相同, 此处省略.同样可以得出, 智能体i(i=1, 2, ..., n)任意两个连续的事件触发时刻t_k+1ⁱ-t_kⁱ>0, 智能体i不会持续事件触发.

3 仿真实验

通过Matlab仿真来验证本文算法以及两种事件触发条件的有效性.

考虑由4个智能体组成的多智能体系统, 智能体之间的通信拓扑图如图 1所示.

每个智能体成本函数f_i(z_i)为二次凸函数, 其对应的参数如表 1所示.

令初始值x₁(0)=D₁=130, x₂(0)=D₂=90, x₃(0)=D₃=80, x₄(0)=D₄=100, D= , 则对应的ξ₁(0)=26.18, ξ₂(0)=16.37, ξ₃(0)=19.33, ξ₄(0)=20.42.由式(6)和(7)可知, 对应的优化解ξ₁^*(t)=ξ₂^*(t)=ξ₃^*(t)=ξ₄^*(t)=η^*=20.275 9, x₁^*(t)=z₁^*=99.249 6, x₂^*(t)=z₂^*=117.124 5, x₃^*(t)=z₃^*=84.504 4, x₄^*(t)=z₄^*=99.121 5.

由图 1可知, 系统对应的拉普拉斯矩阵的最大特征根λ_n(L)=4, 由定理1可以得到ψ_i需满足ψ_i < 0.25, 因此设置ψ₁=ψ₂=ψ₃=ψ₄=0.24.仿真结果如图 2 ~图 9所示.

图 2展示了ξ_i(t)的收敛过程, 由图 2可以看出, ξ_i(t)渐近收敛于优化值η^*=20.275 9.

图 3 ~图 6分别展示了|e_i(t)|和w_i(t)的轨迹.以图 3为例, |e₁(t)|一旦大于w₁(t), 立即被置为0, 因此可保证|e₁(t)|≤ w₁(t).

图 7展示了各个智能体的事件触发时刻分布情况, 可以看出各个智能体的事件触发时刻非常稀疏, 同时表明各个智能体控制输入更新次数和通信次数较少.

图 8和图 9分别给出了x_i(t)的收敛曲线以及和的曲线.可以看出, x_i(t)收敛到各自的优化值, 同时等式约束也实时得到了满足.

针对第2种事件触发条件(事件触发条件2), 根据定理3设置参数ψ'₁=ψ'₂=ψ'₃=ψ'₄=0.12.仿真结果如图 10 ~图 17所示.同样可以看出, 算法在该事件触发条件下也同样解决了文中的分布式优化问题.由于空间问题, 在此不再具体说明.

表 2中分别列出了算法(9)和(10)在事件触发条件1和事件触发条件2下的触发次数.

从表 2中可以看出, 在本文仿真示例中, 事件触发条件2的事件驱动性能优于事件触发条件1.需要指出的是, 事件触发条件2的优势是参数的设置不需要系统的全局信息, 即通信拓扑图拉普拉斯矩阵的最大特征根信息.本示例中事件触发条件2的事件驱动性能优于事件触发条件1, 原因是相同的事件触发状态值下, 事件触发条件2中状态测量误差的绝对值|e_i(t)|的上限值ω_i(t)大于其在事件触发条件1中的上限值.通过简单推导可以得出, 在相同的事件触发状态值下, 当 0, i=1, 2, 3, 4时.本仿真示例中d_iψ_i²=0.115 2, ψ'₁=0.12, i=1, 2, 3, 4.

4 结论

本文研究了多智能体系统中含有等式约束的二次凸优化问题, 给出了一种新的分布式事件驱动优化算法, 并针对算法给出了两种不同的事件触发条件, 保证了算法在事件触发条件下实现系统状态渐近收敛到各自对应的优化解.每个智能体只需在其自身及其邻居事件触发时刻更新控制输入并进行邻居间的通信, 因此不再需要连续地或者周期性地更新控制输入和通信, 有效地降低了系统的功耗和通信负担.仿真结果验证了算法和事件触发条件的有效性.在未来的研究中, 将尝试基于分布式事件驱动算法解决同时含有等式、不等式约束的二次凸优化问题以及有向图下的二次凸优化问题.