-
摘要: 随着信息物理系统技术的发展, 面向多智能体系统的分布式协同优化问题得到广泛研究. 主要研究面向多智能体系统的受约束分布式聚合博弈问题, 其中局部智能体成本函数受到全局聚合项约束和全局等式耦合约束. 首先, 面向一阶积分型多智能体系统设计一种基于估计梯度下降的纳什均衡求解算法. 其中, 利用多智能体系统平均一致性方法设计一种自适应估计策略, 以实现全局聚合项约束分布式估计, 并据此计算出梯度函数估计值. 其次, 利用状态反馈策略和输出反馈策略将上述算法推广至状态信息可测和状态信息不可测一般线性异构多智能体系统. 最后, 利用拉萨尔不变性原理证实上述算法收敛性, 并提供多组案例仿真用以验证算法有效性.
-
关键词:
- 聚合博弈 /
- 自适应 /
- 比例积分 /
- 梯度跟踪 /
- 一般线性多智能体系统
Abstract: With the development of cyber-physical system technology, the distributed cooperative optimization problem for multi-agent systems has been widely studied. This study focuses on the distributed constrained aggregative game for multi-agent systems, where the local cost function is subject to the global aggregative and global equality constraints. Firstly, a Nash equilibrium seeking algorithm based on estimation gradient descent is designed for the first-order integrator-based multi-agent systems. To this end, an adaptive estimation scheme is designed using the average consensus method of multi-agent systems to realize the distributed estimation of global aggregative function. Based on this, the estimation gradient function is calculated. Secondly, the above algorithm is extended to the state-accessible and state-inaccessible general heterogeneous linear multi-agent systems using the state and output feedback control scheme, respectively. Finally, the convergence proof is provided using the LaSalle＇s invariance principle and several simulation examples are provided for illustrating the effectiveness of our proposed algorithms. -
聚合博弈广泛存在于各个领域, 例如公共环境[1]、通信网络[2]、追逃问题[3]、智能电网和自主无人系统[4–6]等, 进而得到学术界的深入研究. 自主无人系统依靠大数据、人工智能等科学技术来实现多智能体系统在没有或有限的人工参与下完成协同任务. 在聚合博弈问题中, 每个玩家的成本函数不仅依赖于自身决策行为, 也与所有玩家的聚合决策行为相关, 即每个玩家根据所有玩家决策行为的汇总来优化自身决策行为. 而在实际应用中, 受到网络带宽或供需平衡等因素限制, 玩家的决策行为往往相互耦合. 特别地, 广义纳什均衡是这一大类问题的恰当解.
为寻求上述聚合博弈问题的广义纳什均衡, 学术界和工业界已设计了许多优秀的分布式算法. 例如, 文献[7]对受约束可微聚合博弈问题设计一类同步和异步分布式优化算法, 并利用矩阵收缩理论分析算法的敛散性. 与此同时, 文献[8]利用次梯度下降法解决受约束不可微聚合博弈问题. 为提高算法速度, 文献[9]利用多轮通信策略设计一类分布式算法, 在每次迭代中仅进行固定次数通信. 为提高算法隐私性, 文献[10]利用随机噪声和梯度跟踪技术实现对其他玩家决策行为的安全估计, 并寻求固定或时变网络下聚合博弈问题的广义纳什均衡. 为减少玩家间通信次数, 文献[11]利用事件触发通信机制设计一种时变递减参数的分布式投影算法求解受约束平均聚合博弈问题的广义纳什均衡. 更多类似研究成果亦包括于文献[12–17].
现如今, 随着信息物理系统技术和智能体技术发展, 考虑物理对象动力学特性的分布式策略吸引越来越多学者的关注[18–20]. 针对无约束纳什均衡求解问题, 文献[21]利用多智能体系统一致性方法实现对所有玩家的决策行为进行估计, 在估计信息基础上结合梯度上升法实现玩家自身目标函数最大化. 自适应设计方法旨在自动调整控制参数以使控制系统稳定[22–23]. 基于此, 为简化上述算法控制参数选取, 文献[24]将自适应控制思想引入进来, 分别设计一类基于通信链路和基于玩家的自适应分布式纳什均衡求解算法. 而当玩家控制输入有界时, 文献[25]分别针对一阶和二阶积分型系统设计分布式控制策略寻求纳什均衡解. 为减少玩家间通信频次, 文献[26]设计一类基于动态事件触发通信策略的指数收敛分布式梯度下降法寻求纳什均衡解. 文献[27]将其推广至一般线性异构多智能体系统. 此外, 为确保算法避免Zeno现象发生, 该事件触发控制策略中增加一段停留时间, 进而确保智能体相邻两次触发时间间隔存在最小正下界. 为提高算法收敛速度, 文献[28]利用非周期离散采样技术设计一类预定义时间收敛分布式纳什均衡算法. 针对玩家决策行为受局部约束情形, 文献[29]将广义纳什均衡求解转化为求解满足该问题的KKT (Karush-Kuhn-Tucker)条件, 并利用时间尺度分离方法证实所设计算法可收敛至纳什均衡解的无限小邻域内. 进一步地, 文献[30]研究当所有玩家受到等式约束耦合时的纳什均衡求解问题. 当玩家同时受到局部和全局不等式约束时, 文献[31]针对二阶智能体系统设计一类分布式优化算法, 并将其应用于凸轮发电机系统的电力市场交易问题中.
在上述博弈问题中, 每个玩家的成本函数仅与部分玩家决策行为相关. 而在聚合博弈问题中, 每个玩家的成本函数除与自身决策行为有关外, 也与所有玩家决策行为的聚合项有关[32]. 针对局部约束下的聚合博弈问题, 文献[33]利用梯度跟踪策略设计一种指数收敛的分布式优化算法, 文献[34–36]利用动态平均一致性策略设计一类渐近收敛的分布式优化算法. 针对带耦合不等式约束和局部约束的聚合博弈问题, 文献[37]利用有限时间梯度跟踪技术和映射算子法设计一种分布式连续时间优化算法, 并借助本地数据和邻居玩家信息交互实现广义纳什均衡. 针对带耦合等式约束时, 文献[38]将其转化为变分广义纳什均衡求解问题, 并利用动态平均一致性技术和内模原理实现一阶积分型系统的扰动抑制和变分广义纳什均衡. 文献[39]将文献[38]中线性聚合项推广至非线性聚合项, 并以指数收敛速度实现耦合等式下的广义纳什均衡求解. 文献[40–42]同时考虑耦合等式约束和局部约束下的聚合博弈纳什均衡求解, 并分别利用微分映射算子和映射算子设计分布式优化算法. 此外, 文献[43–45]分别针对一阶非线性扰动智能体、二阶线性扰动智能体和二阶非线性智能体无约束聚合博弈纳什均衡问题设计分布式优化算法. 文献[46]和[47]分别研究欧拉−拉格朗日系统的无约束和等式耦合约束聚合博弈广义纳什均衡.
通过上述讨论可以发现, 现有聚合博弈纳什均衡求解算法主要采用动态平均一致性策略或梯度跟踪策略实现聚合项分布式估计. 然而已有梯度跟踪策略中控制参数为固定常数, 且其收敛范围多与聚合项Lipschitz常数相关, 导致所设计算法适用对象需满足Lipschitz连续, 此外, 现有算法仅关注一阶或二阶积分型动力学特性智能体系统, 而对实际应用中更广的一般线性异构多智能体系统关注较少. 为此, 本文首先利用自适应梯度跟踪策略分布式估计全局聚合项, 避免控制参数对聚合项Lipschitz系数依赖, 扩大算法适用范围. 其次利用估计值计算局部成本函数梯度值. 最后结合拉格朗日乘子法实现受耦合约束聚合博弈问题广义纳什均衡求解, 并将所设计算法推广至一般线性异构多智能体系统. 本文主要创新点总结如下: 1)针对一阶积分型智能体设计一种无初始约束分布式算法. 借助多智能体系统平均一致性策略, 利用自适应梯度跟踪策略对博弈问题全局聚合项进行估计, 无需手动选择控制参数. 2)针对一般线性异构多智能体系统设计一种分布式纳什均衡求解算法, 相比于文献[48], 本文将智能体全局等式约束考虑进来. 此外, 利用状态观测器和输出反馈控制设计一种分布式纳什均衡求解策略.
本文的结构安排如下: 第1节主要介绍网络拓扑和问题描述; 第2节首先针对一阶智能体进行算法设计和收敛性分析, 其次将算法推广至一般线性异构多智能体系统, 最后提供两组数值仿真; 第3节对全文进行总结和展望.
符号说明. 现将后续所需符号及定义说明如下. $ {\bf{R}} $表示实数集. $ {\bf{1}}_n, {\bf{0}}_n, {\boldsymbol{I}}_n $分别表示$ n $维全1、全0向量和单位矩阵. $ \otimes $代表克罗内克积. $ \ln(\cdot) $表示以自然数$ {\rm{e}} $为底的对数函数. $ \text{diag}\{x_1,x_2,\cdots,x_n\} $表示由$ x_1,x_2,\cdots,x_n $构成的对角矩阵或块对角矩阵. $ \text{col}\{x_1,x_2,\cdots,x_n\} $表示由$ x_1,x_2,\cdots,x_n $构成的聚合向量. $ \nabla f(x) $表示函数$ f(x) $的微分. 对于多变量函数$ f(x,y) $, $ \partial f(x,y) $表示其对应的偏微分. $ \sup(\cdot) $表示上界函数. $ \min(\cdot) $表示求最小值. $ \Vert\cdot\Vert $默认是2范数.
1. 基础知识
1.1 图论基础知识
令符号$ {\cal{G}} = ({\cal{V}},{\cal{E}},{\cal{A}}) $表示一个静态无向网络, 其中网络节点集合定义为$ {\cal{V}} = \{1,2,\cdots,n\} $, 网络节点通信链路集合记为$ {\cal{E}} $, 通信链路对应的伴随矩阵记为$ {\cal{A}} = [a_{ij}]\in{\bf{R}}^{n\times n} $. 若通信链路$ (i,j) $属于集合$ {\cal{E}} $, 则称节点$ i $和$ j $是邻居节点, 同时也有$ a_{ij}>0 $; 否则$ a_{ij} = 0 $. 虽然节点可以获取到自身信息, 为分析方便, 本文默认节点不存在自环, 即$ a_{ii} = 0 $. 网络$ {\cal{G}} $的拉普拉斯矩阵 $L=[L_{ij}]\in\bf{R}^{n\times n}$定义为 $L_{ii} = \sum\nolimits_{j = 1}^na_{ij}, \; L_{ij} = -a_{ij}, \; i\not = j,\forall i,j\in{\cal{V}}$. 若网络$ {\cal{G}} $中任一节点都存在邻居节点, 则称网络$ {\cal{G}} $为连通网络. 针对无向连通网络$ {\cal{G}} $, 其对应拉普拉斯矩阵$ L $的特征根从小到大排序记为$0 = \rho_1(L) < \rho_2(L)\le \cdots \le \rho_n(L)$.
假设 1. 在本文所研究的纳什均衡求解问题中, 智能体之间通信网络$ {\cal{G}} $为无向连通图.
引理 1. 若假设1成立, 则存在正交矩阵$Q = [\frac{1}{\sqrt{n}}{\bf{1}}_n,R]\in{\bf{R}}^{n\times n}$, 满足[19]
$$\left\{ \begin{split} &{\bf{0}}_{n\times n}\le\rho_2(L)K_n\le L\\ &R\Lambda_1^{-1}R^{\text{T}}L = LR\Lambda_1^{-1}R^{\text{T}} = K_n \end{split}\right. $$ (1) 其中, 矩阵 $ K_n,\Lambda_1 $ 分别定义为 $K_n = {\boldsymbol{I}}_n-\frac{1}{n}{\bf{1}}_n{\bf{1}}_n^{\text{T}}, \Lambda_1 = \text{diag}\{\rho_2(L),\rho_3(L),\cdots,\rho_n(L)\}$.
1.2 问题描述
假设所研究聚合博弈包含$ n $个玩家, 每个玩家拥有成本函数$ J_i(x_i,x_{-i}):{\bf{R}}^{nm}\to{\bf{R}} $, 其中$ x_i\in{\bf{R}}^m $为玩家$ i $的决策变量, $x_{-i} = \text{col}(x_1,\cdots,x_{i-1},x_{i+1},\cdots, x_n)$. 此外, 所有玩家受到如下耦合等式约束:
$$ X = \left\{x\in{\bf{R}}^{nm}|\sum\limits_{i = 1}^nx_i = \sum\limits_{i = 1}^nd_i\right\} $$ (2) 其中, $x=[x_1^{\rm{T}},x_2^{\rm{T}},\cdots,x_n^{\rm{T}}]^{\rm{T}}\in\mathbf{R}^{nm},$ 常数向量$ d_i\in{\bf{R}}^m $为玩家$ i $的局部资源需求量或供给量. 定义如下聚合函数: $ \sigma(x) = \frac{1}{n}\sum\nolimits_{i = 1}^n\varphi_i(x_i) $, 其中, $\varphi_i(x_i):{\bf{R}}^m\to {\bf{R}}$. 此时成本函数可定义为$ J_i(x_i,x_{-i}) = f_i(x_i,\sigma(x)) $. 虽然成本函数中包含全局信息$ \sigma(x) $, 但是成本函数$ J_i(x_i,x_{-i}) $仅自身可知. 综上所述, 每个玩家$ i $都在求解如下优化问题:
$$ \begin{split} & \min\limits_{x_i} J_i(x_i,x_{-i})\\ &\text{s.t.}\quad\sum\limits_{i = 1}^nx_i = \sum\limits_{i = 1}^nd_i \end{split} $$ (3) 定义 1. 对任意玩家$ i $, 若$ x^* = (x_i^*,x_{-i}^*)\in X $满足如下不等式:
$$ J_i(x_i^*,x_{-i}^*)\le J_i(x_i,x_{-i}^*),\forall x_i,(x_i,x_{-i}^*)\in X $$ (4) 则$ x^* $是聚合博弈(3)的广义纳什均衡.
上述定义表明, 每个玩家的成本函数在纳什均衡点处达到最小, 并且单独改变某个玩家的决策不会使其成本函数降低. 纳什均衡称为所有玩家都接受的解.
假设 2. 对于所有智能体$ i $, 成本函数$ J_i(x_i,x_{-i}) $连续可微. 映射$ F(x) $满足$\mu{\text{-}}$强凸, 其中映射$ F(x) $定义为
$$ \begin{split} F(x) =\;& \text{col}\{\nabla_{x_1} f_1(x_1,\sigma(x)),\cdots,\\ &\nabla_{x_n}f_n(x_n,\sigma(x))\} \end{split} $$ (5) 假设 3. $ g(x,\eta) $是关于变量$ x $满足$\kappa_1{\text{-}}$Lipschitz连续, 关于变量$ \eta $满足$\kappa_2{\text{-}}$Lipschitz连续, 其中
$$ g(x,\eta) = \text{col}\{g_1(x_1,\eta_1),\cdots,g_n(x_n,\eta_n)\} $$ (6) 和
$$ \begin{split} g_i(x_i,\eta_i) =\; &(\nabla_{x_i} f_i(\cdot,\sigma)\;+\\ &\frac{1}{n}\nabla_{\sigma}f_i(x_i,\cdot)^{\text{T}}\nabla\varphi_i)_{\sigma = \eta_i} \end{split} $$ (7) 假设 4. 对任意智能体$ i $, 映射$ \varphi_i(x_i) $可微且满足$\kappa_3{\text{-}}$Lipschitz连续.
注 1. 虽然动态平均一致性策略也可以用于分布式估计聚合博弈纳什均衡问题中聚合项, 但现有文献所设计算法在理论上仅能证明渐近收敛. 而梯度跟踪策略在上述假设条件下能够理论证明指数收敛[49]. 此外, 梯度跟踪策略由于结构简单更易于与基于符号函数的固定时间理论结合实现收敛速率提升. 当采用相同控制参数时, 梯度跟踪策略所设计算法要快于动态平均一致性策略. 这一点在后续案例仿真中得以体现.
注 2. 上述假设是分布式纳什均衡求解算法的基本条件, 在已有文献[9, 32-33, 37-40]中得以利用. 其中, 假设1中连通网络拓扑确保各智能体可通过通信网络将局部信息扩散至整个系统, 以确保所设计算法收敛至全局最优解. 假设2中强凸性确保了问题(3)解的唯一性. Lipschitz连续确保函数$ g(x,\eta) $和$ \sigma(x) $局部变化幅度有限. 假设3和假设4主要体现在算法收敛性分析中, 用以确定控制参数的收敛范围. 此外, 现有文献中基于梯度跟踪策略所设计算法控制参数选取依赖于上述假设中Lipschitz常数. 在分布式系统中, 各智能体仅知道自身的Lipschitz常数. 随着智能体系统规模大肆扩张, 各局部智能体需要更多时间去分布式获取上述全局性参数. 虽然本文亦采用上述假设条件, 但与已有文献不同, 本文所设计算法在控制参数选取时与上述假设条件Lipschitz常数无关. 此外, 在后续算法收敛性分析中证明了变量$ x_i $的有界性, 这进一步扩大了本文所设计算法的适用性, 这一点也在仿真案例部分得到验证.
引理 2. 若假设2成立, 则$x^* = \text{col}\{x_1^*,x_2^*,\cdots, x_n^*\}$是聚合博弈(3)的变分广义纳什均衡当且仅当存在$ \lambda_0\in{\bf{R}}^m $, 使得下式成立[40]:
$$\qquad\qquad\qquad {\bf{0}}_m\in\partial J_i(x_i^*,x_{-i}^*)+\lambda_0 $$ (8a) $$\qquad\qquad\qquad \sum\limits_{i = 1}^nx_i^* = \sum\limits_{i = 1}^nd_i $$ (8b) 2. 主要结果
本节首先针对一阶积分型多智能体系统设计一种分布式纳什均衡求解算法, 其次将其推广至一般线性异构多智能体系统上, 其中分别考虑智能体状态信息可测和不可测两种情形.
2.1 一阶积分型系统
问题(3)求解的关键在于全局等式约束的解耦. 由引理2可知, 可以通过全局对偶拉格朗日乘子$ \lambda_0 $实现全局等式的解耦. 为此, 本文给每个智能体设置一局部拉格朗日乘子. 随后利用多智能体系统一致性控制策略使得所有局部对偶变量$ \lambda_i $协同收敛至最优拉格朗日乘子. 具体地, 智能体$i,\forall i\in\mathcal{V} $按如下规则对自身信息进行更新:
$$ \dot{x}_i = -g_i(x_i,\eta_i)-\lambda_i $$ (9a) $$ \dot{\lambda}_i = x_i-d_i-\beta\sum\limits_{j = 1}^na_{ij}(\lambda_i-\lambda_j)-\theta z_i $$ (9b) $$ \dot{z}_i = \beta\sum\limits_{j = 1}^na_{ij}(\lambda_i-\lambda_j) $$ (9c) $$ \dot{s}_i = \sum\limits_{j = 1}^na_{ij}\alpha_{ij}(\eta_j-\eta_i) $$ (9d) $$ \eta_i = s_i+\varphi_i(x_i) $$ (9e) $$\dot{\alpha}_{ij}= \gamma_{ij}a_{ij}\Vert\eta_i-\eta_j\Vert^2 $$ (9f) 其中, 控制参数$ \beta,\theta,\gamma_{ij} = \gamma_{ji},\forall i,j\in{\cal{V}} $大于零. 算法(9)可分为以下3个部分:
1) 在式(9b)和式(9c)中, 通过增加辅助变量$ z_i\in{\bf{R}}^m $记录对偶变量 $ \lambda_i $的历史差值信息, 并与$ \sum\nolimits_{j = 1}^na_{ij}(\lambda_i-\lambda_j) $一起实现对 $ \lambda_i $的比例积分控制. 此外, 不同于传统梯度下降法中的时变递减参数, $ z_i $的存在也使得对偶变量$ \lambda_i $的梯度项$ x_i-d_i $控制系数为常数. 对偶变量$ \lambda_i $用于驱动智能体趋向于广义纳什均衡, 且$ \lambda_i $最终收敛至引理1中的最优解$ \lambda_0 $.
2) 在问题(3)中, 局部智能体成本函数$ f_i(x_i,\sigma(x)) $中聚合项$ \sigma(x) $都与所有智能体信息相关. 然而在分布式通信网络中, 无法保证网络的全联通. 因此在算法(9d) ~ (9f)中$ \eta_i $利用多智能体系统平均一致性算法实现聚合项的分布式预测, 辅助变量$s_i $用于平衡全局平均聚合项$\frac{1}{n}\sum_{i=1}^n\phi_i(x_i) $和局部函数$\phi_i(x_i) $. 为方便理解, 将算法(9d) ~ (9f)修改为
$$ \begin{split} \dot{\eta}_i=\;& \sum\limits_{j = 1}^na_{ij}\alpha_{ij}(\eta_j-\eta_i)+\frac{\text{d}}{\text{d}t}\varphi_i(x_i) = \\ &\sum\limits_{j = 1}^na_{ij}\alpha_{ij}(\eta_j-\eta_i)+(\nabla \varphi_i(x_i))^{\text{T}}\dot{x}_i \end{split} $$ (10) 式(10)即为平均一致性跟踪策略. 当变量$ \eta_i $一致时, 即有$\eta_i = \frac{1}{n}\sum\nolimits_{i = 1}^n\varphi_i(x_i) = \sigma(x)$.
3) 在式(9a)中, 利用估计值$ \eta_i $计算局部成本函数梯度值$ g_i(x_i,\eta_i) $替代式(8a)中$ \partial J_i(x_i,x_{-i}) $, 最后结合式(8a)构建式(9a).
此外, 为书写方便, 在算法(9)以及后文中省略时间变量$ t $.
注 3. 在算法(9)中, 为实现智能体对全局聚合项$ \sigma(x) $的获取, 现有算法主要分为两大类: 平均一致性方法[38, 40, 43-48]和梯度跟踪方法[32-33, 37, 39, 41-42]. 与已有文献类似, 本文同样采用多智能体系统梯度跟踪方法实现全局聚合项预测. 此外, 已有文献多采用固定控制参数$ \alpha $. 这就导致$ \alpha $的收敛范围过于苛刻. 例如文献[32]中$ \alpha $需要满足
$$ \alpha>\frac{\kappa_2\kappa_3+\frac{(\kappa_2+\kappa_3\kappa_1)^2}{2\mu}}{\rho_2(L)} $$ (11) 文献[33]中, $ \alpha $需要满足
$$ \alpha>\frac{2\kappa_2\kappa_3}{\mu\rho_2(L)} $$ (12) 文献[37]中, $ \alpha $需要满足
$$ \alpha>(n-1)\max\limits_i\sup\limits_{t\to\infty}\Vert\dot{\varphi}_i(t)\Vert $$ (13) 以上述现有算法架构为基础, 算法(9)采用自适应通信权重, 从而避免在算法执行时参数选取困难问题.
定理 1. 若假设1 ~ 4成立, 则算法(9)收敛至问题(3)最优解, 且控制参数收敛范围为$\beta > {1}/{2},$ $\theta > {1}/({2\mu})$.
证明. 令$\lambda=[\lambda_1^{\rm{T}},\;\lambda_2^{\rm{T}},\;\cdots, \;\lambda_n^{\rm{T}}]^{\rm{T}},\;z=[z_1^{\rm{T}},\; z_2^{\rm{T}},\; \cdots, \; z_n^{\rm{T}}]^{\rm{T}}, \eta=[\eta_1, \eta_2,\cdots,\eta_n]^{\rm{T}}$, $(x^*,\lambda^*,z^*,\eta^*) $表示系统(9)的稳定点. 由引理2和文献[40]中引理6可知, $x^* $为问题(3)最优解. 令李雅普诺夫函数为
$$ \begin{split} V_1=\;& \Vert x-x^*\Vert^2+\frac{1}{2}\Vert\lambda-\lambda^*+z-z^*\Vert^2\;+\\ &\frac{1}{2}\Vert\lambda-\lambda^*\Vert^2\;+\\ &\frac{\theta}{\beta}(z-z^*)^{\text{T}}((R\Lambda_1^{-1}R^{\text{T}})\otimes{\boldsymbol{I}}_m)(z-z^*) \end{split} $$ (14) 则函数$ V_1 $在系统(9)上关于时间$ t $的微分为
$$ \begin{split} \dot{V}_1 =\; &-2(x-x^*)^{\text{T}}(g(x,\sigma(x))-g(x^*,\sigma(x^*)))\;-\\ &2(x-x^*)^{\text{T}}(\lambda-\lambda^*)-\theta\Vert z-z^*\Vert^2\;+\\ &2(x-x^*)^{\text{T}}(\lambda-\lambda^*)-2\theta(z-z^*)^{\text{T}}(\lambda-\lambda^*)\;-\\ &\beta(\lambda-\lambda^*)^{\text{T}}(L\otimes {\boldsymbol{I}}_m)(\lambda-\lambda^*)\;+\\ &(x-x^*)^{\text{T}}(z-z^*)-2\theta(z-z^*)^{\text{T}}(\lambda-\lambda^*)\;+\\ &2\theta(z-z^*)^{\text{T}}(\lambda-\lambda^*)\;-\\ &2(x-x^*)^{\text{T}}(g(x,\eta)-g(x,\sigma(x)))\le\\ &-2\mu\Vert x-x^*\Vert^2+2\kappa_2\Vert x-x^*\Vert\cdot\Vert e\Vert\;-\\ &\beta(\lambda-\lambda^*)^{\text{T}}(L\otimes {\boldsymbol{I}}_m)(\lambda-\lambda^*)\;-\\ &\theta\Vert z-z^*\Vert^2+(x-x^*)^{\text{T}}(z-z^*) \\[-10pt]\end{split} $$ (15) 其中, $ e = \eta-{\bf{1}}_n\otimes \sigma(x) $. 在上述分析过程中用到假设2中映射$ F(x) $强凸性和假设3中Lipschitz连续条件. 令$ V_2 $定义如下:
$$ V_2 = \frac{1}{2}\Vert e\Vert^2+\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n\frac{1}{2\gamma_{ij}}(\alpha_{ij}-\varrho)^2 $$ (16) 其中, 常数$ \varrho $满足
$$ \varrho\lambda_2(L)> \kappa_2\kappa_3+\frac{2\kappa_2+\kappa_3(\kappa_2\kappa_3 +\kappa_1)+\mu\kappa_3^2}{2\mu} $$ (17) 则函数$ V_2 $在系统(9)上关于时间$ t $的微分为
$$ \begin{split} \dot{V}_2 =\; &-e^{\text{T}}(L_{\alpha})e+e^{\text{T}}\zeta(x,e)\;+\\ &\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n(\alpha_{ij}-\varrho)a_{ij}\Vert\eta_i-\eta_j\Vert^2\le\\ &-\varrho\lambda_2(L)\Vert e\Vert^2+e^{\text{T}}\zeta(x,e) \end{split} $$ (18) 其中, $ \zeta(x,e) = \frac{\text{d}}{\text{d}t}(\varphi(x)-{\bf{1}}_n\otimes\sigma(x)) $. 拉普拉斯矩阵 $ L_{\alpha} $ 定义为 $L_{\alpha,ii} = \sum\nolimits_{j = 1}^na_{ij}\alpha_{ij},\forall i\in{\cal{V}}$和$L_{\alpha,ij} = -a_{ij}\alpha_{ij}, \forall i\not = j.$ 此外有
$$ \begin{split} \Vert\zeta(x,e)\Vert\le\;&\kappa_3\Vert g(x,\eta)+\lambda\Vert = \\ &\kappa_3\Vert g(x,\eta) -g(x^*,\eta^*)+\lambda -\lambda^*\Vert\le\\ &\kappa_3\Vert\lambda-\lambda^*\Vert+\kappa_3\Vert g(x,\eta)\;-\\ &g(x,\eta^*)+g(x,\eta^*)-g(x^*,\eta^*)\Vert\le\\ &\kappa_3\Vert\lambda-\lambda^*\Vert+\kappa_3\kappa_1\Vert x-x^*\Vert\;+\\ &\kappa_3\kappa_2\Vert\eta-{\bf{1}}_n\otimes\sigma(x)\;+\\ &{\bf{1}}_n\otimes\sigma(x)-{\bf{1}}_n\otimes\sigma(x^*)\Vert\le\\ &\kappa_3\Vert\lambda-\lambda^*\Vert+\kappa_2\kappa_3\Vert e\Vert\;+\\ &\kappa_3(\kappa_2\kappa_3+\kappa_1)\Vert x-x^*\Vert \end{split} $$ (19) 令$ V = V_1+V_2 $, 将式(19)代入式(18), 则有
$$ \begin{split} \dot{V}\le\;&-\mu\Vert x-x^*\Vert^2\;-\\ &(\beta-\frac{1}{2})\lambda_2(L)\Vert\lambda-\lambda^*\Vert^2\;-\\ &(\theta-\frac{1}{2\mu})\Vert z-z^*\Vert^2\;-\\ &(\varrho\lambda_2(L)-\kappa_2\kappa_3\;-\\ &\frac{2\kappa_2+\kappa_3(\kappa_2\kappa_3+\kappa_1)+\mu\kappa_3^2}{2\mu})\Vert e\Vert^2 \end{split} $$ (20) 在上式分析过程中, 基于Young不等式, 用到以下不等式:
$$ \begin{split} &\kappa_3 e^{\text{T}}(\lambda-\lambda^*)\le\frac{\rho_2(L)}{2}\Vert \lambda-\lambda^*\Vert^2+\frac{\kappa_3^2}{2\rho_2(L)}\Vert e\Vert^2\\ &(2\kappa_2+\kappa_2\kappa_3^2+\kappa_1\kappa_3)e^{\text{T}}(x-x^*)\le \\ &\;\;\;\;\frac{\mu}{2}\Vert x-x^*\Vert^2+\frac{(2\kappa_2+\kappa_2\kappa_3^2+\kappa_1\kappa_3)^2}{2\mu}\Vert e\Vert^2\\ &(x-x^*)^{\text{T}}(z-z^*)\le\frac{\mu}{2}\Vert x-x^*\Vert^2+\frac{1}{2\mu}\Vert z-z^*\Vert^2 \end{split} $$ (21) 不难发现, 李雅普诺夫函数$ V $关于变量$\text{col}\{x-x^*, \lambda-\lambda^*,z-z^*,e\}$和$ \alpha_{ij} $径向无界. 从式(20)可以看出, 上述变量均有界. 注意到变量$ \alpha_{ij} $单调非减, 所以其极限$ \lim_{t\to\infty}\alpha_{ij} $存在. 从而基于拉萨尔不变性原理可知, $ \lim_{t\to\infty}x = x^* $.
□ 2.2 一般线性系统
在算法(9)中, 我们将智能体$ i $视作一阶积分型系统. 而在实际应用中, 高阶系统较为普遍. 因此, 本文考虑如下一般线性异构多智能体系统:
$$ \left\{\begin{split} &\dot{x}_i = A_ix_i+B_iu_i\\ &y_i = C_ix_i \end{split}\right. $$ (22) 其中, $ x_i \in{\bf{R}}^{n_i},u_i \in{\bf{R}}^{p_i},y_i \in{\bf{R}}^{q} $分别是智能体$ i $ 的状态、输入和输出变量. $A_i\in{\bf{R}}^{n_i\times n_i}, B_i\in{\bf{R}}^{n_i\times p_i}, C_i\in {\bf{R}}^{q\times n_i}$分别表示状态、输入和输出矩阵. 本文旨在利用各智能体间信息交互设计控制器$ u_i $使得输出变量$ y_i $收敛至资源分配问题(3)的纳什均衡点. 同时可以看出, 算法(9)为智能体状态最优控制问题, 而系统(22)则为最优输出控制问题. 为此下面的假设条件是必要的.
假设 5. $ (A_i,B_i) $可控, 且矩阵$ B_i,C_i $满足秩约束$ \text{rank}(C_iB_i) = q,\forall i\in{\cal{V}} $.
引理 3. 若假设5成立, 则下述方程解$ (K_{1i},K_{2i}) $存在[49]:
$$ C_iB_iK_{1i} = C_iA_i,\quad C_iB_iK_{2i} = {\boldsymbol{I}}_q $$ (23) 基于引理3, 系统(22)中的控制器$ u_i $设计如下:
$$ u_i = -K_{1i}x_i-K_{2i}(g_i(y_i,\eta_i)+\lambda_i) $$ (24a) $$ \dot{\lambda}_i = y_i-d_i-\beta\sum\limits_{j = 1}^na_{ij}(\lambda_i-\lambda_j)-\theta z_i $$ (24b) $$\dot{z}_i = \beta\sum\limits_{j = 1}^na_{ij}(\lambda_i-\lambda_j) $$ (24c) $$ \dot{s}_i = \sum\limits_{j = 1}^na_{ij}\alpha_{ij}(\eta_j-\eta_i) $$ (24d) $$ \eta_i= s_i+\varphi_i(y_i) $$ (24e) $$ \dot{\alpha}_{ij} = \gamma_{ij}a_{ij}\Vert\eta_i-\eta_j\Vert^2 $$ (24f) 其中, 算法(24)中变量$\lambda_i,z_i,s_i,\eta_i,\alpha_{ij}$与算法(9)定义相同, 控制参数$ \theta,\beta,\gamma_{ij} = \gamma_{ji},\forall i\in{\cal{V}} $大于零. 在算法(24)中, 控制策略$ u_i $除了包含梯度项$g_i(y_i, \eta_i)$和对偶变量$ \lambda_i $之外, 还存在项$ -K_{1i}x $, 从后续分析中可以看出该项主要目的是抵消系统状态式(22)中项$ A_ix_i $. 而辅助反馈矩阵$ K_{2i} $更有助于后续的算法收敛性分析.
注 4. 文献[48]利用多智能体系统平均一致性对一般线性多智能体系统的无约束聚合博弈纳什均衡问题设计分布式算法. 此外, 为保证算法收敛, 文献[48]中存在一正实数$ \epsilon $使得$ [g(y,\eta),\epsilon(\eta-\varphi(y))]^{\text{T}} $满足强单调性和Lipschitz连续性, 然而并未给出参数$ \epsilon $的选取范围. 与之相比, 本文将全局等式约束考虑进来, 算法(24)中参数收敛范围在定理2中给出.
定理 2. 若假设1 ~ 5成立, 则算法(24)收敛至问题(3)最优解, 且控制参数收敛范围为$\beta > {1}/{2},$ $\theta > {1}/({2\mu} )$.
证明. 首先对输出变量$ y_i $求微分, 并结合引理3, 可知
$$ \begin{split} \dot{y}_i = \;&C_i\dot{x}_i = C_i(A_ix_i+B_iu_i) = \\ &-g_i(y_i,\eta_i)-\lambda_i \end{split} $$ (25) 此时可发现, 当选择满足引理3的反馈矩阵$ K_{1i},K_{2i} $, 算法(24)与算法(9)本质一样. 因而从定理1可知算法(24)与算法(9)具有相同的收敛性结果. 故后续证明可参考定理1, 在此予以省略.
□ 为抵消智能体状态方程中$ A_ix_i $对系统的影响, 在算法(24)中引入状态反馈项$ -K_{1i}x_i $. 但在部分系统中, 智能体状态信息$ x_i $不可测. 此时上述反馈项失效. 而为解决智能体状态信息不可测情形下问题(3)纳什均衡求解, 基于Luenberge状态观测技术, 本文设计一种基于输出反馈的分布式纳什均衡算法. 对任意智能体$ i $, 其状态更新规则修改如下:
$$ u_i = -K_{1i}\hat{x}_i-K_{2i}(g_i(y_i,\eta_i)+\lambda_i) $$ (26a) $$ \dot{\hat{x}}_i = A_i\hat{x}_i+B_iu_i+F_i(y_i-C_i\hat{x}_i)\,$$ (26b) $$ \dot{\lambda}_i= y_i-d_i-\beta\sum\limits_{j = 1}^na_{ij}(\lambda_i-\lambda_j)-\theta z_i $$ (26c) $$ \dot{z}_i = \beta\sum\limits_{j = 1}^na_{ij}(\lambda_i-\lambda_j) $$ (26d) $$ \dot{s}_i = \sum\limits_{j = 1}^na_{ij}\alpha_{ij}(\eta_j-\eta_i) $$ (26e) $$ \eta_i = s_i+\varphi_i(y_i) $$ (26f) $$ \dot{\alpha}_{ij} = \gamma_{ij}a_{ij}\Vert\eta_i-\eta_j\Vert^2 $$ (26g) 其中, 算法(26)中变量$\lambda_i,z_i,s_i,\eta_i,\alpha_{ij}$与算法(9)定义相同, 变量$ \hat{x}_i $用于估计智能体真实状态信息$ x_i $. 同时反馈矩阵$ F_i $使得$ A_i-F_iC_i $是Hurwitz稳定的. 而为确保智能体状态信息可重构, 系统(22)需满足如下假设.
假设 6. $ (A_i,B_i) $可控, $ (A_i,C_i) $可观测, 且矩阵$ B_i,C_i $满足秩约束$ \text{rank}(C_iB_i) = q,\forall i = 1,2,\cdots,n $.
算法(26)收敛性分析如定理3所示.
定理 3. 若假设1 ~ 4和假设6成立, 则算法(26)收敛至问题(3)最优解, 且控制参数收敛范围为$ \beta>{1}/{2}, \theta>{1}/({2\mu}) $.
证明. 令$ e_{x,i} = x_i-\hat{x}_i $, 结合算法(26)可得
$$ \dot{e}_{x,i} = \dot{x}_i-\dot{\hat{x}}_i = (A_i-F_iC_i)e_{x,i} $$ (27) 由于$ A_i-F_iC_i $是Hurwitz稳定的, 所以存在正定矩阵$ P $, 使得 $(A-FC)^{ \text{T}}P+P(A-FC) = -(1+ \frac{\Vert CA\Vert^2}{2}+\frac{\Vert CA\Vert^2}{2\mu}){\boldsymbol{I}}_{N},N = \sum\nolimits_{i = 1}^nn$, $A,B,C $分别表示由所有智能体中$A_i,B_i,C_i $构成的块对角矩阵. 令李雅普诺夫函数$V_3=2e_x^{\text{T}}Pe_x$, 则函数$ V_3 $对时间$ t $的微分为
$$ \dot{V}_3 = -\left(1+\frac{\Vert CA\Vert^2}{2}+\frac{\Vert CA\Vert^2}{2\mu}\right)\Vert e_x\Vert^2 $$ (28) 与定理2类似, 对输出变量$ y_i $求微分, 并结合引理3, 可知
$$ \begin{split} \dot{y}_i = C_iA_ie_{x,i}-g_i(y_i,\eta_i)-\lambda_i \end{split} $$ (29) 此时, 定理1函数$ V_2 $不变. 令$\lambda,z,e $与定理1中定义一致, $y^*,x^*,\lambda^*,z^* $分别表示系统(26)的稳定点. 由引理2和文献[40]中引理6可知$y^* $为问题(3)最优解. 将定理1中$ V_1 $修改为
$$ \begin{split} V_1=\;& \Vert y-y^*\Vert^2+\frac{1}{2}\Vert\lambda-\lambda^*+z-z^*\Vert^2\;+\\ &\frac{1}{2}\Vert\lambda-\lambda^*\Vert^2\;+\\ &\frac{\theta}{\beta}(z-z^*)^{\text{T}}((R\Lambda_1^{-1}R^{\text{T}})\otimes {\boldsymbol{I}}_m)(z-z^*) \end{split} $$ (30) 则函数$ V_1+V_2 $在系统(26)上关于时间$ t $的微分为
$$ \begin{split} \dot{V}_1+\dot{V}_2\le\;&-\frac{\mu}{2}\Vert y-y^*\Vert^2\;-\\ &(\beta-\frac{1}{2})\lambda_2(L)\Vert\lambda-\lambda^*\Vert^2\;-\\ &(\theta-\frac{1}{2\mu})\Vert z-z^*\Vert^2\;-\\ &(\varrho\lambda_2(L)-\kappa_2\kappa_3-\frac{\Vert CA\Vert^2+\kappa_3^2}{2}\;-\\ &\frac{2\kappa_2+\kappa_3(\kappa_2\kappa_3+\kappa_1)}{2\mu})\Vert e\Vert^2 \end{split} $$ (31) 其中, 利用了以下不等式结论:
$$ \left\{\begin{split} &(y-y^*)^{\text{T}}CAe_x\le\frac{\mu}{2}\Vert y-y^*\Vert^2+\frac{\Vert CA\Vert^2}{2\mu}\Vert e_x\Vert^2\\ &e^{\text{T}}CAe_x\le\frac{1}{2}\Vert e\Vert^2+\frac{\Vert CA\Vert^2}{2}\Vert e_x\Vert^2 \end{split} \right.$$ (32) 令李雅普诺夫函数为$ V = V_1+V_2+V_3 $, 则函数$ V $在系统(26)上关于时间$ t $的微分为
$$ \begin{split} \dot{V}\le\;&-\frac{\mu}{2}\Vert y-y^*\Vert^2\;-\\ &(\beta-\frac{1}{2})\lambda_2(L)\Vert\lambda-\lambda^*\Vert^2\;-\\ &(\theta-\frac{1}{2\mu})\Vert z-z^*\Vert^2-\Vert e_x\Vert^2\;-\\ &(\varrho\lambda_2(L)-\kappa_2\kappa_3-\frac{\Vert CA\Vert^2+\kappa_3^2}{2}\;-\\ &\frac{2\kappa_2+\kappa_3(\kappa_2\kappa_3+\kappa_1)}{2\mu})\Vert e\Vert^2 \end{split} $$ (33) 从式(33)可以看出, 算法(26)中系统观测值可精确跟踪系统实际值, 从而表明所设计观测器(26b)可以对不可测状态信息实现精确估计. 与定理1类似, 可证明算法(26)能够实现系统(22)对聚合博弈问题(3)的纳什均衡解分布式获取.
□ 注 5. 本文将第2.1节所设计算法推广至一般线性系统. 此外, 借助状态观测器, 可将第2.1节所设计算法推广至非线性系统. 例如针对如下二阶非线性系统:
$$ \left\{\begin{split} \dot{x}_i& = v_i\\ v_i& = h_i(x_i,v_i)+u_i,\forall i\in{\cal{V}} \end{split} \right.$$ (34) 其中, $x_i,v_i $分别表示智能体$i $ 位置量和速度量, $ h_i(x_i, v_i) $为智能体$ i $的非线性项. 此时, 控制器$u_i, \forall i\in{\cal{V}}$设计如下:
$$ \left\{\begin{split} u_i& = -kv_i-g_i(x_i,\eta_i)-\lambda_i+\xi_i\\ \dot{\xi}_i& = -kv_i-g_i(x_i,\eta_i)-\lambda_i \end{split}\right. $$ (35) 其中, $ \xi_i $为智能体$ i $的观测变量, 用于抵消智能体动力学特性中的非线性项$ h_i(x_i,v_i) $. 与本文线性系统相比, 非线性系统收敛性分析较难, 可结合本文分析方法及文献[50-51]进行分析.
2.3 一阶积分型系统案例仿真
首先考虑一环形通信网络构成的五节点(电力消费者)资源需求管理问题[38]. 每个消费者采用如下成本函数: $ J_i(x_i,x_{-i}) = (x_i-x_{i0})^2+p(\sigma)x_i $, 其中$ x_i $为电力消费量, $ x_{i0} $为电力消费的额定值, $p(\sigma) = p_0+an\sigma$是带有聚合项$ \sigma = \frac{1}{n}\sum\nolimits_{i = 1}^nx_i $的电力价格. 设定参数为$n = 5,a = 0.04,p_0 = 5, x_0 = [50, 55,60, 65,70]^{\text{T}}$. 此外局部期望生产电力为$d = [80, 90,70, 85,60]^{\text{T}}$. 令初始值为$ x(0) = [50,55,60,65,70]^{\text{T}} $, 其他变量初始值设定为零, 控制参数设定为$ \beta = \theta = \gamma_{ij} = \gamma_{ji} = 1,\forall i,j\in{\cal{V}} $, 则算法(9)的运行轨迹如图1和图2所示. 从图1可以看出, 本文所设计算法能够收敛至最优纳什均衡点$x^* = [67.20,72.10, 77.00,81.90,86.80]^{\text{T}}\in{\bf{R}}^6$. 从图2可以看出, 自适应权重$ \alpha_{ij} $一直处于非减趋势, 当所有智能体聚合项估计值$ \eta $达到一致时权重停止更新. 由于算法(9)采用自适应平均一致性策略估计全局聚合函数$ \sigma(x) $, 在提高算法收敛的同时避免控制参数收敛范围对拉普拉斯矩阵第二小特征根的依赖. 此外, 从图2可以看出, 算法 (9)能够在较短时间内对全局聚合项$ \sigma(x) $实现精确估计.
图 2 本文算法的自适应权重$ \alpha_{ij}$轨迹Fig. 2 The trajectories of the adaptive weight $ \alpha_{ij}$ in our algorithm作为对比, 文献[40]利用多智能体系统动态平均一致性方法实现聚合项获取, 文献[42]使用基于符号函数的梯度跟踪策略. 从相同初始条件和相同控制参数出发, 三种算法的收敛误差轨迹展示如图3所示, 其中纵坐标为$ e_{\text{opt}}(t) = \ln(\frac{1}{2}\sum\nolimits_{i = 1}^n(x_i(t)- x_i^*)^2) $. 文献[42]通过使用符号函数提高算法收敛速度, 但符号函数的存在也会导致算法收敛精度降低. 这一点在图3中得到验证. 与文献[40]固定控制参数相比, 本文所设计算法拥有相对较快的收敛速度. 此外, 与文献[40, 42]相比, 本文所设计算法控制参数能够自适应调整, 无需手动设置. 为分析参数大小对算法收敛速度的影响, 不同参数下算法的收敛误差轨迹如图4所示. 从算法(24b)可以看出, 参数$ \beta $作为比例项$ -\sum\nolimits_{j = 1}^na_{ij}(\lambda_i-\lambda_j) $的控制系数, $ \beta $值越大, 算法(9)收敛越快. 变量$ z $用来平衡$ x_i $与$ d_i $的差值, $ \theta $值越小, $ z^* $幅值越大. 算法(9)中$ z_i $从$ z_i(0) $收敛至$ z_i^* $所需时间越久, 算法(9)收敛越慢. 参数$ \gamma_{ij} $作为变量$ \alpha_{ij} $的控制系数, $ \gamma_{ij} $值越大, 算法(9)收敛越快. 上述分析与图4所示结果一致. 值得注意的是, 过大参数$ \beta,\theta,\gamma_{ij} $值对算法(9)加速效果甚微. 故为降低智能体存储负担, 在满足定理1收敛范围下默认设置为1.
图 3 不同算法的输出收敛误差轨迹Fig. 3 The output convergence error trajectories of different algorithms
图 4 不同控制参数值下本文算法的输出收敛误差轨迹Fig. 4 The output convergence error trajectories of our algorithm under different control parameters2.4 一般线性多智能体系统案例仿真
接下来对算法(24)和算法(26)进行有效性验证, 其中, $ {\cal{V}} = \{1,2,3,4,5\} $, $A_1 = A_2 = [0,1;0,0], $ $A_3 = A_4 = [0,-1;1,-2],$ $A_5 = [1,0;1,0],$ $B_1 = B_2 = [0,1; 1,-2],$ $B_3 = B_4 = [1,0;3,-1],B_5 = [1,0;1,1], $ $C_i = {\boldsymbol{I}}_2, \forall i\in{\cal{V}}.$ 此外, 每个智能体的成本函数定义如下:
$$ \begin{split} f_1(y_1)& = \Vert y_1-[3,3]^{\text{T}}\Vert^2+\Vert y_1\Vert^2+\sigma(y)(y_{11}+y_{21})\\ f_2(y_2)& = \text{exp}(\Vert y_2\Vert^2)+\sigma(y)(y_{12}+y_{22})\\ f_3(y_3)& = \Vert y_3- [3,3]^{\text{T}}\Vert^2 +\ln(\Vert y_3\Vert^2)+\sigma(y)(y_{13}+y_{23})\\ f_4(y_4)& = \Vert y_4\Vert^2+\exp(2(y_{41}-y_{42}))+\sigma(y)(y_{14}+y_{24})\\ f_5(y_5)& = \exp(3y_{51}-5y_{52})+\sigma(y)(y_{15}+y_{25}) \end{split} $$ (36) 其中, 全局聚合项定义为$ \sigma(y) = \frac{1}{n}\sum\nolimits_{i = 1}^n(y_{i1}^3+y_{i2}^3) $. 令局部期望资源量为$ d_i = [0.5,2]^{\text{T}},\forall i\in{\cal{V}} $. 上述系统的反馈矩阵设定为$ K_{11} = K_{12} = [0,2;0,1], $ $K_{13} = K_{14} = [0,-1;-1,-1],$ $K_{15} = [1,0;0,0] ,$ $K_{21} = K_{22} = [2,1;1,0],$ $K_{23} = K_{24} = [1,0;3,-1], $ $K_{25} = [1,0;-1, 1],$ $F_1 = F_2 = [1,\,1;\,0,\,1],$ $F_3 = F_4 = [1,-1;\,1,-1],$ $F_5 = [2,0;1,1]$. 控制参数设定为$\beta = \theta = \gamma_{ij} = \gamma_{ji} = 1,\forall i, j\in{\cal{V}}$. 算法(26)的运行轨迹如图5和图6所示. 从图5可以看出, 本文所设计算法能够精确收敛至理论最优解 $ y^* = [(1.03,2.03), $ $(0,1.16),(1.24, 2.25), $ $(0.02, 2.09), (0.20, 2.46)]^{\text{T}}$. 此外可以看到, 假设4要求聚合项中$ \varphi_i(y_i) $满足Lipschitz连续, 但仿真案例中$ \varphi_i(y_i) = y_{i1}^3+y_{i2}^3 $并不满足此项限制. 在算法(26)中, 我们证明了变量$ y_i $的有界性, 且所设计算法并不需要知道真正的Lipschtiz常数. 由于算法控制参数$ \alpha_{ij} $自适应增加以使变量$ \eta $趋向于聚合函数$ \sigma(x) $, 并以此保证系统的稳定. 所以本文的算法依然有效. 与已有算法相比, 本文所设计算法有更广的应用范围. 当状态信息不可测时, 算法(26)利用状态观测器对智能体状态进行预计, 并结合智能体输出设计控制算法. 如图6所示, 本文所设计的观测器能精确跟踪智能体状态信息.
3. 结束语
本文针对多智能体系统的分布式聚合博弈纳什均衡问题进行研究, 其中各智能体受到全局等式约束, 且局部成本函数包含与全体智能体相关的聚合项. 为此, 首先针对一阶积分型智能体, 设计一种自适应分布式纳什均衡算法, 其中各智能体利用自适应梯度跟踪技术实现全局聚合项的分布式获取. 其次将所设计算法推广至状态信息可测和不可测下的一般线性异构多智能体系统. 本文假设1中要求智能体间通信拓扑为无向连通网络. 然而在一些通信环境较差情况下或者通信存在时延的情况下, 无向连通网络难以满足. 此时智能体间通信拓扑变为有向非平衡网络. 本文所设计方法随之失效. 此外, 本文设计自适应策略以通信链路为对象, 而随着智能体邻居数增加, 算法所需存储变量相应增加. 未来, 我们将研究如何设计有向非平衡网络下基于节点的自适应分布式聚合博弈纳什均衡求解问题, 并尝试将该成果推广至非线性系统.
-
图 2 本文算法的自适应权重$ \alpha_{ij}$轨迹
Fig. 2 The trajectories of the adaptive weight $ \alpha_{ij}$ in our algorithm
图 3 不同算法的输出收敛误差轨迹
Fig. 3 The output convergence error trajectories of different algorithms
图 4 不同控制参数值下本文算法的输出收敛误差轨迹
Fig. 4 The output convergence error trajectories of our algorithm under different control parameters
-
[1] Cornes R. Aggregative environmental games. Environmental and Resource Economics, 2016, 63(2): 339−365 doi: 10.1007/s10640-015-9900-6 [2] Barrera J, Garcia A. Dynamic incentives for congestion control. IEEE Transactions on Automatic Control, 2015, 60(2): 299−310 doi: 10.1109/TAC.2014.2348197 [3] 耿远卓, 袁利, 黄煌, 汤亮. 基于终端诱导强化学习的航天器轨道追逃博弈. 自动化学报, 2023, 49(5): 974−984Geng Yuan-Zhuo, Yuan Li, Huang Huang, Tang Liang. Terminal-guidance based reinforcement-learning for orbital pursuit-evasion game of the spacecraft. Acta Automatica Sinica, 2023, 49(5): 974−984 [4] Ye M J, Han Q L, Ding L, Xu S Y. Distributed Nash equilibrium seeking in games with partial decision information: A survey. Proceedings of the IEEE, 2023, 111(2): 140−157 doi: 10.1109/JPROC.2023.3234687 [5] 王龙, 黄锋. 多智能体博弈、学习与控制. 自动化学报, 2023, 49(3): 580−613Wang Long, Huang Feng. An interdisciplinary survey of multi-agent games, learning, and control. Acta Automatica Sinica, 2023, 49(3): 580−613 [6] 陈灵敏, 冯宇, 李永强. 基于距离信息的追逃策略: 信念状态连续随机博弈. 自动化学报, 2024, 50(4): 828−840Chen Ling-Min, Feng Yu, Li Yong-Qiang. Distance information based pursuit-evasion strategy: Continuous stochastic game with belief state. Acta Automatica Sinica, 2024, 50(4): 828−840 [7] Koshal J, Nedić A, Shanbhag U V. Distributed algorithms for aggregative games on graphs. Operations Research, 2016, 64(3): 680−704 doi: 10.1287/opre.2016.1501 [8] Grammatico S. Dynamic control of agents playing aggregative games with coupling constraints. IEEE Transactions on Automatic Control, 2017, 62(9): 4537−4548 doi: 10.1109/TAC.2017.2672902 [9] Huang S J, Lei J L, Hong Y G. A linearly convergent distributed Nash equilibrium seeking algorithm for aggregative games. IEEE Transactions on Automatic Control, 2023, 68(3): 1753−1759 doi: 10.1109/TAC.2022.3154356 [10] Ye M J, Hu G Q, Xie L H, Xu S Y. Differentially private distributed Nash equilibrium seeking for aggregative games. IEEE Transactions on Automatic Control, 2022, 67(5): 2451−2458 doi: 10.1109/TAC.2021.3075183 [11] Shi C X, Yang G H. Distributed Nash equilibrium computation in aggregative games: An event-triggered algorithm. Information Sciences, 2019, 489: 289−302 doi: 10.1016/j.ins.2019.03.047 [12] Parise F, Gentile B, Lygeros J. A distributed algorithm for almost-Nash equilibria of average aggregative games with coupling constraints. IEEE Transactions on Control of Network Systems, 2020, 7(2): 770−782 doi: 10.1109/TCNS.2019.2944300 [13] Sun C, Hu G Q. Nash equilibrium seeking with prescribed performance. Control Theory and Technology, 2023, 21(3): 437−447 doi: 10.1007/s11768-023-00169-4 [14] Belgioioso G, Nedic A, Grammatico S. Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks. IEEE Transactions on Automatic Control, 2021, 66(5): 2061−2075 doi: 10.1109/TAC.2020.3005922 [15] Pan W, Xu X L, Lu Y, Zhang W D. Distributed Nash equilibrium learning for average aggregative games: Harnessing smoothness to accelerate the algorithm. IEEE Systems Journal, 2023, 17(3): 4855−4865 doi: 10.1109/JSYST.2023.3264791 [16] Zhang P, Yuan Y, Liu H P, Gao Z. Nash equilibrium seeking for graphic games with dynamic event-triggered mechanism. IEEE Transactions on Cybernetics, 2022, 52(11): 12604−12611 doi: 10.1109/TCYB.2021.3071746 [17] Fang X, Wen G H, Zhou J L, Lv J H, Chen G R. Distributed Nash equilibrium seeking for aggregative games with directed communication graphs. IEEE Transactions on Circuits and Systems I: Regular Papers, 2022, 69(8): 3339−3352 doi: 10.1109/TCSI.2022.3168770 [18] Shi X L, Wen G H, Yu X H. Finite-time convergent algorithms for time-varying distributed optimization. IEEE Control Systems Letters, 2023, 7: 3223−3228 doi: 10.1109/LCSYS.2023.3312297 [19] 时侠圣, 杨涛, 林志赟, 王雪松. 基于连续时间的二阶多智能体分布式资源分配算法. 自动化学报, 2021, 47(8): 2050−2060Shi Xia-Sheng, Yang Tao, Lin Zhi-Yun, Wang Xue-Song. Distributed resource allocation algorithm for second-order multi-agent systems in continuous-time. Acta Automatica Sinica, 2021, 47(8): 2050−2060 [20] An L W, Yang G H. Distributed optimal coordination for heterogeneous linear multiagent systems. IEEE Transactions on Automatic Control, 2022, 67(12): 6850−6857 doi: 10.1109/TAC.2021.3133269 [21] Shi J, Ye M J. Distributed optimal formation control for unmanned surface vessels by a regularized game-based approach. IEEE/CAA Journal of Automatica Sinica, 2024, 11(1): 276−278 doi: 10.1109/JAS.2023.123930 [22] 王鼎. 一类离散动态系统基于事件的迭代神经控制. 工程科学学报, 2022, 44(3): 411−419Wang Ding. Event-based iterative neural control for a type of discrete dynamic plant. Chinese Journal of Engineering, 2022, 44(3): 411−419 [23] 王鼎. 基于学习的鲁棒自适应评判控制研究进展. 自动化学报, 2019, 45(6): 1031−1043Wang Ding. Research progress on learning-based robust adaptive critic control. Acta Automatica Sinica, 2019, 45(6): 1031−1043 [24] Ye M J, Hu G Q. Adaptive approaches for fully distributed Nash equilibrium seeking in networked games. Automatica, 2021, 129: Article No. 109661 doi: 10.1016/j.automatica.2021.109661 [25] Ye M J. Distributed Nash equilibrium seeking for games in systems with bounded control inputs. IEEE Transactions on Automatic Control, 2021, 66(8): 3833−3839 doi: 10.1109/TAC.2020.3027795 [26] Zhang K J, Fang X, Wang D D, Lv Y Z, Yu X H. Distributed Nash equilibrium seeking under event-triggered mechanism. IEEE Transactions on Circuits and Systems II: Express Briefs, 2021, 68(11): 3441−3445 [27] Liu P, Xiao F, Wei B, Yu M. Nash equilibrium seeking for individual linear dynamics subject to limited communication resource. Systems and Control Letters, 2022, 161: Article No. 105162 [28] 张苗苗, 叶茂娇, 郑元世. 预设时间下的分布式优化和纳什均衡点求解. 控制理论与应用, 2022, 39(8): 1397−1406 doi: 10.7641/CTA.2022.10604Zhang Miao-Miao, Ye Mao-Jiao, Zheng Yuan-Shi. Prescribed-time distributed optimization and Nash equilibrium seeking. Control Theory and Applications, 2022, 39(8): 1397−1406 doi: 10.7641/CTA.2022.10604 [29] Zou Y, Huang B M, Meng Z Y, Ren W. Continuous-time distributed Nash equilibrium seeking algorithms for non-cooperative constrained games. Automatica, 2021, 127: Article No. 109535 doi: 10.1016/j.automatica.2021.109535 [30] Zhu Y N, Yu W W, Ren W, Wen G H, Gu J P. Generalized Nash equilibrium seeking via continuous-time coordination dynamics over digraph. IEEE Transactions on Control of Network Systems, 2021, 8(2): 1023−1033 doi: 10.1109/TCNS.2021.3056034 [31] Deng Z H, Liu Y Y, Chen T. Generalized Nash equilibrium seeking algorithm design for distributed constrained noncooperative games with second-order players. Automatica, 2022, 141: Article No. 110317 doi: 10.1016/j.automatica.2022.110317 [32] Shi X S, Su Y X, Huang D R, Sun C Y. Distributed aggregative game for multi-agent systems with heterogeneous integrator dynamics. IEEE Transactions on Circuits and Systems II: Express Briefs, 2024, 71(4): 2169−2173 [33] Liang S, Yi P, Hong Y G, Peng K X. Exponentially convergent distributed Nash equilibrium seeking for constrained aggregative games. Autonomous Intelligent Systems, 2022, 2(1): Article No. 6 doi: 10.1007/s43684-022-00024-4 [34] Zhu Y N, Yu W W, Wen G H, Chen G R. Distributed Nash equilibrium seeking in an aggregative game on a directed graph. IEEE Transactions on Automatic Control, 2021, 66(6): 2746−2753 doi: 10.1109/TAC.2020.3008113 [35] Cheng M F, Wang D, Wang X D, Wu Z G, Wang W. Distributed aggregative optimization via finite-time dynamic average consensus. IEEE Transactions on Network Science and Engineering, 2023, 10(6): 3223−3231 [36] Wang X F, Teel A R, Sun X M, Liu K Z, Shao G R. A distributed robust two-time-scale switched algorithm for constrained aggregative games. IEEE Transactions on Automatic Control, 2023, 68(11): 6525−6540 doi: 10.1109/TAC.2023.3240981 [37] 梁银山, 梁舒, 洪奕光. 非光滑聚合博弈纳什均衡的分布式连续时间算法. 控制理论与应用, 2018, 35(5): 593−600 doi: 10.7641/CTA.2017.70617Liang Yin-Shan, Liang Shu, Hong Yi-Guang. Distributed continuous-time algorithm for Nash equilibrium seeking of nonsmooth aggregative games. Control Theory & Applications, 2018, 35(5): 593−600 doi: 10.7641/CTA.2017.70617 [38] Deng Z H, Nian X H. Distributed algorithm design for aggregative games of disturbed multiagent systems over weight-balanced digraphs. International Journal of Robust and Nonlinear Control, 2018, 28(17): 5344−5357 doi: 10.1002/rnc.4316 [39] Lin W T, Chen G, Li C J, Huang T W. Distributed generalized Nash equilibrium seeking: A singular perturbation-based approach. Neurocomputing, 2022, 482: 278−286 doi: 10.1016/j.neucom.2021.11.073 [40] Deng Z H, Nian X H. Distributed generalized Nash equilibrium seeking algorithm design for aggregative games over weight-balanced digraphs. IEEE Transactions on Neural Networks and Learning Systems, 2019, 30(3): 695−706 doi: 10.1109/TNNLS.2018.2850763 [41] Liang S, Yi P, Hong Y G. Distributed Nash equilibrium seeking for aggregative games with coupled constraints. Automatica, 2017, 85: 179−185 doi: 10.1016/j.automatica.2017.07.064 [42] Deng Z H. Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica, 2021, 132: Article No. 109794 doi: 10.1016/j.automatica.2021.109794 [43] Zhang Y W, Liang S, Wang X H, Ji H B. Distributed Nash equilibrium seeking for aggregative games with nonlinear dynamics under external disturbances. IEEE Transactions on Cybernetics, 2020, 50(12): 4876−4885 doi: 10.1109/TCYB.2019.2929394 [44] Wang X F, Sun X M, Teel A R, Liu K Z. Distributed robust Nash equilibrium seeking for aggregative games under persistent attacks: A hybrid systems approach. Automatica, 2020, 122: Article No. 109255 doi: 10.1016/j.automatica.2020.109255 [45] Deng Z H. Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players. Automatica, 2022, 135: Article No. 109980 doi: 10.1016/j.automatica.2021.109980 [46] Deng Z H, Liang S. Distributed algorithms for aggregative games of multiple heterogeneous Euler-Lagrange systems. Automatica, 2019, 99: 246−252 doi: 10.1016/j.automatica.2018.10.041 [47] Deng Z H. Distributed algorithm design for aggregative games of Euler-Lagrange systems and its application to smart grids. IEEE Transactions on Cybernetics, 2022, 52(8): 8315−8325 doi: 10.1109/TCYB.2021.3049462 [48] Liu X Y, Zhang Y W, Wang X H, Ji H B. Distributed Nash equilibrium seeking design in network of uncertain linear multi-agent systems. In: Proceedings of the 16th IEEE International Conference on Control & Automation. Sapporo, Japan: IEEE, 2020. 147−152 [49] Li L, Yu Y, Li X X, Xie L H. Exponential convergence of distributed optimization for heterogeneous linear multi-agent systems over unbalanced digraphs. Automatica, 2022, 141: Article No. 110259 doi: 10.1016/j.automatica.2022.110259 [50] Liu Y, Yang G H. Distributed robust adaptive optimization for nonlinear multiagent systems. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(2): 1046−1053 doi: 10.1109/TSMC.2019.2894948 [51] Li S L, Nian X H, Deng Z H, Chen Z, Meng Q. Distributed resource allocation of second-order nonlinear multiagent systems. International Journal of Robust and Nonlinear Control, 2021, 31(11): 5330−5342 doi: 10.1002/rnc.5543 -
下载:
下载:
计量
- 文章访问数: 818
- HTML全文浏览量: 317
- PDF下载量: 196
- 被引次数: 0
