Vorstellung des Roboterfußball-Teams TORF (Vortrag)

C A R LV O N

O S S I E T Z K Y

Vorstellung desRoboterfußball-TeamsTORF

Johannes Diemke

Vortrag im Rahmen der ProjektgruppeOldenburger Robot Soccer Teamim Wintersemester 2009/2010

Ubersicht

1 Motivation

2 Grundlagen

3 Vorarbeiten der PG TORF

4 Fazit

Johannes Diemke Teamvorstellung TORF 10. November 2009 2/48

Motivation

Zielsetzung der PGVerbesserung des bestehenden Roboterfußball-Teams TORF

I Umfassende VorarbeitenI Auszeichnung

”Beste PG des Jahres“

Teilnahme an den RoboCup German Open 2010

Voraussetzung

Kenntnisse unterschiedlicher KI-Techniken

Verstandnis der vorhandenen Architektur und Funktionsweise

I Fahigkeiten und Restriktionen erkennenI Verbesserungspotential erkennen


Motivation

PG TORF - Das alte Team

(Quelle: Projektgruppe TORF)


Vom Computerschach zum Roboterfußball

1950

Claude E. Shannon schlagt Automaten vor der Menschen im Schachschlagt

Fortan Prufstein fur neu entwickelte Verfahren

Entstehung leistungsfahiger Spielstrategien und Suchverfahren

1995

Computerschach war bereits kein Prufstein mehr fur KI

Roboterfußball wird das neue Standardproblem

1996

Deep Blue gewinnt gegen den Schachweltmeister Garri Kasparov


Vom Computerschach zum Roboterfußball

IBMs Deep Blue vs. Kasparov

