Opdracht 3: Genetisch Programmeren

Inleiding

In een publicatie van Mataric uit 1990 wordt het probleem behandeld van een robot, genaamd TOTO, die langs de muur van een kamer dient te wandelen met behulp van 12 sonars die hem helpen zijn locatie te bepalen in de kamer. Mataric is het uiteindelijk gelukt om met 4 basale gedragscomponenten (Stroll, Avoid, Align, Correct) het gewenste gedrag van TOTO te modelleren. Wij gaan proberen in deze opdracht met behulp van genetisch programmeren (een enigszins versimpelde versie van) het probleem op te lossen, waarbij het gewenste programma door evolutionaire processen (selectie, mutatie, crossover, etc.) tot stand komt.

Benodigdheden

1. NetLogo 4
2. Het NetLogo TOTO programma.
3. jGE NetLogo extension v2.0 (inclusief documentatie) (mirror).

Globale omschrijving

Leer TOTO zoeken met genetisch programmeren.

Randvoorwaarden

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

1. Zorg dat je programma beschikt over een geschikte BNF. In deze opdracht zijn er strikte eisen aan de BNF: een programma bestaat uit een aaneenschakeling van nul of meer functie-aanroepen. De robot TOTO heeft in deze versie van het probleem slechts keuze uit de volgende vijf functies:
   • TL (deze functie draait de robot 30 graden naar links);
   • TR (deze functie draait de robot 30 graden naar rechts);
   • MF (deze functie verplaatst de robot 100% van de stapgrootte naar voren);
   • MB (deze functie verplaatst de roboto 130% van de stapgrootte naar achteren);
   • if-else(<bool>), waarbij <bool> bestaat uit <op> <var1> <var2>. Hier bestaat <op> uit smaller-than of greater-than en <var1> respectievelijk <var2> uit S00,S01,...,S10 of S11 (sonar variabelen).
2. Zorg dat je programma beschikt over een geschikte fitness functie. De fitness van een gegenereerd programma hangt af van de globale variabelen food-left en time-left. Er zijn 60 food pellets langs de rand van de kamer verspreid; een programma dat meer verzamelt is altijd beter dan een programma dat minder verzamelt. De robot krijgt 400 tijd frames om deze 60 food pelletes te verzamelen; als de tijd op is of alles is verzameld eindigt het programma. Een programma dat sneller alles verzamelt is altijd beter dan een programma die langzamer (d.w.z. met minder time-left) eindigt. Tevens is er nog een variabele patches-visited die bijhoudt hoeveel van het grid verkend is tijdens een run. Het is aan jullie om te bepalen of deze variabele nuttig is om te gebruiken in de fitness functie (mits natuurlijk is voldaan aan de 2 eerder genoemde eisen).
3. Zorg dat je programma beschikt over een geschikt genetisch algoritme, die met behulp van je geschreven BNF taal een populatie aanmaakt en kan kruisen. Materiaal aangeboden op het college bevat flowcharts waarop de globale werking van een genetisch algoritme wordt gespecificeerd.
4. Zorg dat parameters voor het genetisch algoritme instelbaar zijn voor de gebruiker. Denk aan de populatie-grootte, het aantal generaties, en de kruisingskansen. Zorg ook dat het beste programma wordt onthouden en dat deze kan uitgevoerd worden als de gebruiker daar om vraagt.
5. De documentatie is erg belangrijk. Leg goed uuit wat het programma doet, hoe het werkt, wat geschikte parameters zijn en hoe het verbeterd kan worden.
6. De vijf primitieve functies van TOTO en de layout van de kamer mogen niet aangepast worden, zie voor de precieze werking van de simulatie het kopje 'Simulatie'. In principe is het wel mogelijk (maar zeker niet verplicht!) om extra variabelen toe te voegen voor de fitness functie (zolang deze zich in ieder geval gedraagt volgens de twee eerder genoemde eisen).
7. Er mag niet afgeweken worden van de JGE extensie.

Extra

Extra punten kunnen worden verdient door het aanbrengen van de volgende features.

