Roboter-Fußball: Zum Tor mit den richtigen Algorithmen
In der Standard Platform League des RoboCups sehen alle Fußballspieler gleich aus. Wer das Tor schießt, entscheiden deshalb die besten Algorithmen.
(Bild: Peter Schulz)
- Tim Laue
- Thomas Röfer
Beim RoboCup spielen Roboter in verschiedenen Ligen Fußball – mit dem ultimativen Ziel, bis zur Mitte des Jahrhunderts den dann amtierenden menschlichen Weltmeister zu schlagen. Eine dieser Ligen ist die RoboCup Standard Platform League (SPL). Ihre Besonderheit: Sie ist die einzige RoboCup-Fußball-Liga, bei der alle teilnehmenden Teams dieselbe Roboter-Plattform nutzen müssen. Deshalb kommt es bei der SPL um die besten Algorithmen an, jedoch ausgetragen auf echten Robotern.
Meisterschaft der Maschinen:
Aktuell ist in der SPL der NAO von Softbank Robotics im Einsatz. Der NAO ist ein autonomer, humanoider Roboter. Somit ist schnelle und präzise Verarbeitung von Sensordaten notwendig, sowohl um das Geschehen in der Umgebung verfolgen zu können, als auch um Störungen während der Ausführung dynamischer Bewegungen kompensieren zu können.
Wie auch in den anderen RoboCup-Wettbewerben werden die Regeln der Liga jährlich angepasst: Das Spiel und seine Umgebung soll dem menschlichen Fußball immer ähnlicher werden. Dadurch steigt der Anspruch an Hardware und Software kontinuierlich.
Die Roboter-Plattform
Nach einigen ersten Jahren mit dem vierbeinigen Roboter AIBO der Firma Sony als Standard-Plattform arbeiten die Teams seit 2008 mit dem NAO von Softbank Robotics (ehemals Aldebaran Robotics). Der humanoide Roboter ist etwa 60 cm hoch und wiegt ungefähr 5 Kilogramm. Die aktuelle Version, der NAO V5, hat 25 über Servomotoren steuerbare Gelenke: elf für die Beine, zwei zum Bewegen des Kopfes sowie sechs pro Arm.
RoboCup Standard Platform League (9 Bilder)
(Bild: Judith Müller)
Hauptsensoren sind zwei im Kopf übereinander angeordnete Kameras, die jeweils Farbbilder mit einer Auflösung von bis zu 1280 × 960 Pixeln bei 30 Bildern pro Sekunde (fps) aufnehmen. Ein ebenfalls wichtiger und für die Korrektur dynamischer Bewegungen verwendeter Sensor ist der Inertialsensor im Körper des Roboters, der in drei Achsen Beschleunigung und Drehgeschwindigkeit misst. Darüber hinaus enthält jeder Roboter Ultraschallsensoren in der Brust, Drucksensoren unter den Füßen, und er kann von allen Motoren Stellung und Last abfragen.
Um Sensordaten zu verarbeiten und Aktionen zu berechnen, enthält jeder Roboter einen Rechner mit einem Atom-Prozessor von Intel (1,6 GHz). Auf diesem Rechner können beliebige eigene Programme ausgeführt werden. Für die Ansteuerung der Motoren sind zahlreiche Mikrocontroller verbaut, auf die man als Programmierer aber keinen direkten Zugriff hat.
Das Spielfeld
In den Anfangsjahren der SPL war die Spielumgebung stark vereinfacht, damit sich die Roboter leichter orientieren konnten. Dabei halfen künstliche Elemente und eine Kodierung mittels auffälliger, leicht unterscheidbarer Farben: Der Ball war orange, die massiven Tore gelb und blau. Rund um das Feld ordnete man eindeutige Landmarken über einer Bande an. Die Bande sorgte wiederum dafür, dass die Roboter das für die Bilderkennung störende Publikum nicht "sehen" konnten.
Zusammen mit einer konstanten, hellen Beleuchtung erleichterten diese Maßnahmen Aufgaben wie Bildverarbeitung, Objektverfolgung und Lokalisierung: Alle Flächen waren möglichst auffällig gestaltet. Zudem hatte das Feld eine Fläche von nur wenigen Quadratmetern, sodass Objekte nur über kurze Distanzen erkannt werden mussten.
(Bild: Judith Müller)
Mittlerweile ist die Gesamtgröße des Feldes auf 77 Quadratmeter angewachsen und die Spielelemente sehen genauso aus wie beim normalen Fußball inklusive weißen Toren mit Netzen und einem schwarz-weißen Ball.
Wie im "echten Fußball"
Außer den üblichen Feldmarkierungen wie Seitenauslinien gibt es keine zusätzlichen Feldelemente mehr, auch die Bande ist entfallen und der Blick der Roboter auf eine unstrukturierte Umgebung frei. Auch sind die Regeln bezüglich der Beleuchtung weitestgehend aufgehoben und 2016 gab es sogar einen Zusatzwettbewerb in einer Glashalle bei natürlichem Licht.
Diese Bedingungen beinhalten wesentlich komplexere Anforderungen an Bildverarbeitung und "Sensorfusion", also an das Verknüpfen der Daten der unterschiedlichen Sensoren. Beispielsweise müssen die eingesetzten Bildverarbeitungsalgorithmen den Ball von Roboterteilen unterscheiden können, die ebenfalls rund sein können und dunkle Flecken auf einem weißen Untergrund enthalten. Zudem ist das Spielfeld nun vollständig symmetrisch, was die Bestimmung des gegnerischen Tores erschwert.
Die Anzahl von drei Robotern pro Team wurde inzwischen auf fünf erhöht, in anderen RoboCup-Wettbewerben wird mitunter schon mit sechs Robotern gespielt. Die Roboter sind in der Lage, untereinander standardisierte Nachrichten auszutauschen. Die menschlichen Entwickler können diese Nachrichten aus Analysegründen mitlesen, dürfen aber während des Spiels selbst keine senden – denn spätestens ab Anpfiff müssen die Roboter autonom handeln.
Geleitet werden die Spiele von menschlichen Schiedsrichtern, die beispielsweise Fouls ahnden oder den Ball nach Spielunterbrechungen platzieren. In der RoboCup Small Size League werden derartige Aufgaben mitunter bereits von Programmen und Robotern ausgeführt. Die aktuellen Regeln der SPL (PDF) finden sich auf der SPL-Website.
Software: Offener Austausch, etablierte Architektur
Unter den teilnehmenden Teams gibt es einen regen und offenen Austausch von Informationen und auch Software. Die besten Teams einer Weltmeisterschaft sind durch die Regeln sogar dazu angehalten, Teile ihrer Software in dokumentierter Form zu publizieren. Viele Teams haben aber auch schon vor dieser Regel Software als Open Source bereitgestellt und legen bis heute mehr offen, als sie eigentlich müssten. Die Liga sammelt diese Veröffentlichungen auf einer eigenen Webseite. Durch diesen Austausch haben sich im Laufe der Jahre einige Ansätze als besonders erfolgreich etabliert. Am Beispiel des Bremer Teams B-Human, zu dessen Leitung die Autoren gehören, sollen einige dieser Verfahren erläutert werden.
Das Team besteht aus Wissenschaftlern und Studierenden der Universität Bremen (Fachbereich Informatik) und des Deutschen Forschungszentrums für Künstliche Intelligenz. Nach vorhergehenden Aktivitäten in anderen RoboCup-Wettbewerben nimmt es seit 2009 durchgängig und sehr erfolgreich unter dem Namen B-Human an Wettbewerben in der Standard Platform League teil: Fünf Weltmeistertitel hat es inzwischen gewonnen (2009, 2010, 2011, 2013, 2016). Die verwendete Software wird dabei kontinuierlich erweitert und weiterentwickelt, um so mit den Veränderungen der Liga Schritt zu halten und neue, innovative Ansätze zu evaluieren.
Einen humanoiden Roboter autonom Fußball spielen zu lassen ist eine komplexe Aufgabe, die das Zusammenspiel von Hunderten Algorithmen erfordert. Die B-Human-Software besteht aktuell aus ungefähr 150.000 Zeilen C++-Code und ist innerhalb einer selbst entwickelten Software-Architektur organisiert, die eine funktionale Dekomposition in einer Vielzahl kleiner Module für bestimmte Aufgaben ermöglicht. Abhängigkeiten der Komponenten untereinander werden vom Programmierer definiert, sodass das System später eine korrekte Ausführungsreihenfolge automatisiert auflösen kann. Beispielsweise müssen erst einmal die Spielfeldlinien erkannt werden, bevor die eigene Position geschätzt werden kann. Diese Architektur hat sich über die Jahre etabliert und wird von diversen anderen Teams ebenfalls eingesetzt.
Echtzeitbildverarbeitung
Aufgrund der Kombination einer großen Menge erzeugter Daten – zwei Kameras nehmen insgesamt 60 Bilder pro Sekunde auf – und einem eher leistungsschwachen Rechner kommt der Entwicklung effizienter Algorithmen im Bereich Echtzeitbildverarbeitung eine große Bedeutung zu.
Es werden zwei verschiedene Ansätze zur Verarbeitung der großen Datenmenge genutzt: Zum einen arbeitet man mit SIMD-Techniken (Single Instruction, Multiple Data) und damit Intels SSE-Befehle, um mehrere Pixel gleichzeitig zu verarbeiten, etwa bei der Farbklassifikation. Zum anderen wird die Datenmenge durch eine Unterabtastung des Bildes reduziert. Nur Teile des Bildes, in denen sich die gesuchten Elemente überhaupt befinden können, werden verarbeitet. Diese Teile werden anschließend auch nicht in voller Auflösung untersucht, sondern nur so hoch aufgelöst, dass die relevanten Merkmale erkannt werden.
Damit das funktioniert, ist die Kenntnis der Kamera-Perspektive entscheidend, die mit Hilfe der aktuellen Gelenkwinkelstellungen, der Lageschätzung über den Inertialsensor und dem Wissen um die kinematische Konfiguration des Roboters berechnet werden kann. Diese liefert dann Informationen etwa über die Entfernung von Objekten, deren theoretische Größe im Bild oder über den Verlauf des Horizonts.
Grundlegende Verarbeitungsoperationen sind das Finden von Kanten, die Farbklassifikation von einzelnen Pixeln sowie das Zusammenfassen von farblich gleichen Regionen. Aus diesen Merkmalen werden anschließend Objekte zusammengesetzt: So wird mittels linearer Regression aus einer Reihe von weißen, kleinen Regionen eine Linie und möglicherweise anschließend aus mehreren orthogonal zueinander angeordneten Linien eine Kreuzung.
Alternativ dienen diese erkannten Regionen als Startpunkt für spezialisierte Algorithmen, die einen kleinen Bildbereich mit aufwändigeren Verfahren weiter durchsuchen, um beispielsweise den Ball zu entdecken. Einige Teams wie etwa das Leipziger Nao-Team HTWK setzen auch erfolgreich Deep-Learning-Methoden für die Ballerkennung ein.
Sensoren-Mix
Nicht alle Zustände sind direkt zu beobachten, etwa die Bewegungsrichtung und Geschwindigkeit des Balls oder die eigene Position auf dem Feld. Auch sind Messungen verrauscht und können ein falsches Ergebnis liefern, wenn etwa eine Linie verdeckt wird. Aus diesen Gründen baut jeder Roboter ein Modell seiner Umwelt auf, das die Messungen in einen zeitlichen Zusammenhang stellt.
Basierend auf den Ergebnissen der Echtzeitbildverarbeitung werden Position und Bewegung des Balls, die eigene Position sowie die Positionen anderer Roboter geschätzt. Konkret eingesetzte Schätzer sind dabei die Monte-Carlo-Lokalisierung, die auch multimodale Wahrscheinlichkeitsverteilungen, nichtlineare Bewegungen sowie diskrete Zustandsvariablen handhaben kann, sowie der Unscented Kalman Filter, der effizient eine annähernd optimale Schätzung des Zustands liefert, oder auch eine Kombination aus beiden Verfahren.
Außer den eigenen Beobachtungen kann der Roboter per Funk auch die Messungen der anderen Roboter hinzuziehen, um etwa Fehlschätzungen aufzudecken: Sieht er den Ball an einem komplett anderen Ort als seine Mitspieler, korrigiert er seine Annahme.
Schießen oder Passen?
Nach Objekterkennung und dem Auswerten der Sensordaten hat jeder Roboter ein zweidimensionales Bild seiner Umgebung vorliegen, das nur selten vollständig und korrekt ist, aber in der Regel die eigene Position und die Position anderer Elemente präzise einschätzt. Durch die Kommunikation untereinander sind auch die Positionen der Mitspieler bekannt.
Auf Basis dieser Informationen sind Entscheidungen auf unterschiedlichen Ebenen zu treffen, vom allgemeinen "Bin ich Stürmer oder Verteidiger?" zum speziellen "In welchem Winkel spiele ich den Ball weiter?". Die Roboter sind baugleich und haben weitestgehend dieselben Fähigkeiten, es kann also im Verlauf eines Spiels jeder Roboter jede Position bekleiden. Lediglich die Rolle des Torwarts ist fest zu vergeben.
Bei der Aktionsauswahl werden viele spezialisierte Einzelverhalten definiert und in einem gerichteten, azyklischen Graphen angeordnet, mit den abstrakten Aufgaben wie "Spiele Fußball" nahe der Wurzel und konkreten Aktionen wie "Führe Schuss aus" als Blätter. In jedem Ausführungszyklus durchläuft das System einen Pfad auf diesem Graphen, der am Ende zu einer Aktion führt.
Da alle Roboter eines Teams die gleiche Software ausführen und durch die Kommunikation mit anderen über die gleichen Informationen verfügen, ist die Entwicklung von Gruppenverhalten, die die taktische Positionierung der Spieler definieren und kooperative Spielzüge ermöglichen, einfach umsetzbar.
Dynamische Roboterbewegungen
Zu den Hauptbewegungen im Roboterfußball gehört das Laufen zu einem bestimmten Punkt, das Laufen in einem bestimmten Tempo, das Schießen und das Aufstehen. Daneben gibt es aber auch fest vorgegebene Bewegungsabläufe, wie beispielsweise ein Sprung zum Stoppen des Balls. Dabei stehen Effektivität bei gleichzeitiger Zuverlässigkeit und Flexibilität im Vordergrund.
Insbesondere das stabile humanoide Laufen ist ein Gegenstand vieler aktueller Forschungsarbeiten, auch weit über den RoboCup hinaus. Eine große Herausforderung ist dabei die dynamische Bewegung des Oberkörpers, der einen Großteil der Masse des Roboters ausmacht. Sie erfordert permanente Anpassungen der Schritte, um in Balance zu bleiben. Der bisher verwendete Lauf des Teams B-Human basiert auf einem Modell eines linearen invertierten Pendels, welches die sich bewegende Robotermasse beschreibt. Sehr verbreitet sind auch Lösungen basierend auf dem Zero-Moment-Point-Ansatz.
Durch Einführung eines Untergrunds aus Kunstrasen wird ab 2017 der Bereich Fortbewegung noch anspruchsvoller, da – im Gegensatz zum bisher verwendeten kurzflorigen Filz – die Roboter darauf ausrutschen oder einsinken können. Ein recht erfolgversprechendes Verfahren ist hierbei die Nutzung der Drucksensoren unter den Füßen, um den Zeitpunkt zu bestimmen, zu dem der Lastübergang von einem Fuß auf den anderen tatsächlich stattfindet.
Neuer Rasen, natürliches Licht, gemischte Teams
Zusätzlich zu dem bereits erwähnten Kunstrasen, erwarten die Teams beim RoboCup 2017 in Nagoya noch weitere größere Neuerungen in der Standard Platform League. Nachdem in den vergangenen Jahren bereits schrittweise sämtliche eindeutige Farbzuordnungen für Tore, Ball und Spiele entfernt worden sind, werden nun die allgemeinen Lichtbedingungen flexibler gestaltet. Statt an weitestgehend fensterlosen Plätzen unter Kunstlicht sollen Spiele nun bevorzugt unter natürlichen Lichtbedingungen ausgetragen werden. Der Wechsel zwischen Sonne und Wolken ist dabei eine große Herausforderung für die Robustheit aller Bildverarbeitungsalgorithmen.
Ein neuer und besonders interessanter Nebenwettbewerb ist außerdem die Mixed Team Competition. Sie geht aus der 2014 bis 2016 durchgeführten Drop-in Competition hervor, bei der fünf Roboter aus fünf unterschiedlichen Teams zusammen spielen mussten: Im Mixed Team Competition treten dagegen die Roboter aus zwei Teams gemeinsam gegen ein anderes gemischtes Team an.
Der Wettbewerb soll Verfahren für ein gutes Zusammenspiel mit vorher unbekannten Mitspielern ermöglichen, die andere Software als die eigene ausführen und entsprechend unterschiedliche Fähigkeiten haben können. Hier ergibt sich für den Roboter bei der Auswahl der eigenen Handlungen eine ganz neue, grundsätzliche Fragestellung: Welche Aufgaben traue ich meinen Mitspielern zu und welche übernehme ich besser selbst?
Zudem werden zumindest für die erstmalige Austragung des Mixed Team Competition in 2017 die Paarungen im Vorfeld festgelegt, sodass die Teams vorab Strategien und Kommunikationsprotokolle definieren können. In Nagoya werden zunächst für einen ersten Testlauf vier gemischte Teams an den Start gehen, davon zwei aus Deutschland: DoBerMan (Berlin United – NaoTH + Nao Devils Dortmund) und die B-HULKs (B-Human + HULKs).
Teile dieses Artikels sind entnommen aus: Laue, Tim: Sportrobotik als Benchmark multisensorischer Systeme. In: Witte, Kerstin, Nicole Bandow und Jürgen Edelmann-Nusser (Herausgeber): Sportinformatik XI – Jahrestagung der dvs-Sektion Sportinformatik 2016 in Magdeburg. Shaker, 2016.
Eine Liste mit Hintergrundartikeln und wissenschaftlichen Veröffentlichungen finden Sie auf Seite 2 dieses Artikels.
