考虑通信和梯度时延的联盟博弈分布式对偶平均算法及在编队控制中的应用

doi:10.7527/S1000-6893.2024.31322

Abstract

Abstract:

To address coalition games with communication and gradient delays， this paper proposes a distributed algorithm based on dual averaging and delayed gradient to seek the Nash equilibrium. With the help of augmented graphs and Bregman divergence， it is demonstrated that the proposed algorithm converges to the Nash equilibrium at a sub-linear rate， and the effect of communication and gradient delays on the convergence error is also clarified. Simulations in formation of unmanned aerial vehicle swarms verify the effectiveness of the proposed algorithm.

Key words: coalition game, communication delay, gradient delay, dual averaging, Nash equilibrium

CLC Number:

Jiaxun LIU, Mingfei CHEN, Xiaopeng XU, Shuai LIU, Dong WANG. Distributed dual average algorithm with communication and gradient delays for coalition games and its application in formation control[J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531322.

Figures/Tables 8

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

References 24

[1]	杨加秀，李新凯，张宏立，等. 切换拓扑下异构集群的强化学习时变编队控制［J］. 航空学报， 2024， 45（10）： 329166.
	YANG J X， LI X K， ZHANG H L， et al. Time-varying formation control for heterogeneous clusters with switching topologies via reinforcement learning［J］. Acta Aeronautica et Astronautica Sinica， 2024， 45（10）： 329166 （in Chinese）.
[2]	郭洪振，陈谋，戴永东，等. 分布式自适应事件触发四旋翼无人机编队控制［J］. 航空学报， 2023， 44（S2）： 491-500.
	GUO H Z， CHEN M， DAI Y D， et al. Distributed adaptive event-triggered formation control for QUAVs‍［J］. Acta Aeronautica et Astronautica Sinica， 2023， 44（S2）： 729917 （in Chinese）.
[3]	ZIMMERMANN J， TATARENKO T， WILLERT V， et al. Solving leaderless multi-cluster games over directed graphs［J］. European Journal of Control， 2021， 62： 14-21.
[4]	TAN S L， FANG Z H， WANG Y N， et al. A timestamp-based inertial best-response dynamics for distributed Nash equilibrium seeking in weakly acyclic games‍［J］. IEEE Transactions on Neural Networks and Learning Systems， 2024， 35（1）： 1330-1340.
[5]	LI Z K， JIAO J J， CHEN X. Distributed optimal control with recovered robustness for uncertain network systems： A complementary design approach‍［J］. IEEE Transactions on Automatic Control， 2024， 69（4）： 2484-2491.
[6]	XU H， LU K H， WANG T B， et al. Online distributed seeking for first-order Nash equilibria of nonconvex noncooperative games with multiple clusters‍［J］. IEEE Transactions on Circuits and Systems II： Express Briefs， 2023， 70（2）： 621-625.
[7]	YE M J， HU G Q， LEWIS F L. Nash equilibrium seeking for N-coalition noncooperative games‍［J］. Automatica， 2018， 95： 266-272.
[8]	NIAN X H， NIU F X， YANG Z. Distributed Nash equilibrium seeking for multicluster game under switching communication topologies‍［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（7）： 4105-4116.
[9]	ZHOU J L， LV Y Z， WEN G H， et al. Distributed Nash equilibrium seeking in consistency-constrained multicoalition games‍［J］. IEEE Transactions on Cybernetics， 2023， 53（6）： 3675-3687.
[10]	LIU F， DONG X W， YU J L， et al. Distributed Nash equilibrium seeking of N-coalition noncooperative games with application to UAV swarms［J］. IEEE Transactions on Network Science and Engineering， 2022， 9（4）： 2392-2405.
[11]	LI Y M， ZHU Y N， LI T， et al. Distributed Nash equilibrium seeking in a multi-coalition noncooperative game under incomplete decision information［J］. IEEE Transactions on Circuits and Systems Ⅱ： Express Briefs， 2022， 69（8）： 3400-3404.
[12]	GHARESIFARD B， CORTÉS J. Distributed convergence to Nash equilibria in two-network zero-sum games［J］. Automatica， 2013， 49（6）： 1683-1692.
[13]	MENG M， LI X X. On the linear convergence of distributed Nash equilibrium seeking for multi-cluster games under partial-decision information［J］. Automatica， 2023， 151： 110919.
[14]	CAO Y C， YU W W， REN W， et al. An overview of recent progress in the study of distributed multi-agent coordination‍［J］. IEEE Transactions on Industrial Informatics， 2013， 9（1）： 427-438.
[15]	HADJICOSTIS C N， CHARALAMBOUS T. Average consensus in the presence of delays in directed graph topologies‍［J］. IEEE Transactions on Automatic Control， 2014， 59（3）： 763-768.
[16]	TSIANOS K I， RABBAT M G. Distributed dual averaging for convex optimization under communication delays［C］∥2012 American Control Conference （ACC）. Piscataway： IEEE Press， 2012： 1067-1072.
[17]	NEDIĆ A， OZDAGLAR A. Convergence rate for consensus with delays‍［J］. Journal of Global Optimization， 2010， 47（3）： 437-456.
[18]	WANG X F， SUN X M， YE M J， et al. Robust distributed Nash equilibrium seeking for games under attacks and communication delays［J］. IEEE Transactions on Automatic Control， 2022， 67（9）： 4892-4899.
[19]	LI J Y， CHEN G， DONG Z Y， et al. Distributed mirror descent method for multi-agent optimization with delay［J］. Neurocomputing， 2016， 177： 643-650.
[20]	DUCHI J C， AGARWAL A， WAINWRIGHT M J. Dual averaging for distributed optimization： Convergence analysis and network scaling［J］. IEEE Transactions on Automatic Control， 2012， 57（3）： 592-606.
[21]	BREGMAN L M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming‍［J］. USSR Computational Mathematics and Mathematical Physics， 1967， 7（3）： 200-217.
[22]	NESTEROV Y. Primal-dual subgradient methods for convex problems［J］. Mathematical Programming， 2009， 120（1）： 221-259.
[23]	WANG H W， LIAO X F， HUANG T W， et al. Cooperative distributed optimization in multiagent networks with delays［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2015， 45（2）： 363-369.
[24]	NEDIĆ A， OLSHEVSKY A. Distributed optimization over time-varying directed graphs‍［J］. IEEE Transactions on Automatic Control， 2015， 60（3）： 601-615.

Distributed dual average algorithm with communication and gradient delays for coalition games and its application in formation control

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 24

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Zhaohang LI, Changxuan WEN, Dong QIAO, Bo PANG. Geometrical solution of multi-pursuer/one-evader orbital pursuit-evasion game based on reachable set theory [J]. Acta Aeronautica et Astronautica Sinica, 2024, 45(S1): 730803-730803.
[2]	Zebo ZHOU, Zeliang ZHANG, Xin PENG, Gun LI, Yang TAO, Liangquan WANG, Xin LUO. Multi-UAV decentralized cooperative navigation method based on memory-fusion [J]. Acta Aeronautica et Astronautica Sinica, 2023, 44(20): 628440-628440.
[3]	WANG Xin, YAN Jie, MENG Tingwei. High-speed target multi-stage interception scheme based on game theory [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 325598-325598.