1. Werking. Je model moet in de allereerste plaats goed werken. Hoe laat je dat zien? Dat kan door eerst een goed gedocumenteerde en duidelijk geoperationaliseerde definitie (maat) voor de effectiviteit van adaptatie op te stellen. Maak grafieken (zoals een plot van de fitness van het beste individu tot dan toe).
2. Overzichtelijkheid. Zorg dat je programma overzichtelijk is. Probeer je programma niet te complex te maken.
3. Optimaliteit. Een programma wat goede oplossingen vindt in weinig tijd wordt beter gewaardeerd.
4. Modulariteit. De robot start altijd op dezelfde locatie met dezelfde heading. Goede oplossingen voor dit probleem kunnen over het algemeen weinig modulair zijn; als het programma met een andere heading en/of op een andere locatie start kan het ineens totaal misgaan (in het algemeen het probleem van "overfitting"). Verken/implementeer mogelijkheden om dit probleem tegen te gaan.

Aanpak

Een mogelijke globale aanpak voor het probleem is als volgt:

1. Begin met het maken van een BNF. Het TOTO programma bevat 2 demo's (selecteer een knop, en klik "edit"), hieruit kan je afleiden wat de syntax is van de programma's.
2. Probeer in NetLogo met de JGE extensie een populatie van willekeurige genotypen te laten maken, en probeer deze ook om te zetten naar fenotypen met behulp van de gemaakte BNF.
3. Maak een fitness functie, en probeer een functie te maken die een willekeurig genotype omzet naar een fitness waarde. Om de fitness van een genotype te bepalen werk je als volgt:
   1. Zet het genotype om naar een fenotype door middel van de BNF.
   2. Plug het gegenereerde programma in simulate, bijvoorbeeld: 'simulate "MF" true' plugt het programma "MF" en voert deze onzichtbaar uit. Nog een voorbeeld is 'simulate "" false' wat het lege programma laat zien (wat resulteert in een stilstaande robot).
   3. Bepaal vervolgens met variablen als 'food-left' en 'time-left' de uiteindelijke fitness waarde.
   Maak nu functies om de fitness van alle individuen in een populatie te bepalen. Vanaf dit punt is het mogelijk om daadwerkelijk een flowchart te implementeren.

Verdere tips

1. De documentatie van de JGE extensie bevat een voorbeeldprogramma waarin enkele functies van de library worden gedemonstreerd.
2. Zet de snelheid van het programma lager om de simulatie daadwerkelijk goed te kunnen zien.
3. Het aanroepen van 'to simulate [prog hidden]' is het hoofdingrediënt voor het bepalen van de fitness van een individu.
4. De JGE extensie is spatiegevoelig als het gaat om genereren van een programma uit een genotype met behulp van het BNF. NetLogo heeft hier over het algemeen geen problemen mee
5. Met name Fig. 2.2 uit Hoofdstuk 2 van I. Dempsey et al. (2009) Grammatical Evolution is zeer verhelderend. (Chapter 2 uit: Foundations in Grammatical Evolution for Dynamic Environments, SCI 194, pp. 9-24. Springer-Verlag.)

Simulatie

Nog wat extra details over de simulatie (niet nodig voor het maken van de opdracht).

1. De 12 sonar variabelen die de robot tot zijn beschikking heeft corresponderen met de afstand van de robot tot de muur om de robot heen. S00 correspondeert met de afstand van de robot tot de muur onder een hoek van 0 graden, S01 hetzelfde onder een hoek van 30 graden, etc. Dit is misschien het beste te illustreren met het volgende plaatje:

   

2. De state van de robot wordt volledig bepaalt door zijn X,Y locatie en zijn 12 mogelijke headings.
3. Er zijn 1413 bewandelbare patches. De voorwaartse snelheid van de robot is de lengte van een patch, en de achterwaartse snelheid de lengte van een patch maal 1.3. Als de robot dreigt in een muur te crashen gebeurt er niks (behalve dat er een tijd-frame voorbij gaat).