Verteilte Methoden zur Lösung von beschränkten Optimierungsproblemen in Multiagentensystemen

Zimmermann, Jan (2023)
Verteilte Methoden zur Lösung von beschränkten Optimierungsproblemen in Multiagentensystemen.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00024563
Dissertation, Erstveröffentlichung, Verlagsversion

URL / URN: https://tuprints.ulb.tu-darmstadt.de/24563

Kurzbeschreibung (Abstract)

Besteht ein Optimierungsproblem aus einer Menge von einzelnen Kostenfunktionen und Nebenbedingungen, die auf ein Multiagentensystem verteilt sind, so wird von einem verteilten Optimierungsproblem gesprochen. Dabei besitzt jeder Agent eine der Kostenfunktionen und eine gewisse Untermenge der Nebenbedingungen. Je nachdem, ob die Agenten zusammenarbeiten, um das Problem gemeinsam zu lösen, oder gegeneinander bezüglich ihrer verkoppelten Kostenfunktionen konkurrieren, wird die Problemstellung als kooperativ oder nicht-kooperativ bzw. als spieltheoretisches Problem bezeichnet. Um eine robuste, ausfallsichere Lösung der jeweiligen Problemstellung zu erreichen, bei der zusätzlich die Kostenfunktionen bzw. Nebenbedingungen der Agenten privat bleiben, müssen verteilte Optimierungsmethoden entwickelt werden, die auf einer möglichst großen Menge von Kommunikationsarchitekturen konvergieren. Darüber hinaus existieren verteilte Problemstellungen, bei denen eine Untermenge von Agenten des Netzwerkes kooperativ zusammenarbeitet, während mit anderen Agenten ein nicht-kooperatives Verhältnis besteht. Für diese Art von Problemen ist eine entsprechend angepasste, verteilte Lösungsmethode notwendig.

In der vorliegenden Arbeit werden zur Lösung von kooperativen, verteilten Problemstellungen unbeschränkte, gradientenbasierte Verfahren erweitert, sodass Nebenbedingungen berücksichtigt werden können. Dabei kommen die Techniken der Strafterme, der Lagrangeparameter bzw. des dualen Ansatzes und der Projektion in drei verschiedenen Algorithmen zum Einsatz. Neben der Berücksichtigung von Beschränkungen ist ein weiteres Ziel, dass die resultierenden Algorithmen auf einer möglichst großen Menge von Kommunikationsarchitekturen konvergieren. Die Konvergenz der Verfahren wird mathematisch bewiesen und durch Simulationen veranschaulicht.

Zusätzlich werden beschränkte Multiclusterspiele betrachtet, die aus der Kombination einer kooperativen und nicht-kooperativen Problemstellung bestehen. Damit das Problem als gelöst betrachtet werden kann, muss ein stabiler Zustand, d. h. ein Nash-Gleichgewicht, zwischen den konkurrierenden Parteien und gleichzeitig ein kooperatives Optimum bezüglich der zusammenarbeitenden Agenten erreicht werden. Für diese Problemstellung wird ein gradientenbasiertes Verfahren vorgestellt, das die Problemstellung unter Verwendung eines Gradientenschätzverfahrens und der Projektion der Aktualisierungsgleichungen auf die jeweilige Nebenbedingungsmenge lösen kann. Im theoretischen Teil wird lineare Konvergenz des Verfahrens zum Optimum nachgewiesen, während in Simulationen die Effizienz des Verfahrens gezeigt wird.

Alle im Rahmen der vorliegenden Arbeit durchgeführten Simulationen werden auf eine energietechnische Problemstellung bezogen. Dabei wird ein Einsatzplanproblem zwischen Microgrids betrachtet, bei dem der optimale, kooperative Einsatz von Generatoren und Speichern innerhalb der Micrgrids geplant wird, während die Microgrids selbst gegeneinander in einer Marktsituation bezüglich des Strompreises eines Hauptnetzes konkurrieren.

Typ des Eintrags:

Dissertation

Erschienen:

2023

Autor(en):

Zimmermann, Jan

Art des Eintrags:

Erstveröffentlichung

Titel:

Verteilte Methoden zur Lösung von beschränkten Optimierungsproblemen in Multiagentensystemen

Sprache:

Deutsch

Referenten:

Tatarenko, Dr. Tatiana ; Adamy, Prof. Dr. Jürgen ; Deutscher, Prof. Dr. Joachim

Publikationsjahr:

25 Oktober 2023

Ort:

Darmstadt

Kollation:

XVI, 235 Seiten

Datum der mündlichen Prüfung:

23 Juni 2023

DOI:

10.26083/tuprints-00024563

URL / URN:

https://tuprints.ulb.tu-darmstadt.de/24563

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

A distributed optimization problem is defined as a set of cost functions and constraints that are distributed over a multi-agent system. Each of these agents holds one of the cost functions and a specific subset of the overall constraint set. The distributed problem is denoted as either cooperative or non-cooperative, i. e. game theoretic, depending on whether the agents work together to solve the problem at hand or compete against each other regarding their coupled cost functions. In order to achieve a robust and fail-safe solution of the problem, while keeping the cost functions and constraints private, distributed optimization procedures need to be employed. Additionally, distributed problems exist, wherein a cooperative behaviour is exhibited by a subset of agents, while there is competition with other agents of the network. In order to solve such problems, distributed algorithms need to be accordingly adapted.

In this thesis, unconstrained and gradient-based algorithms are extended, such that constraints can be handled in cooperative environments. For that, penalty functions, Langrange multipliers, i. e. dual approaches, and projections are employed in three distinct algorithms. Another goal next to the consideration of constraints is to make the algorithms applicable to a wide range of communication architectures. For all three algorithms, convergence is mathematically proven and illustrated by simulations.

Furthermore, constrained multi-cluster games are considered, which consist of a combination of cooperative and non-cooperative problems. In order to achieve a solution of such games, a stable state, i. e. a Nash Equilibrium, needs to be reached between the non-cooperating parties while simultaneously achieving local optima inside the cooperating groups. This problem is solved in this work by a gradient-based algorithm that estimates the gradients in the cooperative clusters and projects the gradient steps onto the considered constraint sets. Linear convergence is proven, while simulations show the practical efficiency of the procedure.

All simulations are performed on the basis of a power engineering problem, which is posed as an optimal dispatch problem between microgrids. Herein, the optimal dispatch of cooperating generators and storage devices needs to be set inside the microgrids, while the latter compete against each other in a market situation regarding power provided by the main grid.

Englisch

Status:

Verlagsversion

URN:

urn:nbn:de:tuda-tuprints-245639

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

600 Technik, Medizin, angewandte Wissenschaften > 621.3 Elektrotechnik, Elektronik

Fachbereich(e)/-gebiet(e):

18 Fachbereich Elektrotechnik und Informationstechnik
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Automatisierungstechnik und Mechatronik
18 Fachbereich Elektrotechnik und Informationstechnik > Institut für Automatisierungstechnik und Mechatronik > Regelungsmethoden und Intelligente Systeme

Hinterlegungsdatum:

25 Okt 2023 12:47

Letzte Änderung: