Wegfindung, Entscheidungsfindung und Verhaltensanalyse in Multiagentensystemen

Hahn, Carsten (2022): Wegfindung, Entscheidungsfindung und Verhaltensanalyse in Multiagentensystemen. Dissertation, LMU München: Fakultät für Mathematik, Informatik und Statistik

Abstract

Die vorliegende Arbeit befasst sich mit der Wegfindung, Entscheidungsfindung und der Analyse des Verhaltens intelligenter Agenten, wenn diese in kontinuierlichen, zweidimensionalen Flächen bestimmte Ziele ansteuern sollen, ohne dabei mit statischen oder dynamischen Hindernissen zu kollidieren. Zunächst wird ein Verfahren entwickelt mit welchem ein einzelner Agent unter Verwendung eines erlernten Umgebungsmodells befähigt wird, intuitiv die zukünftigen Positionen beweglicher Objekte vorherzusagen, um so Kollisionen zu vermeiden bzw. Objekte direkt anzusteuern. Es wird vorgeschlagen, die erlernte Positionsvorhersage beweglicher Objekte mit einer baumartigen Suche nach günstigen Folgezuständen, indem der Ausgang von Aktionsfolgen simuliert wird, zu kombinieren. Zur Steigerung der Effizienz wird, aufbauend auf dem vorherigen Ansatz, das Verfahren modifiziert und die Positionsvorhersagen dynamischer Objekte über zeitabhängige Kantenkosten in einen Graph integriert, um so mit angepassten, klassischen Pfadplanungsalgorithmen, wie dem A* Algorithmus, Pfade in einer Raum-Zeit-Dimension planen zu können, die den Kontakt mit dynamischen Hindernissen von vornherein meiden. Außerdem wird in dieser Arbeit der Frage nachgegangen, wie der zum Routing benötigte Graph auch in sich dynamisch veränderten, kontinuierlichen Umgebungen aktuell gehalten werden kann, wozu auf eine Methode namens Stable Growing Neural Gas zurückgegriffen wird. Diese ist von der gleichmäßigen Ausbreitung von Gas-Molekülen im Raum inspiriert und diskretisiert auf diese Weise einen Raum. Weiter wird behandelt, wie der Graph parallel und kollisionsfrei von multiplen Agenten zum Routing verwendet werden kann, wofür die Verwendung eines Potential Field Ansatzes vorgeschlagen wird. Neben Detailverbesserungen an der Methode des Stable Growing Neural Gas, werden vor allem die Synergien erarbeitet, die sich aus der Kombination der Methoden des Stable Growing Neural Gas, dem Potential Field Ansatz und der Verwendung des A* Algorithmus ergeben. Um eine ganze Gruppe von Agenten zu kontrollieren, wird ein auf Reinforcement Learning basierendes Verfahren vorgeschlagen, um Agenten auf einen virtuellen, dynamischen Zielpunkt zuzusteuern. Dieses zeichnet sich durch eine hohe Anpassungsfähigkeit aus. In einem entwickelten Szenario, in welchem Agenten durch Kollisionen untereinander implizit benachteiligt werden, konnte gezeigt werden, dass die Agenten durch das entworfene Trainingsverfahren gelernt haben Kollisionen untereinander zu vermeiden, ohne explizit darauf trainiert zu werden. Um die Interaktion lernender Agenten weiter zu untersuchen, wird in einem umgedrehten Szenario eine Gruppe von Agenten mittels Reinforcement Learning darauf trainiert, einem auf sie zukommenden Objekt auszuweichen. Unter der Prämisse, dass sich dieses von mehreren potenziellen Zielen ablenken lässt, hat sich wie im vorhergehenden Szenario emergent ein Schwarmverhalten unter den Agenten entwickelt, was mit Methoden der Spieltheorie weiter untersucht wurde und bei der Untersuchung sozialer Interaktionen und Dilemmata von Bedeutung ist.

Abstract

This thesis deals with the pathfinding, decision-making and behavior analysis of intelligent agents when they are supposed to approach certain targets in continuous, two-dimensional areas without colliding with static or dynamic obstacles. First, a method is developed to enable a single agent, using a learned environment model, to intuitively predict the future positions of moving objects in order to avoid collisions or directly target objects. It is proposed to combine the learned position prediction of moving objects with a tree-like search for favorable subsequent states by simulating the outcome of action sequences. To increase efficiency, building on the previous approach, the method is modified to integrate the position predictions of dynamic objects into a graph via time-dependent edge costs, allowing adapted classical path planning algorithms, such as the A* algorithm, to plan paths in a space-time dimension that avoid contact with dynamic obstacles in the first place. In addition, this work explores the question of how the graph needed for routing can be kept up-to-date in dynamically changing, continuous environments, relying on a method called Stable Growing Neural Gas. This method inspired by the uniform distribution of gas molecules in space and discretizes a space in this way. Further, it is addressed how the graph can be used in parallel and collision-free by multiple agents for routing, for which the use of a Potential Field approach is proposed. In addition to detail improvements of the Stable Growing Neural Gas method, the synergies resulting from the combination of the Stable Growing Neural Gas methods, the Potential Field approach and the use of the A* algorithm are discussed. In order to control a whole group of agents, a reinforcement learning based method is proposed to steer agents towards a virtual dynamic target point. This is characterized by high adaptability. In a developed scenario, in which agents are implicitly penalized by collisions among each other, it could be shown that the agents learned to avoid collisions among each other by the designed training procedure without being explicitly trained for it. To further investigate the interaction of learning agents, in a reversed scenario, a group of agents is trained to avoid an approaching object using reinforcement learning. Under the premise that this can be distracted from multiple potential targets, swarming behavior emerged among the agents, as in the previous scenario, which was further investigated using methods from game theory and is important in the study of social interactions and dilemmas.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Themengebiete: 000 Allgemeines, Informatik, Informationswissenschaft ; 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
• Fakultäten: Fakultät für Mathematik, Informatik und Statistik
• Sprache der Hochschulschrift: Deutsch
• Datum der mündlichen Prüfung: 29. März 2022
• 1. Bericht­erstatter:in: Linnhoff-Popien, Claudia