Java opdracht: Pole Balancing

Introductie

In deze Java opdracht is het de bedoeling om een algoritme te schrijven dat zo goed mogelijk een variant van het zogenaamde Pole Balancing probleem oplost. Dit probleem kan als volgt worden omschreven:

De wereld bestaat uit een kar (in ons geval een golfkar) waarop een verticale paal staat (in ons geval een palmboom). De paal zit met een scharnier vast aan de kar, en kan naar links en rechts vrij bewegen. Als de kar dus stil blijft staan, zal de paal onder invloed van de zwaartekracht omvallen. Om dit echter tegen te gaan kan de kar naar links of naar rechts bewegen en zo de paal in evenwicht houden. De bedoeling is dat het algoritme, gegeven de hoek en snelheid van de paal, de kar beweegt en daarmee de paal in evenwicht houdt.

Opdracht

Voor het oplossen van deze opdracht krijg je van ons een simulator (zie technische details). Deze simulator simuleert de vallende paal en de kar, en toont een grafische representatie hiervan op het scherm. Het enige dat jouw code hoeft te doen is een interface implementeren, met een functie die gegeven de hoek en de hoeksnelheid van de paal bepaalt welke kracht er op de kar uitgeoefend moet worden. Lees eerst de hele opdracht en de technische details goed door voordat je begint.

1. Probeer eerst een simpel algoritme te bedenken (b.v. een aantal if-else statements) dat het al aardig doet. Kun je met een paar simpele regels een programma maken dat het beter doet dan je zelf kunt met de pijltjestoetsen? Lever deze klasse ook in.

2. Implementeer een Self Organizing Map (SOM) algoritme om de opgave op te lossen. Je code moet aan de volgende voorwaardes voldoen:
   • 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).
   • Zie verder de pagina met clausules voor de programmeeropgaven.
   
   We raden je aan om de volgende stappen te nemen, dit 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 waardes (2 double waardes) opgeslagen. Deze klasse moet de afstand tot een andere node kunnen berekenen (het is handig om hiervoor de euclidische afstand te gebruiken). Voeg ook vast functies toe voor het optellen en vermenigvuldigen van 2 nodes, en het vermenigvuldigen van de waardes in de node met een double.

   2. Probeer nu in de provideForce functie een SOM te maken die de invoer netjes verdeelt over de nodes. Laat voorlopig nog even return 0; staan, zodat de paal gewoon omvalt en van de verschillende oriëntaties van de paal geleerd kan worden. Doe dit als volgt:

      1. Maak in de constructor van je controller een 2-dimensionale array van nodes aan, en initialiseer ze op random waardes. De grootte mag je zelf bepalen, maar een vierkant netwerk van 10 bij 10 lijkt goed te werken. Dit kun je natuurlijk later nog aanpassen.
      2. Definieer een neighbourhood-functie die gegeven de locatie van 2 nodes bepaalt hoe sterk ze verbonden zijn. Zoek in de literatuur over SOMs een naar een geschikte functie.
      3. Zorg nu dat elke keer dat de provideForce functie wordt aangeroepen, de nodes worden geupdate. Selecteer eerst de node met de kleinste afstand tot de invoer, en update vervolgens alle nodes door ze een stukje dichter naar de invoer toe te bewegen, afhankelijk van de grootte van de neighbourhood-functie en een leerparameter alpha.
      Ter controle kun je in de endTraining functie het geleerde netwerk uitprinten, om zo handmatig te controleren of eruit komt wat je zou verwachten.

   3. Vervolgens moet de uitvoer geleerd worden, zodanig dat er bij elke node in je SOM een uitvoer getal hoort. De waarde die de provideForce functie zal teruggeven is het gewogen over de outputs, aan de hand van de geselecteerde node en de neighbourhood-functie. De geselecteerde node zal dus de uitvoer voor het grootste deel bepalen, maar de omliggende nodes dragen hier ook aan bij.

      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 moet dus afhangen van de oriëntatie en snelheid van de paal, en hoger worden naarmate de paal meer in evenwicht is.
      2. Kies nu de output van je netwerk als het gewogen gemiddelde met behulp van de neighbourhood-functie, en voeg hier ruis aan toe. Laat de hoeveelheid ruis afhangen van alpha 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 provideForce 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 neighbourhood-functie (waarbij je natuurlijk de node gebruikt die de vorige keer geselecteerd was).

