Zusammenfassung
In diesem Beitrag wird die Anwendung von Gradient-Tracking-Verfahren in Multi-Cluster-Spielen untersucht. Neben einer Aufarbeitung relevanter Literatur umfasst die Arbeit einen theoretischen und simulativen Vergleich zwischen zwei bestehenden Gradient-Tracking-basierten Algorithmen. Hierbei wird insbesondere auf die Unterschiede der Kommunikationsarchitekturen eingegangen. In den durchgeführten Simulationen werden die Konvergenzzeiten der Algorithmen in Anwendung auf ein Nash-Cournot-Spiel miteinander verglichen. Es wird deutlich, dass sich eine weniger eingeschränkte Kommunikationsarchitektur zwischen den Clustern positiv auf die Konvergenzzeit auswirkt.
Abstract
In this work, the application of gradient-tracking procedures in multi-cluster games is analyzed. Next to a reprocessing of relevant literature, the work encompasses a theoretical and simulative comparison between two existing gradient-tracking-based algorithms. Differences regarding the communication architectures are highlighted in particular. In the conducted simulations the convergence times of the algorithms are compared with each other by application of the algorithms on a Nash-cournot game. It becomes apparent that a less restricted communication architecture between the agents is beneficial regarding the convergence time.
Funding source: Deutsche Forschungsgemeinschaft
Award Identifier / Grant number: 1984
Funding statement: Diese Arbeit wurde durch die Deutsche Forschungsgemeinschaft gefördert - Schwerpunktprogramm 1984.
Über die Autoren
M. Sc. Jan Zimmermann ist wisschenschaftlicher Mitarbeiter am Fachgebiet Regelungsmethoden und Robotik unter der Leitung von Prof. Dr.-Ing. J. Adamy am Institut für Automatisierungstechnik und Mechatronik im Fachbereich Elektrotechnik und Informationstechnik der Technischen Universität Darmstadt. Hauptarbeitsgebiete: Verteilte Optimierung, Spieltheorie.
Dr. rer. nat. Tatiana Tatarenko ist Gruppenleiterin der Forschergruppe Verteilte Optimierung und Spieltheorie des Fachgebietes Regelungsmethoden und Robotik unter der Leitung von Prof. Dr.-Ing. J. Adamy am Institut für Automatisierungstechnik und Mechatronik im Fachbereich Elektrotechnik und Informationstechnik der Technischen Universität Darmstadt. Hauptarbeitsgebiete: Angewandete Mathematik, verteilte Optimierung, Spieltheorie.
Prof. Dr.-Ing. Volker Willert ist Professor für maschinelles Sehen der Fakultät Elektrotechnik der Hochschule für angewandte Wissenschaften Würzburg-Schweinfurt. Hauptarbeitsgebiete: Maschinelles Sehen, Mobile Robotik, Maschinelles Lernen, Multi-Agenten-Systeme.
Prof. Dr.-Ing. Jürgen Adamy ist Professor des Fachgebietes Regelungsmethoden und Robotik am Institut für Automatisierungstechnik und Mechatronik im Fachbereich Elektrotechnik und Informationstechnik der Technischen Universität Darmstadt. Hauptarbeitsgebiete: Nichtlineare Regelungstechnik, Computational Intelligence, Mobile Robotik.
Literatur
1. Ahat, M., S.B. Amor, M. Bui, A. Bui, G. Guérard and C. Petermann. 2013. Smart Grid and Optimization. American Journal of Operations Research 3(1): 196–206.10.4236/ajor.2013.31A019Search in Google Scholar
2. Dall’Anese, E., H. Zhu and G.B. Giannakis. 2013. Distributed optimal power flow for smart microgrids. IEEE Transactions on Smart Grid 4(3): 1464–1475.10.1109/TSG.2013.2248175Search in Google Scholar
3. Kanzow, C. and A. Schwartz. 2018. Spieltheorie: Theorie und Verfahren zur Lösung von Nash- und verallgemeinerten Nash-Gleichgewichtsproblemen. Birkhäuser.10.1007/978-3-319-96679-3Search in Google Scholar
4. Kasbekar, G.S. and S. Sarkar. 2012. Pricing games among interconnected microgrids. In: IEEE Power and Energy Society General Meeting.10.1109/PESGM.2012.6344881Search in Google Scholar
5. Meng, M. and X. Li. 2020. On the linear convergence of distributed Nash equilibrium seeking for multi-cluster games under partial-decision information. arXiv: 2005.06923.Search in Google Scholar
6. Mengelkamp, E., J. Gärttner, K. Rock, S. Kessler, L. Orsini and C. Weinhardt. 2018. Designing microgrid energy markets: A case study: The Brooklyn Microgrid. Applied Energy 210: 870–880.10.1016/j.apenergy.2017.06.054Search in Google Scholar
7. Nedić, A., A. Olshevsky and W. Shi. 2017. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM 27(4): 2597–2633.10.1137/16M1084316Search in Google Scholar
8. Pang, Y. and G. Hu. 2021. Gradient-free Nash equilibrium seeking in n-cluster games with uncoordinated constant step-sizes. arXiv: 2008.13088.10.1109/CDC42340.2020.9304014Search in Google Scholar
9. Pu, S., W. Shi, J. Xu and A. Nedić. 2021. Push-Pull Gradient Methods for Distributed Optimization in Networks. IEEE Transactions on Automatic Control 66(1): 1–16.10.1109/CDC.2018.8619047Search in Google Scholar
10. Qu, G. and Na Li. 2018. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems 5(3): 1245–1260.10.1109/CDC.2016.7798263Search in Google Scholar
11. Tatarenko, T. and A. Nedić. 2020. Geometric convergence of distributed gradient play in games with unconstrained action sets. IFAC-PapersOnLine 53: 3367–3372, Elsevier B. V.10.1016/j.ifacol.2020.12.1501Search in Google Scholar
12. Tatarenko, T., J. Zimmermann and J. Adamy. 2021. Gradient play in n-cluster games with zero-order information. arXiv: 2107.12648.10.1109/CDC45484.2021.9683636Search in Google Scholar
13. Xin, R., C. Xi and U.A. Khan. 2019. FROST – Fast row-stochastic optimization with uncoordinated step-sizes. Eurasip Journal on Advances in Signal Processing 2019(1): 1.10.1186/s13634-018-0596-ySearch in Google Scholar
14. Ye, M. and G. Hu. 2017. Simultaneous social cost minimization and Nash equilibrium seeking in non-cooperative games. In: Chinese Control Conference, CCC, pp. 3052–3059.10.23919/ChiCC.2017.8027826Search in Google Scholar
15. Ye, M., G. Hu and F.L. Lewis. 2018. Nash equilibrium seeking for N-coalition noncooperative games. Automatica 95: 266–272.10.1016/j.automatica.2018.05.020Search in Google Scholar
16. Ye, M., G. Hu, F.L. Lewis and L. Xie. 2017. A unified strategy for solution seeking in graphical N-coalition noncooperative games. IEEE Transactions on Automatic Control 64(11): 4645–4652.10.1109/TAC.2019.2901820Search in Google Scholar
17. Ye, M., G. Hu and S Xu. 2020. An extremum seeking-based approach for Nash equilibrium seeking in N-cluster noncooperative games. Automatica 114: 108815.10.1016/j.automatica.2020.108815Search in Google Scholar
18. Zeng, X., J. Chen, S. Liang and Y. Hong. 2019. Generalized Nash equilibrium seeking strategy for distributed nonsmooth multi-cluster game. Automatica 103: 20–26.10.1016/j.automatica.2019.01.025Search in Google Scholar
19. Zimmermann, J., T. Tatarenko, V. Willert and J. Adamy. 2021. Solving leaderless multi-cluster games over directed graphs. European Journal of Control 62: 14–21.10.1016/j.ejcon.2021.06.007Search in Google Scholar
20. Zou, Y., B. Huang, Z. Meng and W. Ren. 2019. Distributed Nash equilibrium seeking algorithms for two-layer constrained non-cooperative games. In: Chinese Control Conference, CCC, pp. 5776–5781.10.23919/ChiCC.2019.8865303Search in Google Scholar
© 2022 Walter de Gruyter GmbH, Berlin/Boston