Learning a Multiagent Behavior

Pass Evaluation

Problemstellung

Ziel:

Möchte ein Spieler den Ball zu

einem Mitspieler passen, so soll er

aus einer Reihe von Merkmalen,

die seine Umgebung beschreiben,

jenen bestimmen, zu dem ein Pass

am wahrscheinlichsten erfolgreich

ist.

Play Tennis or not ?

Wie funktioniert ein DT ?

• Ein Beispiel (bestehend ausMerkmalen) wird einer Klassezugeordnet.

• Blätter sind Klassen

• In Knoten wird über einMerkmal entschieden und jeNach Ausgang im Baumverzweigt.

Voraussetzungen für DT learning

• Attribute - value descriptiondiskret oder numerisch, aber für alle Beispiele gleich

• Vordefinierte Klassensupervised learning, z.B. {good, bad}

• Diskrete Klassen1 Beispiel gehört genau 1 Klasse an

• Genügend TrainingsdatenUnter den Trainingsbeispielen muß sich ein Muster abzeichnen

• Logisches Modell

Decision Tree algorithmus C4.5

• Nachfolger des ID3

• Literatur

Quinlan, J. Ross (1993). C4.5: Programs for Machine LearningC4.5 / Beschreibung der Software (incl. Source) und dessen

Anwendung

Mitchell, Tom M. (1997). Machine Learningu.a. Decision Tree Learning (Grundlagen, ID3)

• WWWwww.cse.unsw.edu.ac/~quinlan (C4.5)

Merkmale des C4.5

• Algorithmus wählt die Merkmale, nach denen sich der Baum verzweigt.

• Kontinuierliche Merkmale sind möglich, wobei der Algorithmus den optimalen Schwellwert auswählt.

• Neben der Klassifizierung kann zu jeder Klasse ein Erwartungswert für ungesehene Beispiele berechnet werden.

Trainingssituation CMU

1. Der Passer ist in Ballbesitz und steht in der Mitte des Spielfeldes.2. Darunter werden in einem vorgegebenen Bereich 3 Mitspieler und 4

Gegenspieler zufällig plaziert.3. Der Passer gibt bekannt, daß er abspielen möchte.4. Alle Mitspieler übermitteln dem Passer eine Reihe von Merkmalen,

der sie zusammen mit von ihm wahrgenommenen Merkmalen speichert.

5. Der Passer wählt einen Mitspieler aus und teilt ihm mit, daß er den Ball empfangen soll.

6. Der Ballabgabe wird durchgeführt, wobei die Gegner und der Empfänger versuchen den Ball abzufangen.

7. Der Passer klassifiziert das Ergebnis und legt die gesammelten Merkmale als gutes oder schlechtes Beispiel ab.

Trainingssituation CMU

ErweiterungEs werden 2 zusätzliche Gegner mit einem Abstand zwischen 2 und 10

vom Passer plaziert. Dadurch soll simuliert werden, daß der Abspieler von

Gegnern bedrängt oder blockiert wird.

Anmerkung: Alle Spielersind mit dem „pass interception“-skill des 1. Layers ausgestattet.

Input Merkmale (1/2)jeweils von Passer und Empfänger

Beobachtung des eigenen Umfeldes:• Distanz und Winkel zum Empfänger

• Distanz und Winkel zu Mitspielern

• Distanz und Winkel zu Gegnern

• Spielerverteilung für {2,4,6,8,10,12}

... relativer Sichtwinkel

Input Merkmale (2/2)jeweils von Passer und Empfänger

Beobachtung des Umfeldes des jeweils anderen Beteiligten• Spielerverteilung (Mitspieler/Gegner/Gesamt) für , {4,8,12}

... relativer Sichtwinkel

... relativer Abstand

Klassifikation

Wurde ein Ball erfolgreich gestoppt, wird er in Richtung gegnerisches Tor gekickt, woraus der Passer den Ausgang des Beispiels erkennt.

Problem: Der Ball kann mit einem anderen Spieler kollidieren.Lösung: Der Spieler sucht nach dem

maximalen Winkel zwischen 2 Spielern.

Anmerkung: Aufgrund fehlender visueller Information kann dieser Fall trotzdem eintreten.

Synchronisation (Passer)

1. (PLAY_MODE_PLAY_ON) and (ball_kickable) t0 = time2. (time > t0 + 5) SAY(I_WANT_TO_PASS) / t1 = time3. (time > t1 + 20) and (receiver found) randomize receiver4. (time > t1 + 20) and (no receiver answered)5. HEAR(READY_TO_RECEIVE) process data / kick

SHOOTER_WAITING while(time < t1+20) receive data from teammates

SHOOTER_SHOOTINGSAY(PASSING_TO_YOU) + wait for (READY_TO_RECEIVE)

SHOOTER_FINISHEDface ball and classify result {success, failure, miss} tell coach to start again / reset

Synchronisation (Receiver)

1. Is member of „Team1“2. HEAR(I_WANT_TO_PASS) t1 = time3. (Player faces ball) and (data sent)4. HEAR(I_WANT_TO_PASS) t1 = time5. HEAR(PASSING_TO_YOU) delay 1 step SAY(READY) / t2 = time6. no ball movement for 15 steps7. Ball interception failed8. Ball interception successful9. Ball shot towards opposite goal

RECEIVER_ANSWERINGtry to face ball in 8 steps + send data at time (t1 + 8 + 2*myNumber)

example

DT training

Das Trainingsset, bestehend aus 5128 Beispielen

(2973 good, 2155 bad), setzt sich wie folgt zusammen:

3248 Beispiele: 3 Mitspieler, 4 Gegner, 2 Gegner im Umkreis des Passers

900 Beispiele: 3 Mitspieler, 4 Gegner

980 Beispiele: 3 Mitspieler, 4 Gegner, Merkmale des Empfängers fehlen

Offene Frage: Wie wirkt sich eine Veränderung der Zusammensetzung

der Trainingsdaten auf den Entscheidungsbaum aus?

example

Ergebnis (1/2)

• Original Tree1281 nodes

Error on training set 10,2 %

• Pruned Tree77 nodes

Error on training set: 15,3 %

• Pruned Tree CMU:87 nodes

Error on training set: 26 %

Ergebnis (2/2)

0

100

200

300

400

500

600

700

examples

Decision Tree Estimation

Failure

Miss

Success

Fehlerquellen

• Kommunikationsfehler

• Ballverlust nach erfolgreicher Annahme

• Schlechte Passannahme (NN)

• Falsche Entscheidung des DT

example