(Quellen: http://www.ibm.com/ & http://www.theinsider.com/)


http://www.ibm.com/

http://www.theinsider.com/

Roboterfußball

Besonderheiten des Roboterfußballs

Herausforderung fur Robotik und KI

Vollig andere Aspekte als beim Computerschach

I Dynamische UmgebungI Unvollstandige InformationenI EchtzeitanforderungenI Unvorhersehbare EreignisseI . . .


Roboterfußball

Weitere Vorteile des Roboterfußballs

Populare Sportart

Einfaches und bekanntes Regelwerk

Leistungsfahigkeit von Verfahren lasst sich einfach messen:

I Erzielte ToreI Platzierung

Evolution der Verfahren durch Wettkampfe

I RoboCupI Federation of International Robot-Soccer Association (FIRA)


RoboCup

Die internationale RoboCup-Initiative

Veranstaltet seit 1997 den RoboCup

Roboterfußball Weltmeisterschaft

RoboCup German Open in Deutschland

Verschiedene Ligen:

I 2D Simulation / 3D SimulationI Small SizeI Four Legged (Aibo) / Standard Platform League (Nao)I HumanoidI . . .


RoboCup

Zielsetzung der RoboCup-Initiative

Bis zum Jahr 2050 den amtierenden menschlichen Weltmeister ineinem gewohnlichen Fußballspiel besiegen

(Quelle: http://www.welt.de/)


http://www.welt.de/

RoboCup

Die 2D-SimulationsligaGespielt wird auf RoboCup Soccer Simulator Server

I Spieler verbinden sich als ClientI Ubernimmt vollstandige Simulation

Zwei Teams aus je 11 autonomen Spielern + Coach

Jeder Spieler ist ein autonomer Software-Agent

Agenten nach Russell & Norvig

Definition

Als Agent kann alles angesehen werden, was seine Umwelt durchSensoren wahrnimmt und durch Effektoren beeinflusst.


RoboCup

RoboCup Soccer Simulator

Simulator ist gemaß Client-Server-Architektur ein Server

Angebotener Dienst ist die Simulation:

I Verwaltung der Spieler und des BallsI Simulation einfacher PhysikI Visuelle und auditive WahrnehmungI Simulation von Beschrankungen (Verrauschen, partielle

Beobachtbarkeit)

Spieler, Coach und Trainer melden sich an

Kommunikation uber S-Expressions

Verwendet wird das UDP/IP-Protokoll


Arbeitsumgebung

Klassifikation der Arbeitsumgebung

Erfolgt nach PEAS-Beschreibung (Russell & Norvig)

Akronym fur Performance, Environment, Actuators, Sensors

Besteht aus:

I Beschreibung der ArbeitsumgebungI Umgebungsklassifikation

Ziel

Dient Ableitung erster Anforderungen an einen Software-Agenten


Arbeitsumgebung

Beschreibung der Arbeitsumgebung

Agententyp Leistungsbe-wertung

Umgebung Aktuatoren Sensoren

Spieler Stabilitat, Ge-schwindigkeit,kongruentesVerhalten

RoboCupSoccer Server

Spielerkom-mandos (dash,turn, say, . . . )

Sehen undHoren

Trainer Stabilitat, Ge-schwindigkeit

RoboCupSoccer Server(im Trainings-modus)

change mode,move, start,say, . . .

Spielfelduber-sicht

Coach Stabilitat, Ge-schwindigkeit

RoboCupSoccer Server

say, look, eyes,team names,. . .

Spielfelduber-sicht

(Quelle: Abschlußbericht PG TORF)


Arbeitsumgebung

UmgebungsklassifikationAnhand folgender Eigenschaften:

I Vollstandig vs. teilweise beobachtbarI Deterministisch vs. stochastischI Episodisch vs. sequentiellI Statisch vs. dynamischI Diskret vs. stetigI Einzelagenten vs. Multiagenten-Umgebung

Erste Schlusse bzgl. der Anforderungen

I Verwaltung eines inneren Zustandes (Weltmodell)I Keine absoluten Aussagen uber Folgezustande (Wahrscheinlichkeiten)I VorausdenkenI Veranderung der Umgebung wahrend der Entscheidungsfindung


Agenten

Spieler als modellbasierter Reflex-Agent

Teilweise Beobachtbarkeit macht Verwaltung eines Zustandesnotwendig

(Quelle: Russell & Norvig)


Vorarbeiten der PG TORF

Komponentenmodell des Spieler-Agenten




Das Weltmodell



Das Weltmodell

Zweck

Grundlage des Entscheidungsprozesses

Besitzt Ist-Zustand und Dynamikwissen

Moglichst korrekte Abbildung der Arbeitsumgebung

Umgang mit verrauschten Daten

Erfassung von:

I Objekten (Spieler, Ball, Flaggen, . . . )I Punktestand und Spielphase


Das Weltmodell

Bestimmung der eigenen Position

Durch Winkel und Entfernungen der Flaggen

Unterscheidung zweier Falle (a) und (b)

(a) Zwei Flaggen. (b) Eine Flagge.



Das Weltmodell

Bestimmung der eigenen Position (Forts.)

Berechnete Positionen sind verfalscht

Sensordaten werden kunstlich verrauscht



Das Weltmodell

Bestimmung der eigenen Position (Forts.)Verringerung der Verfalschung:

I Bildung von FlaggenpaarenI Schatzung durch das [sic] Kalman-Filter

Sind keine Flaggen sichtbar:

I Bestimmung uber Dynamik des Kalman-Filters


Das Weltmodell

Grafische Darstellung des Weltmodells




Der Planer



Der Planer

Zweck

Umsetzung des Entscheidungsprozesses

Festlegen der Strategie und das Starten der Skills

Hierarchischer Planer

Benotigt Planerdatenbank mit Domanenwissen

Zugriff auf das Weltmodell uber Literale

Unterstutzung von Team-Skills


Der Planer

Die Planer-Architektur

play soccer

offensiv

set piece

free kick

start Skill

Messages

state (via literals)

select methodstatus

push /

pop

play soccer

offensiv

defensive normal play

Planner

Com

Worldmodel

Database

Stack



Der Planer

Auschnitt der Planerdatenbank

BallPossessionHandling

kick2GoalComplex

NearestToBall

Do Positioning, Offensive

DoPositioningSkillParam

lookAround

LookAroundSkillParam

Negation of (NearestToBall)

NearestToBall

intercept

InterceptSkillParam

kickToGoal

Kick2PosSkillParam

NearestToBall

NearestToBall

Negation of (NearestToBall)




Skills



Skills

Zweck

Realisierung grundlegender Fertigkeiten

Verwaltung durch Skill-Manager

Unterscheidung von zwei Arten

I Primitive Skills (kapseln S-Expressions)I Komplexe Skills

Handische Implementierung nicht trivial

Einsatz von Lernverfahren bietet sich an


Skills

Hierarchische Struktur der Skills

PlayerSkillspackage Data[ ]

doKickOffFormatio

ProbabilisticGoalie

TurnHeadComplex

CatchComplex

doPositioning

PlayerSkills

teleport2Pos

changeView

lookAround

receivePass

findObjec

followPath

turnHead

intercept

turnBody

kick2Pos

stopBall

dribble

go2Pos

doPass

goalie

catch movedashsay kick



Skills

Aktivitatsdiagramm fur den Go2Pos-Skill




Kommunikation



Kommunikation

Zweck

Absprachen zwischen Spieler-Agenten (Taktiken auf Teamebene)

Beispiel: Passspiel

Spieler-Agent empfangt nicht jede Nachricht:

I Maximale EntfernungI eingeschrankte NachrichtenlangeI Vorgegebenes Alphabet ΣI Erste Nachricht je Simulations-Zyklus


Kommunikation

Implementiertes Verfahren

Einteilung in Cluster mit je einem Router

Verwendung von Zeitmultiplexing (Vermeiden von Kollisionen)

Problem

Derzeit nicht vollstandig funktionsfahig

Aufgabe

Protokoll auf Korrektheit prufen

Gegebenenfalls Alternativen entwerfen


Trainer- und Coach-Framework

Aufbau

Trainer und Coach sind eine Applikation

Gemeinsamkeiten:

I Message-BrokerI WeltmodellI Controller

Trainer

Nach Sternarchitektur aufgebaut

Trainiert Spieler

Austauschbare Lerntechniken (KI-Module)

Laden von Spielsituationen im XML-Format



Sternarchitektur des Trainers




Gemeinsame Architektur von Trainer und Coach

!""#-$"-!! /!%Projektgruppe TORF – Universität Oldenburg • Fakultät II • Department für Informatik • Abteilung LLS

Architektur des Trainer-Agenten

$#

Trainer-Agent

Spieler-AgentTrainee/LT

Learning-Technique

XML-Situation

Coach-Agent

BasicCoach

RCSS-Server WorldModel

Message-Broker

Controller

Player-Types …

DatenflussVererbung




Ablauf einer Trainingssession und des Trainings

MagicDraw UML, 1-1 /Users/stefan/Documents/Studium/7/PG/sprint/20080101/trainer-coach/Trainer.mdzip Trainer 27.02.2008 14:42:08

Academic Use Only

activity Trainer Trainer[ ]

Training

durchführen

Client

aufnehmen

Lernergebnisse

speichern

Clients

verabschieden

WM verbindenMB verbinden

LT abmelden

Bei LT

registrieren

Auf Clients

lauschen

aufräumen

init LTLT laden

zu wenig Clients

Genug Clients

MagicDraw UML, 1-1 /Users/stefan/Documents/Studium/7/PG/sprint/20080101/trainer-coach/Trainer.mdzip Training durchführen 27.02.2008 14:42:08

Academic Use Only

Training durchführenactivity Trainer[ ]

Ergebnisse von

Spieler empfangen

Instruktionen

an Spieler senden

Lerntechnik

starten

Spieler

beobachten

Ergebnisse

auswertenTraining beendet

Training nicht beendet

(Quelle: Abschlußbericht PG TORF)Johannes Diemke Teamvorstellung TORF 10. November 2009 38/48


CoachVergibt momentan nur Spielertypen

I 18 zufallig generierte SpielertypenI Werden nach Zufallsprinzip vom RCSS zugewiesenI Coach kann diese neu zuweisenI Data-Mining fur optimale Heuristik (LogfileAnalysis)


Hilfsprogramme

TORF Strategy ToolManuelle Erstellung der Planderdatenbank zu aufwandig

I Boost-Serialisierung (Metadaten)

Umfang des Domanenwissens entscheidend

Intention

Komfortable Erstellung von Planerdatenbanken

Visuelle Darstellung der Daten

Schnelle Entwicklung mittels der NetBeans Platform 6.1

I Anbindung an Planer uber das JNI mittels SWIG


Hilfsprogramme

Hauptfenster des TORF Strategy Tool



Hilfsprogramme

Probleme

Interoperabilitat zwischen Java und C++

Aus der Verwendung von SWIG resultieren einige Probleme:

I Verlust von PolymorphieI Speicherverwaltung (keine Destruktion auf C++-Seite)I . . .

Mogliche Problemlosung

Entwurfsentscheidungen uberdenken


Hilfsprogramme

LogfileAnalysis

Sammlung von Python-Skripten

Auswertung von Logdateien

I Enthalten kompletten Spielverlauf

Offizielle Spiele ab dem Jahr 1997 verfugbar

Pradestiniert fur Analysezwecke mittels Data-Mining


Hilfsprogramme

Feldabdeckungsanalyse



Hilfsprogramme

Torschussanalyse




Fazit

Umfangreiche Vorarbeiten der PG TORF

Handlungsumgebung sehr komplex

Grobarchitektur ist gute Grundlage fur Erweiterungen

Leistungspotential des Planers besser ausschopfen

I Fehlendes Domanenwissen



Fazit (Forts.)Weitere Skills implementieren

I Nutzen von Lernverfahren

Fertigstellung der Kommunikations-Komponente

Erweitern des Trainer und Coach-Frameworks:

I KI-ModuleI Umfangreichere Unterstutzung durch den Coach

TORF Strategy Tool

I Entwurfsentscheidungen uberdenkenI Probleme beseitigen


Literatur

� Universitat Oldenburg, Projektgruppe TORFTeam Oldenburger Robo-Fußball – Abschlussberichthttps://torf.uni-oldenburg.de/

� The RoboCup FederationRoboCuphttp://www.robocup.org/

� Stuart Russell und Peter NorvigKunstliche Intelligenz: Ein moderner Ansatzhttp://aima.cs.berkeley.edu/

� IBM CorporationDeep Bluehttp://www.ibm.com/


https://torf.uni-oldenburg.de/

http://www.robocup.org/

http://aima.cs.berkeley.edu/

http://www-03.ibm.com/ibm/history/exhibits/vintage/vintage_4506VV1001.html

Technology

Vorstellung des Roboterfußball-Teams TORF (Vortrag)