引用本文

时侠圣, 任璐, 孙长银. 自适应分布式聚合博弈广义纳什均衡算法. 自动化学报, 2024, 50(6): 1210−1220 doi: 10.16383/j.aas.c230584

Shi Xia-Sheng, Ren Lu, Sun Chang-Yin. Distributed adaptive generalized Nash equilibrium algorithm for aggregative games. Acta Automatica Sinica, 2024, 50(6): 1210−1220 doi: 10.16383/j.aas.c230584

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230584

关键词

聚合博弈，自适应，比例积分，梯度跟踪，一般线性多智能体系统 

摘要

随着信息物理系统技术的发展, 面向多智能体系统的分布式协同优化问题得到广泛研究. 主要研究面向多智能体系统的受约束分布式聚合博弈问题, 其中局部智能体成本函数受到全局聚合项约束和全局等式耦合约束. 首先, 面向一阶积分型多智能体系统设计一种基于估计梯度下降的纳什均衡求解算法. 其中, 利用多智能体系统平均一致性方法设计一种自适应估计策略, 以实现全局聚合项约束分布式估计, 并据此计算出梯度函数估计值. 其次, 利用状态反馈策略和输出反馈策略将上述算法推广至状态信息可测和状态信息不可测一般线性异构多智能体系统. 最后, 利用拉萨尔不变性原理证实上述算法收敛性, 并提供多组案例仿真用以验证算法有效性.

文章导读

聚合博弈广泛存在于各个领域, 例如公共环境[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节对全文进行总结和展望. 

图 1  本文算法的状态x_i轨迹

图 2  本文算法的自适应权重α_ij轨迹

图 3  不同算法的输出收敛误差轨迹

本文针对多智能体系统的分布式聚合博弈纳什均衡问题进行研究, 其中各智能体受到全局等式约束, 且局部成本函数包含与全体智能体相关的聚合项. 为此, 首先针对一阶积分型智能体, 设计一种自适应分布式纳什均衡算法, 其中各智能体利用自适应梯度跟踪技术实现全局聚合项的分布式获取. 其次将所设计算法推广至状态信息可测和不可测下的一般线性异构多智能体系统. 本文假设1中要求智能体间通信拓扑为无向连通网络. 然而在一些通信环境较差情况下或者通信存在时延的情况下, 无向连通网络难以满足. 此时智能体间通信拓扑变为有向非平衡网络. 本文所设计方法随之失效. 此外, 本文设计自适应策略以通信链路为对象, 而随着智能体邻居数增加, 算法所需存储变量相应增加. 未来, 我们将研究如何设计有向非平衡网络下基于节点的自适应分布式聚合博弈纳什均衡求解问题, 并尝试将该成果推广至非线性系统. 

作者简介

时侠圣

安徽大学人工智能学院博士后. 2020年获得浙江大学控制科学与控制工程专业博士学位. 主要研究方向为分布式协同优化和网络化系统. E-mail: shixiasheng@zju.edu.cn

任璐

安徽大学人工智能学院讲师. 2021年获得东南大学控制科学与工程专业博士学位. 主要研究方向为多智能体系统一致性控制, 复杂动态网络的同步. E-mail: penny_lu@ahu.edu.cn

孙长银

安徽大学人工智能学院教授. 1996年获得四川大学应用数学专业学士学位. 分别于2001年, 2004年获得东南大学电子工程专业硕士和博士学位. 主要研究方向为智能控制, 飞行器控制, 模式识别和优化理论. 本文通信作者. E-mail: cysun@seu.edu.cn