Opdracht 4: Pursuer evader

Introductie

In deze Java opdracht gaan jullie een A.I. schrijven die de “Evader” bestuurt in een variant op het “Pursuer Evader” (of Pursuit-evasion) spel. Het gedrag van de evader wordt bepaald door een Self-Organizing Map (SOM) te implementeren, die getraind kan worden door een groot aantal ronden van het spel te spelen. De resultaten worden weergegeven in een tabel of grafiek die het percentage dat de evader wint over een groot aantal ronden weergeeft. Het is de bedoeling dat dit percentage toeneemt naarmate het spel vordert, en dat de evader uiteindelijk zoveel mogelijk ronden wint.

In de Pursuer Evader Tracking (PET) game zijn er twee spelers: een pursuer en een evader. De evader probeert te ontkomen van de pursuer, terwijl de pursuer de taak heeft de evader te pakken te krijgen. Het spel wordt gespeeld op een oneindig groot, twee-dimensionaal veld, waarbij de agents een constante startpositie t.o.v. elkaar hebben, maar een willekeurige startrichting. De spanning in het spel ligt in het feit dat de pursuer zich met een hogere snelheid voortbeweegt, terwijl de evader weer sneller kan draaien.

Extra hint en uitleg

Omdat het niet voor iedereen duidelijk is hoe ze de SOM moeten implementeren en vooral vastlopen op het gedeelte van de 'output', is hier extra uitleg en wat hints.

Qua input: Het aantal dimensies voor de input is een vrije keuze, maar het meest logisch zou zijn om te kiezen voor 2 of 3 dimensies. Deze keuze bepaald naast de input, dan ook het aantal gewichten in de nodes. Bij het kiezen van de inputs is het belangrijk om je af te vragen of de informatie relevant is, er geen of weinig overlap is tussen de verschillende dimensies en of het voldoende informatie is.

Qua output: Naast een x aantal weights, heeft de SOM in dit geval (dus niet zoals bij de voorbeelden in de links hieronder) ook een variabele voor de output. Deze wordt bij het aanmaken van de node geinitialiseerd (op 0, random of via een heuristiek). Op een vergelijkbare manier als de input weights, tellen de outputs alleen mee als ze in de neighborhood van de BMU zit en hoe dichterbij de BMU hoe zwaarder ze meetellen.

Leren: Nadat de outputs zijn geinitialiseerd, wil je ze kunnen aanpassen (dus leren). Dit doe je via een simpel algoritme:
1) Bepaal de wenselijkheid van de situatie waar je nu in zit (fitness functie).
2) Bepaal de output zoals hierboven bepaald.
3) Pas de output van 2 aan via een beetje ruis. Onthoud deze output voor de volgende stap en onthoud de BMU
4) Gebruik de output om de BMU aan te sturen
5) Bepaal opnieuw de wenselijkheid. dan zijn er 2 situaties:
5a) beter: leer
5b) slechter: leer niet Ga daarna verder met stap2

Benodigdheden

• Java 5 of 6 (JDK)
  Een IDE zoals Eclipse (wordt aangeraden).
• De pursuer-evader library (alternatieve versie voor JDK1.5)
• ExampleAI.java, een voorbeeld implementatie van de library
  Javadoc van de library.

Gebruiksinformatie van de Pursuer-evader library

De library bestaat uit een jar file, die je zult moeten importeren in je Java project. We nemen even aan dat je Eclipse gebruikt, maar bij de andere editor zoals Netbeans is de procedure vergelijkbaar.

• Maak een nieuw Java project aan;
• Zet de voorbeeld implementatie (ExampleAI.java) in de src directory;
• Importeer de library als een external library: rechtermuisknop op het project; Properties; Java build path; Libraries, Add external jars;
• Run ExampleAI.java nu als een Applet en het spel begint.

De Applet

Wanneer je de voorbeeld klasse start zal er een Java Applet opstarten die beide spelers laat zien. De pursuer is roodgekleurd en bezit een standaard, hard-coded, AI. De evader loopt in de standaard-implementatie slechts vooruit. Zodra je de applet start zal er meteen een spel beginnen voor vijf ronden. De pursuer probeert de evader te vangen, en heeft hier een bepaalde tijd voor. Als dit hem lukt binnen de tijd dan wint hij, anders wint de evader. Zoals je ziet wint de pursuer lang niet altijd (de winstverdeling is ongeveer 50%-50%), maar de strategie van de evader is verre van optimaal.

In de Applet kun je kiezen tussen verschillende perspectieven. Wanneer je kiest voor het Relative (all) perspectief, zullen de bewegingen van de evader altijd relatief t.o.v. van die van de persuer zijn. De pursuer staat dus altijd op (0,0) en heeft een heading van 0. Deze modus is handig bij het maken van een AI, omdat hij het aantal variabelen reduceert, maar het is niet verplicht om hiermee te werken.

Stappenplan

1. Probeer eerst een simpel algoritme te bedenken (b.v. een aantal if-else statements, random gedrag of iets anders slims) dat het al aardig doet. De besturing van de evader werkt erg eenvoudig: je kunt alleen de hoek aangeven waarmee je wilt dat de evader in de volgende tick van richting veranderd . Doel van deze (sub)opdracht is om bekend te raken met de mogelijkheden van de library. Lees hiervoor eerst de Javadoc van de klassen ExampleAI, GameCommunicator en AgentListener door. Lever deze klasse ook in.