Technische Details

Uitvoeren

Download hier het jar-bestand met de simulator. Om deze te runnen gebruik je:

java -jar PoleBalancing.jar <ControllerNaam>

waar <ControllerNaam> de naam is van de controller die je wilt gebruiken. Gebruik bijvoorbeeld:

java -jar PoleBalancing.jar nl.uu.cs.ias.cartpolebalancing.controllers.KeyController

en je kunt met de pijltjestoetsen sturen. Ook zit er een simpele voorbeeld oplossing bij die het even volhoudt (nl.uu.cs.ias.cartpolebalancing.controllers.DummyController).

Eigen implementatie

Om zelf een controller te bouwen moet je de interface nl.uu.cs.ias.cartpolebalancing.service.CartPoleController implementeren. De implementatie moet de volgende 4 functies implementeren:

• public void startSimulation();
  Deze functie zal worden aangeroepen aan het begin van elke simulatie, en kan gebruikt worden om bepaalde waardes goed te zetten (bv het ongedaan maken van bepaalde trainingsparameters).
• public void startTraining(int step, int totalSteps);
  Deze functie zal worden aangeroepen aan het begin van elke trainingssimulatie, en kan gebruikt worden om bepaalde trainingsparameters goed te zetten. step geeft het volgnummer van de huidige simulatie aan aan (in de range van 0 tot en met totalSteps-1). totalSteps geeft het totaal aantal trainingssimulaties aan.
• public void endTraining();
  Deze functie zal worden aangeroepen aan het einde van alle trainingssimulaties en kan gebruikt worden om waarden te herstellen of bijvoorbeeld debug-informatie te printen.
• public double provideForce(CartPoleStatus currentStatus);
  Deze functie zal 20 keer per seconde worden aangeroepen tijdens de simulaties, en is de belangrijkste functie. De return waarde geeft aan hoeveel kracht (in Newton) er op de kar uitgeoefend zal moeten worden, waarbij een negatief getal betekent dat de kar naar links moet bewegen en een positief getal dat de kar naar rechts moet bewegen. De klasse CartPoleStatus bevat de volgende functies die je kunt gebruiken om informatie over de paal en de kar te verkrijgen:
  • currentStatus.getCartPosition()
    Deze functie geeft de positie van de kar aan in meters. Aangezien deze simulatie werkt met een oneindig lange wereld kan dit in principe alle waardes aannemen.
  • currentStatus.getPoleAngle()
    Deze functie geeft de hoek van de paal weer in graden radialen. De range zal liggen tussen -0.5 * π en 0.5 * π, waarbij een negatief getal aangeeft dat de paal naar links overhelt, een positief getal dat paal naar rechts overhelt, en 0 betekent dat de paal precies rechtop staat.
  • currentStatus.getPoleAngularVelocity()
    Deze functie geeft de hoeksnelheid van de paal weer, in graden radialen per seconde. Omdat de kar vrij kan bewegen kan de snelheid van de paal in principe oneindig groot zijn, maar als de paal bijvoorbeeld door de zwaartekracht omvalt, ligt de snelheid tussen de 0.0 en 5.0 radialen/seconde.

Compileren

Om je eigen implementatie te compileren gebruik je het volgende commando:

javac -cp PoleBalancing.jar <ControllerNaam>.java

waar <ControllerNaam> vervangen moet worden door de naam van jouw controller.

Voorbeeld oplossing

Om je op weg te helpen met het implementeren van interfaces in Java, de basis van je oplossing zal er zo uit moeten zien:

import nl.uu.cs.ias.cartpolebalancing.service.CartPoleController;
import nl.uu.cs.ias.cartpolebalancing.service.CartPoleStatus;

public class <ControllerNaam> implements CartPoleController {

	public double provideForce(CartPoleStatus currentStatus) {
	   return 0;
	}

	public void startSimulation() {
	}

	public void startTraining(int step, int totalSteps) {
	}

	public void endTraining() {
	}
}