Kunstmatige intelligentie
Programmeeropgave 2 van 2014 — Domestic Robots
De tweede programmeeropgave behorende bij het vak
Kunstmatige intelligentie gaat over Multi-agent Systems. De bedoeling van de opdracht is om een verzameling gesimuleerde eenvoudige huishoudrobots te implementeren en een klein onderzoekje te doen naar de efficiëntie van de robots als functie van de grootte van de verzameling.
Zie ook de sheets van 4 maart.
Voor deze programmeeropgave gebruiken we de programmeeromgeving GOAL. Download de laatste release en installeer deze op je eigen Linuxaccount. Start GOAL met ./goal.sh. Je mag natuurlijk ook je eigen computer en/of een ander besturingssysteem gebruiken. Meer informatie over de GUI en de programmeertaal staat in de User Manual en de Programming Guide van GOAL (bron: http://mmi.tudelft.nl/trac/goal/wiki/WikiStart#Documentation).
Bekijk als voorbeeld de Cake-agent. Deze agent heeft als doel om een cake te hebben. Merk op dat doelen een toestand van de wereld aangeven (declaratief), en niet een actie die uitgevoerd moet zijn (een cake bakken). Dit verschil is belangrijk voor de structuur van de agent, en dit zal worden gebruikt in de beoordeling van de opdracht. De cake-agent bevat commentaar met uitleg over de syntax en semantiek van GOAL. Pak de twee bestanden uit in de map waar je GOAL hebt geïnstalleerd, in de subdirectory GOALagents/HelloWorld. Open het .mas2g-bestand in GOAL en dubbelklik op de agent (cake.goal) om de code te bekijken in de ingebouwde editor. Klik op Run (ctrl-r) om het systeem te starten. Selecteer daarna de agent helloWorldAgent en klik dan op de Introspector (ctrl-d) om de huidige toestand van de agent (beliefs, goals, knowledge, percepts, messages) te kunnen bekijken. Selecteer daarna weer het systeem (HelloWorld.mas2g) en klik op Step (ctrl-t). Onderin de GUI verschijnt een trace van de agent-code in de tab helloWorldAgent. De berichten die de agent zelf print verschijnen in de tab Console. Voer het systeem stapsgewijs uit en probeer de toepassing van de regels en de veranderingen in beliefs en goals te begrijpen. Klik op Kill (ctrl-k) terwijl het .mas2g-bestand geselecteerd staat om het hele systeem te stoppen (als het agent-bestand geselecteerd staat wordt alleen de agent gestopt, dit is meestal niet de bedoeling).
Opdracht
Implementeer een verzameling agenten in de Domestic-Robot environment. Deze omgeving is meegeleverd met GOAL, maar wij gebruiken een aangepaste versie. Update (24-03-2014): het percept received is vervangen door een percept obtained(N) met een stabielere implementatie, zie verder de beschrijving. Kopieer deze naar de installatiedirectory van GOAL in de subdirectory GOALagents/Domestic. Lees de beschrijving van de acties en percepts van deze versie. De omgeving bevat een koelkast (F), een eigenaar (O) en een aantal robots (R0 t/m R9). Het doel van de robots is om consumpties in glazen flesjes van de koelkast naar de eigenaar te brengen. Hierbij kunnen de robots samenwerken, dat wil zeggen dat ze elk een gedeelte van de route afleggen. De robots zijn echter niet perfect: tijdens het verplaatsen kan een flesje op de grond vallen. Bij een langere afstand wordt de kans op vallen groter. Hierdoor is het verstandig om veel robots in te zetten die elk een klein gedeelte van de route lopen, waardoor de kans op vallen tijdens het lopen wordt verminderd. Echter, ook tijdens het overdragen van een flesje van de ene robot naar de andere kan er iets misgaan, waardoor het risico op vallen groter wordt met een groter aantal agenten.
Implementatie
Gebruik voor deze opgave de skelet-code, pak deze uit in de installatiedirectory in GOALagents/Domestic. De implementatie moet aan de volgende eisen voldoen:
- Implementeer de opgave voor n=1..10 agenten. De eerste agent loopt naar de koelkast, pakt een flesje, loopt naar de tweede agent, draagt het flesje over, loopt terug naar de koelkast, etc. De tweede agent wacht totdat hij een flesje gekregen heeft en loopt dan naar de derde agent. Ondertussen kan de eerste agent natuurlijk alweer verder gaan met het volgende flesje. De laatste agent draagt het flesje over aan de eigenaar.
- Aan de hand van het aantal robots en een per robot vooraf toegekend volgnummer moeten de agenten autonoom bepalen hoe het veld wordt verdeeld. Vraag het aantal agenten dynamisch op door te kijken naar het aantal instanties van het Belief-element agent(X). Bonus (+0.5 punt): implementeer een communicatieprotocol waardoor de verdeling door de agenten onderling wordt afgesproken zonder het gebruik van vooraf toegekende volgnummers.
- Gebruik initieel een kans van 10% dat een flesje valt tijdens het overdragen. Voor het lopen geldt dat de kans op vallen met elke stap 0.5+n/10 procentpunt groter wordt voor het aantal afgelegde stappen n. Als een agent een nieuw flesje krijgt (uit de koelkast of van een andere agent) wordt n op 0 gezet. De kansen worden dus 0, 0.005, 0.011, 0.018, 0.026, etc.
- De acties move_towards(Object,Agent,Hold), move_towards(X,Y,Agent,Hold) en transfer_out(AgentFrom,AgentTo,Hold) hebben als laatste argument de parameter Hold. Als aan deze parameter de waarde 0 wordt gegeven betekent dit dat het flesje valt, bij 1 blijft het flesje heel. Gebruik de Prolog-functie random(N) voor het genereren van een (semi-)willekeurig getal tussen 0 en n en beeld dit af op {0,1} volgens de gegeven kansverdeling.
- Initieel bevat de koelkast 10 flesjes. Het succes van dit multi-agentsysteem is gedefinieerd als het aantal flesjes dat de eigenaar bereikt. Voer per aantal agenten (van 1..10) 100 simulaties uit en bereken het gemiddelde succes. Maak een grafiek van de resultaten. Schrijf een script om de simulaties te automatiseren.
- Gebruik voor elke agent een apart bestand zodat op de plaatsen waar dat nodig is de naam of het volgnummer van de agent kan worden gespecificeerd. Bonus (+0.5 punt): instantieer alle agenten uit hetzelfde bestand waarbij de specifieke informatie automatisch wordt afgeleid.
- Richtlijn lengte: ongeveer 200 regels code.
Algemene informatie GOAL
GOAL is een agent-framework dat gebruikmaakt van de programmeertaal Prolog.
(Zie voor enige uitleg over Prolog:
uitleg met voorbeelden.)
Een agent in GOAL bestaat uit de volgende elementen:
- Knowledge: algemene regels over de concepten die gebruikt worden door de agent (enigszins vergelijkbaar met functies in C++).
- Beliefs: de overtuigingen van de agent over hoe de wereld er op dit moment uitziet.
- Goals: de doelen van de agent.
- Program: regels om acties, nieuwe beliefs en goals af te leiden uit de omgeving en de huidige beliefs en goals. Dit bestaat uit twee delen:
- Event module: regels voor het omgaan met percepts uit de omgeving.
- Main module: regels voor het omgaan met huidige beliefs en goals.
- Action specifications: pre- en postcondities van beliefs voor acties.
Elke Program-regel bestaat uit een mogelijk samengestelde voorwaarde en een mogelijk samengestelde actie. Behalve een uitvoerbare actie in de omgeving (bv. open(fridge)) is ook het aanpassen van goals en beliefs gedefinieerd als actie. Een program cycle bestaat uit twee delen. Eerst worden alle regels uit de Event module uitgevoerd waarvan de voorwaarde waar is. Daarna wordt de eerste regel uit de Main module waarvan de voorwaarde waar is uitgevoerd.
Goals hebben dezelfde syntax als beliefs. Een belief is een overtuiging over de toestand van de wereld, een goal geeft aan wat de toestand van de wereld moet worden. Nieuwe beliefs kunnen worden toegevoegd met behulp van de actie insert of als postconditie van een omgevingsactie. Als een belief wordt toegevoegd dat overeenkomt met een van de goals wordt dit goal automatisch uit de lijst doelen van de agent verwijderd.
Tips
- De omgeving genereert een percept adjacent(A,B) als agenten A en B naast elkaar staan. Dit percept kan je gebruiken om de ontvanger van een transfer_out-actie te bepalen.
- Agenten kunnen elkaar berichten sturen, bijvoorbeeld om een andere agent in te lichten dat een bepaalde actie gedaan is. Syntax: if voorwaarde then Ontvanger.send(Bericht). Hierbij is Ontvanger de naam van de ontvangende agent (bv. robot4) en Bericht een Prolog-predicaat, bv. voorraad(3). De ontvangende agent krijgt een nieuw belief received(X,Bericht) met de naam van de verzender X en het bericht. Let op: gebruik sturen en ontvangen van berichten alleen in de event-module. Gebruik bij voorkeur het berichtensysteem voor het afhandelen van transfer_out, en niet het percept obtained(N).
- Batch running: via de terminal kan het systeem meerdere keren achter elkaar worden uitgevoerd. Voordat je dit gaat doen moet je zorgen dat het systeem altijd op de juiste manier termineert, dat wil zeggen dat alle 10 flesjes bij de eigenaar zijn gebracht of zijn gevallen, en dat de agents daarna allemaal eventuele overgebleven goals verwijderen en geen nieuwe goals meer toevoegen.
- Gebruik de volgende syntax vanuit de hoofddirectory van GOAL:
java -cp "goal.jar:environments/domestic.jar" -Djava.library.path=swifiles/libs/ goal.tools.Run [absolute path]/domestic.mas2g -r 100
- Let op het gebruik van een absoluut pad voor het .mas2g-bestand: op NUWD Linux is dit /vol/home/[ulcn-gebruikersnaam]/[GOAL installatie-pad]/[...]/domestic.mas2g.
- De optie -r specificeert het aantal iteraties.
- Vooraf moeten de variabelen LD_LIBRARY_PATH en SWI_HOME_DIR worden ingesteld. In Linux kan je dit eenvoudig doen door het meegeleverde script goal.sh aan te passen.
- Vergeet niet in het .mas2g-bestand de optie gui=off te specificeren. De environment genereert output in de terminal als een flesje valt en als de simulatie is afgelopen. Schrijf deze output weg naar een bestand waar je later de gemiddelde scores mee kunt uitrekenen. Gebruik een programmeertaal naar keuze om dit bestand te parsen.
- Onder Linux kan je naar een bestand schrijven met ./opdracht > bestand (voor nieuwe bestanden) of ./opdracht >> bestand (om onderaan een bestaand bestand nieuwe data toe te voegen, ook wel append genoemd). Hiermee wordt alle uitvoer die normaal in de terminal verschijnt in het bestand opgeslagen. Hierdoor is het niet meer zichtbaar in de terminal zelf. Je kunt het wegschrijven meelezen in een ander terminalvenster met tail -f bestand (-f van follow). Een andere optie is om de opdracht als invoer te gebruiken voor tee, bv. ./opdracht | tee -a bestand. Hiermee wordt de uitvoer in de terminal getoond en gekopieerd naar het bestand (-a van append).
- Maak een grafiek in gnuplot met per aantal agenten het gemiddelde aantal afgeleverde flesjes en de oorzaken van gevallen flesjes (het gemiddeld aantal flesjes dat gevallen is tijdens het lopen, en het gemiddeld aantal dat gevallen is tijdens het overdragen).
- Het kan gebeuren dat het systeem niet in alle gevallen juist termineert, en dat het niet goed lukt om de oorzaak daarvan vast te stellen (en te verhelpen). Als dit gebeurt is het niet mogelijk om automatisch 100 metingen te doen. Als het in de meeste gevallen wel goed gaat kan je eventueel de optie --timeout seconds gebruiken als parameter voor goal.tools.Run. Hiermee wordt een meting gestopt als de ingestelde tijd voorbij is, waarna de volgende meting wordt gestart. Pas op voor een eventuele bias in je meetresultaten en vermeld dit duidelijk in je verslag.
Deadline: dinsdag 1 april 2014, 11:00 uur.
In te leveren: een geprint exemplaar van het verslag tijdens
het college, en de GOAL-code van het programma naar onderstaand adres.
Het verslag moet aan verschillende
eisen voldoen.
Vragen en/of opmerkingen kunnen worden gestuurd
naar: W.A.Kosters@liacs.leidenuniv.nl.
24 maart 2014 —
http://www.liacs.nl/home/kosters/AI/opdracht2.htm