自适应分布式聚合博弈广义纳什均衡算法

时侠圣; 任璐; 孙长银

doi:10.16383/j.aas.c230584

自适应分布式聚合博弈广义纳什均衡算法

doi: 10.16383/j.aas.c230584

时侠圣^{1, 2, 3,},
任璐^{1, 2, 3,},
孙长银^{1, 2, 3,}

1.
安徽大学自主无人系统技术教育部工程研究中心合肥 230601
2.
安徽大学安徽省无人系统与智能技术工程研究中心合肥 230601
3.
安徽大学人工智能学院合肥 230601

基金项目: 国家自然科学基金创新研究群体科学基金(61921004), 国家自然科学基金重点项目(62236002), 国家自然科学基金(62303009)资助

详细信息

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

任璐：安徽大学人工智能学院讲师. 2021年获得东南大学控制科学与工程博士学位. 主要研究方向为多智能体系统一致性控制. E-mail: penny_lu@ahu.edu.cn

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

计量
- 文章访问数: 101
- HTML全文浏览量: 48
- 被引次数: 0
出版历程
- 收稿日期: 2023-09-19
- 录用日期: 2024-01-23
- 网络出版日期: 2024-03-12

Distributed Adaptive Generalized Nash Equilibrium Algorithm for Aggregative Games

SHI Xia-Sheng^{1, 2, 3
,},
REN Lu^{1, 2, 3
,},
SUN Chang-Yin^{1, 2, 3
,}

1.
Engineering Research Center of Autonomous Unmanned System Technology, Ministry of Education, Anhui University, Hefei 230601
2.
Anhui Provincial Engineering Research Center for Unmanned System and Intelligent Technology, Anhui University, Hefei 230601
3.
School of Artificial Intelligence, Anhui University, Hefei 230601

Funds: Supported by Foundation for Innovative Research Groups of National Natural Science Foundation of China (61921004), the Key Projects of National Natural Science Foundation of China (62236002), and National Natural Science Foundation of China (62303009)

More Information

Author Bio:
SHI Xia-Sheng　Postdoctor at the School of Artificial Intelligence, Anhui University. He received his Ph.D. degree in control science and control engineering from Zhejiang University in 2020. His research interests include distributed cooperative optimization and network system

REN Lu　Lecturer at the School of Artificial Intelligence, Anhui University. She received her Ph.D. degree in control science and engineering from Southeast University in 2021. Her research interest covers consensus control of multi-agent systems, and synchronization of complex dynamical networks

SUN Chang-Yin　Professor at the School of Artificial Intelligence, Anhui University. He received his bachelor degree in applied mathematics from Sichuan University in 1996, and his master and Ph.D. degrees in electrical engineering from Southeast University in 2001 and 2004, respectively. His research interest covers intelligent control, flight control, pattern recognition, and optimal theory. Corresponding author of this paper

摘要

摘要: 随着信息物理系统技术的发展, 面向多智能体系统的分布式协同优化问题受到广泛研究. 主要研究面向多智能体系统的受约束分布式聚合博弈问题, 其中局部智能体成本函数受到全局聚合项约束和全局等式耦合约束. 首先, 面向一阶积分型多智能体系统设计一种基于估计梯度下降的纳什均衡求解算法. 其中, 利用多智能体系统平均一致性方法设计一种自适应估计策略, 以实现全局聚合项约束分布式估计. 并据此计算出梯度函数估计值. 其次, 利用状态反馈策略和输出反馈策略将上述算法推广至状态信息可测和状态信息不可测一般异构线性多智能体系统. 最后, 利用拉萨尔不变性原理证实上述算法收敛性, 并提供多组案例仿真用以验证算法有效性.
- 聚合博弈 /
- 自适应 /
- 比例积分 /
- 梯度跟踪 /
- 一般线性多智能体系统
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, an Nash equilibrium seeking algorithm based on estimation gradient descent is designed for the first-order integral-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.
- Aggregative game /
- adaptive /
- proportional-integral /
- gradient tracking /
- general linear multi-agent systems

HTML全文

图 1 案例1中算法(3)状态$ x_i$轨迹

