KI1 Practicum. Opdracht 1:

N.B. de deadline voor deze opdracht is vrijdag 23 februari 2007 om 9:00.

Voor wie geen boek heeft

Voor wie geen boek heeft: een voorbeeld van hoe een PAGE-probleemomschrijving eruit ziet, zie je hier.
Een PAGE-probleemomschrijving is nagenoeg hetzelfde als een PEAS-omschrijving.

De opdrachten

Voor regels omtrent het inleveren van de opdrachten, zie onder inleveren/beoordelen in het menu.

1. Probleemomschrijvingen

vrij naar opdracht 2.3 uit het oude boek :
of vrij naar opdracht 2.5 uit de nieuwste editie :

Gegeven de domeinen: (a) een potje voetbal en (b) een spelletje Monopoly.
Schrijf een PAGE of PEAS-description van een agent voor deze twee omgevingen.
Karakteriseer deze omgevingen als accessible / observable, deterministic, episodic, static en continuous of niet.
Welke agent architecture is het best voor elk van deze twee domeinen?

2. Formele probleemdefinities

Geef de initiele staat, goal test, operatoren en path cost functies voor de volgende problemem:

1. Je wilt een telefoonnummer opzoeken van Dhr. K.F.C.R.M. Janssen in Amsterdam. Je hebt een stapel telefoonboeken alfabetisch geordend op stadsnaam.
2. Zoals a, maar je weet zijn achternaam niet meer
3. Je bent verdwaald in de jungle, en je wilt naar de zee. Er is een rivier in de buurt.
4. Je moet een complexe landkaart zo inkleuren, dat geen twee landen met dezelfde kleur naast elkaar liggen. Je hebt de beschikking over 4 kleuren

3. Doolhof

Gegeven de volgende omgeving:

en een agent, die vier mogelijke relative stappen kan zetten (N,O,Z, of W)

States : de lokatie van de muren en de lokatie van de robot.

Operators : Noord, Zuid, Oost, West.

Goal Test : is de agent in het gele hokje?

Path cost : elke stap kost (uitgevoerde) stap kost 1.

Initial state : agent in rood (1)

Verder onthoudt de agent op de een of andere manier, als hij net tegen een muur is opgebotst : hij heeft daar dan een dikke buil, die hem er aan herinnert. De opdracht is nu, om d.m.v een d.f.s. de weg te vinden van het rode naar het gele hokje. De boom is als volgt: eerst probeert ie N, dan O, dan Z en dan W. (Dus een d.f.s pad van hokje 9 naar hokje 10 gaat zo : N-N (buil)-O-N (buil) - O (buil)- Z klaar. )

Vindt de agent een oplossing? Zo ja : welke? Zo nee, hoe kun je er voor zorgen dat hij wel een oplossing vindt? Het is niet nodig de zoekboom uit te schrijven, een pad dat met d.f.s leidt tot een oplossing is genoeg. Wat zijn de padkosten? Doe ditzelfde met b.f.s. en geef commentaar (wat is de beste methode en waarom).

4. Programmeeropdracht

Er is al een opzet voor de code gegeven in opdracht1.tar.gz
N.B. In operations.txt zijn de operaties {0,1,2,3} genummerd, dit moet zijn {1,2,3,4}. Een gecorrigeerde operations.txt kan je downloaden. Om verdere verwarring te voorkomen staat de {0,1,2,3} versie nog in de .tar.gz

Het is de bedoeling dat je de probleemdefinitie uitwerkt in Java. Je hoeft dus niet het zoekalgoritme uit te werken, dat is een opdracht voor de volgende week.

Je programma moet, gegeven een reeks van n operaties, n + 1 regels uitvoer genereren. Voor elke state waarin de agent verkeert 1 regel (dus 1 voor de initial state, en voor de state na elke actie in totaal n).

De operaties worden door een bij deze opdracht behorende Java class ingelezen. De mogelijke operaties zijn 1 (North), 2 (East), 3 (South) en 4 (West).
In de java class OperationList zijn hiervoor constanten gedefineerd, namelijk OperationList.NORTH, OperationList.SOUTH etc.
In de main() van de meegeleverde broncode wordt al een OperationList object voor je aangemaakt. Je kan aan dit object steeds de volgende operatie vragen door de functie OperationList.next() aan te roepen. Met OperationList.hasNext() kijk je of er nog meer operaties zijn.
Een goede manier om alle operaties te doorlopen is dus al volgt:

    OperationList opList = new OperationList(...);
    while (opList.hasNext()) {
        int op = opList.next();
        if (op == OperationList.NORTH) {
            // actie noord
        } else if (op == ...) {
            ...
        } ...
        ...
    }

De wereld is een doolhofwereld zoals die uit deelopdracht 3. Maar let op, het is nu een mxn doolhofwereld, met states genummerd van 1 linksonder t/m mxn rechtsboven. Je moet zelf een manier bedenken om dit handig te representeren. Wat je aangelevert krijgt is een class MazeData. Hieraan kun je vragen

• hoe groot het doolhof is (MazeData.getSizeX() - van links naar rechts, MazeData.getSizeY() - van beneden naar boven),
• wat de beginpositie (MazeData.getStartPosition()) en de doelpositie (MazeData.getGoalPosition()) zijn,
• of er tussen twee posities een muur staat (MazeData.hasWall(p1, p2))

Het is aan jou om de operaties goed te implementeren. Let er dus op dat de muren om het doolhof geïmpliceert zijn omdat daar het doolhof ophoudt en dat je alleen naar direct aangrenzende vakjes gaat. Je mag natuurlijk niet door muren heen.

Voor het representeren van de state kun je het object State gebruiken. Deze maak je aan door new State(position, bump), de access methoden zijn zoals je volgens de conventies kan verwachten (of zie de broncode).

Bij elke bereikte state willen we de volgende uitvoer zien:

1. De huidige positie
2. Of de agent een buil heeft (of de laatste actie tegen een muur botste)
3. De totale path cost tot nog toe
4. Of de huidige state de doelstate is (N.B. je hoeft alleen de gegeven operaties uit te voeren, als de doelstate bereikt is stop je dus niet met de uitvoer van je programma)

De file Main.java bevat een skelet voor het hoofprogramma en een functie output(position, bump, cost, goal) die je aanroept om uitvoer te geven (pas deze functie dus niet aan, dan kunnen wij de uitvoer van je programma testen!

Als je deze opdracht netjes uitvoert (zie het nieuwe boek pagina 62) heb je volgende week al een probleemdefinitie met initial state, actions, goal test en path cost.

Ik raad je aan om de build-tool 'ant' te gebruiken. Bij de broncode is een 'build.xml' bestand meegeleverd, deze is geschikt als ant buildfile. Om de broncode te compileren gebruik je het commando 'ant build'. Om het programma vervolgens uit te voeren gebruik je 'ant run'. De laatste voert automatisch ook 'ant build' uit. Eventueel kan je onnodige bestanden opschonen met 'ant clean' (daarna moet je wel alles opnieuw compileren).

Ant voert het programma automatisch uit met de twee megeleverde data files. Het staat je natuurlijk vrij om deze aan te passen en ermee te experimenteren.

Lever de hele source directory, ingepakt met tar, weer in. Gebruik wel eerst 'ant clean' om de gecompileerde bestanden te verwijderen. Zie voor filename conventies onder inleveren/beoordelen in het menu.

N.B. wil je het in een andere taal doen, hou er dan rekening mee dat je extra tijd kwijt bent om de geleverde inleesroutines opnieuw te implementeren en dat je ook een (werkende) executable en buildfile meelevert.