Entscheidungsfindung im Roboterfußball mittels Neuroevolution

Abstract

Während eines Fußballspiels befinden sich die Spieler einer Mannschaft in einer Reihe unterschiedlicher Spielsituationen. Jede dieser Spielsituationen erfordert die Ausführung einer Aktion, die der Spieler autonom bestimmen muss. Dabei sollte die gewählte Aktion jene sein, welche für die gesamte Mannschaft langfristig den größten Erfolg bringt. Manuelle Lösungen für dieses Problem der Entscheidungsfindung im Roboterfußball sind durch die enorme Komplexität der Domäne nur mit hohem Aufwand implementierbar, wartbar und auf unterschiedliche Spielvarianten übertragbar. Diese Arbeit untersucht die Anwendbarkeit der Neuroevolution zum automatisierten Erlernen performanter und flexibler Lösungen für das Entscheidungsfindungsproblem in zwei populären Spielformen des Roboterfußballs, dem Ballhalte- und Halbfeldspiel. Als virtuelle Umgebung dient dabei der Simulator der RoboCup 2D-Simulationsliga. Mithilfe der Neuroevolutionsmethode "Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT)" wurden Strategien zur Aktionsselektion sämtlicher Spieler der Offensiv- und Defensivmannschaft mit Ausnahme des Torwarts erlernt. Alle erzeugten Lösungen konnten die Spielstärke vordefinierter, manuell erstellter Benchmark-Lösungen übertreffen. Außerdem wurden die entwickelten Lösungen durch Ausnutzung der von HyperNEAT verwendeten indirekten Kodierung "Compositional Pattern Producing Network" in Spielvarianten mit unterschiedlichen Mannschafts- und Spielfeldgrößen ohne zusätzliche Evolutionszyklen eingesetzt. Die erlernten Strategien konnten automatisch übertragen werden, allerdings traten dabei teilweise Leistungseinbußen auf. Weiters wurden Experimente durchgeführt, um die Auswirkung der kooperativen Koevolution auf die Performanz einer Mannschaft zu untersuchen. Die Resultate dieser Experimente zeigten einen negativen Einfluss auf die resultierende Spielstärke des Teams.

During a robot soccer match, each player of a team faces several game situations, in which an action has to be chosen autonomously. The selected action should have the highest reward for the entire team in the long term. Due to the complexity of the domain, manual solutions to this high-level decision making problem are hard to implement, maintain and transfer to different game variations. This thesis explores the applicability of neuroevolution to automatically learn high performing and flexible solutions to the decision making problem in two popular subtasks of robot soccer, keepaway and half field soccer. The simulator of the RoboCup 2D simulation league serves as a virtual environment. Solutions to the decision making problem of all players in the offensive and defensive team, except for the goalkeeper, were evolved by the means of the neuroevolution method "Hypercube-based Neuroevolution of Augmenting Topologies (HyperNEAT)". All learned strategies could outperform the predefined, manual benchmark policies. Furthermore, the solutions were utilized without any additional learning cycles in several game variations with different team and pitch sizes by exploiting the indirect encoding scheme "Compositional Pattern Producing Network" employed by HyperNEAT. The acquired knowledge of the learned solutions was transferred automatically, but some performance penalties occurred. Additionally, experiments were conducted to observe the effects of cooperative coevolved players on a team's performance. These results indicated a strong negative effect.