Deutsch

Die Robotik ist ein Themenfeld mit vielen Anwendungen, speziell im Bereich der Autonomie und Interaktion von Robotern. In dieser Arbeit werden spieltheoretische und Reinforcement-Learning-Ansätze verwendet, um einen Beitrag zur strategischen Planung im Roboterfußball zu leisten, der als motivierendes Beispiel dient. Zunächst wird ein hardware-unabhängiges spieltheoretisches Modell des Mehrspieler-Roboterfußballs entwickelt. Der Herausforderung, eine optimale Strategie für möglichst viele Roboter zu bestimmen, wird mittels exakter Modellreduktion begegnet. Dazu wird ein theoretisches Konzept zur Reduktion von Symmetrien entwickelt, das auf Homomorphismen basiert. Es wird bewiesen, dass eine derartige Modellreduktion schrittweise erfolgen kann und dass eine qualitativ neue Symmetrie Teil des Konzeptes ist. Die theoretischen Ergebnisse werden algorithmisch umgesetzt für Dynamic-Programming- (DP) und Reinforcement-Learning- (RL) Methoden. Die effizienteren DP Methoden werden durch Ideen aus dem Bereich fast invarianter Mengen weiterentwickelt. Ferner wird als Vorgehensweise zur Lösung realer Probleme empfohlen, zuerst ein approximatives Modell mit DP Methoden zu lösen und dann diese Lösung zur Initialisierung einer RL Methode zu nutzen. Alle Algorithmen werden numerisch analysiert und die optimalen Strategien vor einem Fußballhintergrund interpretiert. Ferner werden wichtige verbleibende Aufgaben identifiziert, die zur Umsetzung auf realen Robotern noch zu bewältigen sind.

English

Robotics is a topic with challenging applications specifically focused on autonomy of robots and their interactions. In this thesis, game theoretic and reinforcement learning approaches are utilised to contribute to strategic planning in robot soccer which serves as a motivating example. First, a hardware independent game theoretic model of multi-player robot soccer is developed. The challenge of determining an optimal strategy for as many robots as possible is met by exact model reduction, i. e. by finding equivalent smaller models. For this, a theoretical framework of symmetries is developed which is based on homomorphisms between two-player zero-sum Markov games. It is proven that this kind of model reduction can be performed stepwise and that a qualitatively new symmetry is part of the framework. The theoretical results are algorithmically exploited for dynamic programming (DP) and reinforcement learning (RL) methods. The more efficient DP methods are advanced by ideas of almost invariant sets. Furthermore, the following procedure for solving real world problems is recommended: firstly, to solve a rough model by DP methods and, secondly, to use that DP solution as initialisation for an RL method. All algorithms are studied numerically and the optimal strategies are interpreted in terms of soccer. Finally, some challenging tasks to implement these strategies on real robots are identified.