2. Implementeer een Self-Organizing Map algoritme om de opgave op te lossen. We raden je aan om eerst de literatuur over SOM door te lezen, en dan de volgende stappen te nemen. Deze stappen zijn is niet verplicht maar waarschijnlijk wel handig bij het oplossen van de opgave.

   1. Maak een klasse die je gaat gebruiken voor de nodes van je SOM, hierin worden de invoer waarden opgeslagen. Probeer alvast te bedenken welke en hoeveel invoerwaardes je wil gebruiken. Belangrijke vraag om hierbij te stellen is welke informatie relevant is. Deze klasse moet de afstand tot een andere node kunnen berekenen (het is handig om hiervoor de euclidische afstand te gebruiken). Voeg ook alvast functies toe voor het optellen en vermenigvuldigen van 2 nodes, en het vermenigvuldigen van de waardes in de node met een double.

   2. Deze nodes worden in een grid/array gezet om samen de SOM te maken. Maak een klasse die hier voor zorgt en die alle relevante waardes initialiseert. Begin bijvoorbeeld met een array van 15x15 nodes. Dit kun je later veranderen.

   3. Verzin een functie die je een best-matching unit (BMU) oplevert. (zie hiervoor de literatuur)
   4. Gegeven de BMU wil je bepalen welke nodes allemaal in zijn 'neighborhood' zitten en welke niet.
   5. Zorg ervoor dat bij elke trainingspoging de nodes geupdate kunnen worden. Slim hiervoor is om de klasse voor de nodes aan te passen.

3. Zorg er nu voor dat gedurende het lopen van het spel de SOM informatie binnen krijgt om te leren. Het is nog niet nodig om de SOM te output te laten bepalen. Controleer eerst dat de SOM datgene doet wat je ervan verwacht. Een mogelijkheid is om het getrainde netwerk uit te printen om zo de ontwikkeling te zien. De informatie die het SOM binnen krijgt moet er natuurlijk voor kunnen zorgen dat de evader een goede strategie ontwikkelt. Je zou bijvoorbeeld de hoek van de evader t.o.v. de pursuer kunnen gebruiken, en de heading van de evader.

4. Het is de bedoeling dat elke node ook een output bevat en dat hiervoor een optimale waarde geleerd wordt. De waarde die de functie zal teruggeven is het gewogen gemiddelde over de outputs, aan de hand van de geselecteerde node en de neighborhood. De geselecteerde node zal dus de uitvoer voor het grootste deel bepalen, maar de omliggende nodes dragen hier ook aan bij. De output zal de volgende actie van de evader zijn. De output is altijd de verandering in heading in de volgende tick, omdat dit het enige is wat je kunt instellen.

   Om de optimale uitvoer te benaderen, voegen we tijdens het leren elke keer aan de uitvoer wat ruis toe, en kijken we of dit de prestatie heeft verbeterd. Het is handig om hier de volgende stappen te nemen:

   1. Definieer een score-functie die aangeeft hoe goed een bepaalde situatie is. Deze functie hangt af van de waarden die je aan de SOM hebt meegegeven. Een hoge score (of fitness) is positief.
   2. Kies nu de output van je netwerk als het gewogen gemiddelde met behulp van de neighborhood, en voeg hier ruis aan toe. Laat de hoeveelheid ruis afhangen van de learningrate en zorg dat de ruis zowel positief als negatief kan zijn (een willekeurige waarde uit een normaalverdeling zou bijvoorbeeld goed kunnen werken).
   3. Controleer nu elke keer in de output functie of de score sinds de vorige keer beter is geworden. Als dit het geval is, werk dan alle output getallen bij aan de hand van de vorige output (inclusief de ruis) en de neighborhood (waarbij je natuurlijk de node gebruikt die de vorige keer geselecteerd was).

Randvoorwaarden

Hier staat wat moet.* Bij afwijking van randvoorwaarden worden punten in mindering gebracht.

1. Het systeem moet zelflerend zijn, oftewel het moet werkelijk van de simulaties leren. Je mag dus niet de invoer en uitvoer waardes hardcoden (maar bepaalde parameters erin zetten mag natuurlijk wel).
2. Jouw programmacode moet in goed, idiomatisch Java geschreven worden. Dit betekent correct gebruik van classes, interfaces, overerving, etc. De parameters van zowel de evader als de pursuer worden aan het begin van elk spel met een random term vermenigvuldigd; zorg dus dat je netwerk hierop berekend is;
3. Het netwerk mag enkel getraind worden door het spel zoals het in de library staat.
4. De SOM implementatie is tot op zeker mate modulair en redelijk makkelijk uit te breiden naar een andere leeralgoritme zonder de structuur van het netwerk fundamenteel aan te moeten passen.
5. Testresultaten in de vorm van tabellen en/of plots.
6. Testresultaten moeten reproduceerbaar zijn door middel van instructies. Geef hiervoor geschikte documentatie.

Inleveren

Je wordt geacht om de volgende stukken in te leveren:

1. Een zip/rar bestand met de volgende subdirectories:
2. /src/ De java code (bij voorkeur onderverdeeld in packages)
3. /doc/ Een doc/pdf bestand waarin je je ontwerpbeslissingen motiveert en enkele uitkomsten van je programma beschrijft

• SOM tutorial
• SOM example
• Example of use SOM
• Oude IAS opdracht met SOM