Fig. 1 The state trajectories $ x_i(t)$ in case 1 with algorithm (3)

下载: 全尺寸图片幻灯片

图 2 案例1中算法(3)自适应权重$ \alpha_{ij}$轨迹

Fig. 2 The trajectories of the adaptive weight $ \alpha_{ij}$ in case 1 with algorithm (3)

下载: 全尺寸图片幻灯片

图 3 案例1中已有算法收敛速度轨迹

Fig. 3 The convergence rate trajectories of the existing algorithms in case 1

下载: 全尺寸图片幻灯片

图 4 案例1中不同参数值下算法(9)收敛速度轨迹

Fig. 4 The convergence rate trajectories of algorithm (9) under different control parameters

下载: 全尺寸图片幻灯片

图 5 案例2中算法(26)状态$ y_i$轨迹

Fig. 5 The output trajectories $ y_i$ in case 2 with algorithm (26)

下载: 全尺寸图片幻灯片

图 6 案例2中算法(26)状态观测误差轨迹

Fig. 6 The trajectories of estimator error in case 2 with algorithm (26)

下载: 全尺寸图片幻灯片

参考文献(51)

[1]	Cornes R. Aggregative environmental games. Environmental & Resource Economics, 2016, 63(2): 339-365.
[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-984. GENG 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, Han Q L, Ding L, Xu S. 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-613. WANG Long, HUANG Feng. An interdisciplinary survey of multi-agent games, learning, and control. ACTA Automatica SINICA, 2023, 49(3): 580-613.
[6]	陈灵敏, 冯宇, 李永强. 基于距离信息的追逃策略: 信念状态连续随机博弈. 自动化学报, 2023, 待出版. CHEN Ling-Min, FENG Yu, LI Yong-Qiang. Distance information based pursuit-evasion strategy: Continuous stochastic game with belief state. ACTA Automatica SINICA, 2023, in press.
[7]	Koshal J, Nedic A, Shanbhag U V. Distributed algorithm for aggregative games on graph. Operation Research, 2016, 63(3): 680-704.
[8]	Grammatico S. Dynamic dontrol 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, Lei J, Hong Y. 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, Hu G, Xie L, Xu S. 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, Yang G. 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 euilibria 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. Nash equilibrium seeking with prescribed performance. Control Theory and Technology, 2023, 21: 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, Lu Y, Zhang W. 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, 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, Zhou J, Lu J, Chen G. Distributed nash euilibrium 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, Wen G, Yu X. Finite-time convergent algorithms for time-varying distributed optimization. IEEE Control Sytems Letters, 2023, 7: 3223-3228. doi: 10.1109/LCSYS.2023.3312297
[19]	时侠圣, 杨涛, 林志赟, 王雪松. 基于连续时间的二阶多智能体分布式资源分配算法. 自动化学报, 2021, 47(8): 2050-2060. SHI Xiasheng, YANG Tao, LIN Zhiyun, 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, Yang G. Distributed optimal coordination for heterogeneous linear multi-agent systems. IEEE Transactions on Automatic Control, 2022, 67(12): 6850-6857. doi: 10.1109/TAC.2021.3133269
[21]	Shi J, Ye M. Distributed optimal formation control for unmanned surface vessels by 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-419. doi: 10.3321/j.issn.1001-053X.2022.3.bjkjdxxb202203010 WANG Ding. Event-based iterative neural control for a type of discrete dynamic plant. Chineses Journal of Engineering, 2022, 44(3): 411-419. doi: 10.3321/j.issn.1001-053X.2022.3.bjkjdxxb202203010
[23]	王鼎. 基于学习的鲁棒自适应评判控制研究进展. 自动化学报, 2019, 45(6): 1031-1043. WANG Ding. Research progress on learning-based robust adaptive critic control. Acta Automatica Sinica, 2019, 45(6): 1031-1043.
[24]	Ye M, Hu G. Adaptive approaches for fully distributed nash equilibrium seeking in networked games. Automatica, 2022, doi: 10.1016/j.automatica.2021.109661.
[25]	Ye M. Distributed nash euilibrium 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, Fang X, Wang D, Lv Y, Yu X. Distributed nash equilibrium seeking under event-triggered mechanism. IEEE Transactions on Circults and Systems-II: Express Briefs, 2021, 68(11): 3441-3445. doi: 10.1109/TCSII.2021.3068176
[27]	Liu P, Xiao F, Wei B, Yu M. Nash euilirium seeking for individual linear dynamics subject to limited communication resource. Systems & Control Letters, 2022, doi: 10.1016/j.sysconle.2022.105162.
[28]	张苗苗, 叶茂娇, 郑元世. 预设时间下的分布式优化和纳什均衡点求解. 控制理论与应用, 2022, 39(8): 1397-1406. doi: 10.7641/CTA.2022.10604 ZHANG Miaomiao, YE Maojiao, ZHENG Yuanshi. Prescribed-time distributed optimization and nash equilibrium seeking problem. Control Theory & Applications, 2022, 39(8): 1397-1406. doi: 10.7641/CTA.2022.10604
[29]	Zou Y, Huang B, Meng Z, Ren W. Continuous-time distributed nash euiqilibrium seeking algorithms for non-cooperative constrained games. Automatica, 2021, doi: 10.1016/j.automatica.2021.109535.
[30]	Zhu Y, Yu W, Ren W, Wen G, Gu J. Generalized nash euilibrium 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, Liu Y, Chen T. Generalized nash equilibrium seeking algorithm design for distributed constrained noncooperative games with second-order players. Automatica, 2022, doi: 10.1016/j.automatica.2022.110317.
[32]	Shi X, Su Y, Huang D, Sun C. Distributed aggregative game for multi-agent systems with heterogeneous integrator dynamics. IEEE Transactions on Circuits and Systems II: Express Briefs. 2023, in press. doi: 10.1109/TCSII.2023.3336386.
[33]	Liang S, Yi P, Hong Y, Peng K. Exponentially convergent distributed nash equilibrium seeking for constarained aggregative games. Autonomouos Intelligent Systems, 2022, 2: 6. doi: 10.1007/s43684-022-00024-4
[34]	Zhu Y, Yu W, Wen G, Chen G. 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, Wang D, Wang X, Wu Z, 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, Tee A R, Sun X, Liu K, Shao G. A dsitributed 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.70617 LIANG 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, Nian X. Distributed algorithm design for aggregative games of disturbed multiagent systems over weight-balanced digraphs. International Journal of Rboust and Nonlinear Control, 2018, 28: 5344-5357.
[39]	Lin W, Chen G, Li C, Huang T. 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, Nian X. Distributed generalized nash equilibrium seeking algorithm design for aggregative games over weighted-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. 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. Distributed generalized Nash equilibrium seeking algorithm for nonsmooth aggregative games. Automatica, 2021, doi: 10.1016/j.automatica.2021.109794.
[43]	Zhang Y, Liang S, Wang X, Ji H. 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, Sun X, Teel A R, Liu K. Distributed robust nash equilibrium seeking for aggregative games under persistent attacks: A hybrid systems approach. Automatica, 2020, doi: 10.1016/j.automatica.2020.109255.
[45]	Deng Z. Distributed Nash equilibrium seeking for aggregative games with second-order nonlinear players. Automatica, 2022, doi: 10.1016/j.automatica.2021.109980.
[46]	Deng Z, 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. 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, Zhang Y, Wang X, Ji H. Distributed nash equilibrium seeking design in network of uncertain linear multi-agent systems. In: Proceedings of IEEE 16th International Conference on Control & Automation. Sapporo, Hokkaido, Japan, IEEE, 2020: 147-152.
[49]	Li L, Yu Y, Li X, Xie L. Exponential convergence of distributed optimization for heterogeneous linear multi-agent systems over unbalanced digraphs. Automatica, 2022, in press. doi: 10.1016/j.automatica.2022.110259.
[50]	Liu Y, Yang G. Distributed robust adaptive optimization for nonlinear multi-agent systems. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(2): 1046-1053. doi: 10.1109/TSMC.2019.2894948
[51]	Li S, Nian X, Deng Z, 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