COMP3411 Artificial Intelligence

Session 1, 2011

Project 1 - Maze Exploration and Traversal

Due: Sunday 10 April, 11:59 pm
Marks: 16% of final assessment

Specification

In this project you will be writing a controller for a robot to explore a maze and visit a light source, then return to its original location.

The robot will be equipped with an array of 12 sonar sensors.

The maze will be composed of horizontal and vertical walls conforming to a rectangular grid with square cells of size 2 by 2 units.

Getting Started

Copy the file src.zip into your own directory and unzip it. You will see a directory with four java files and two shell scripts.

Compile the code by typing 

./comp.sh hw1.java hw1Body.java hw1Brain.java
The Java file GenMaze.java can be used to randomly generate new mazes of a specified size, as follows: 
    javac GenMaze.java
    java GenMaze 6 > maze.in
The simulation can then be run by typing 
./run.sh hw1 < maze.in
Your task will be to provide the method performBehavior() in the file hw1Brain.java (you may also add other methods, if you wish).

Stage 1

Program the robot so that it explores the maze systematically, by following either the left-hand or right-hand rule. When the simulation is run, your robot should eventally visit the light source, and then keep going until it returns to its original location, at which point the simulation will end. You may assume that the maze does not contain any loops.

Stage 2

Now modify your code so that, after reaching the light source, the robot will return to its original location by the shortest known path, i.e. without going down any dead-ends.

For this project, the method getCoords() may be used to return a vector indicating the current position of the robot in global co-ordinates. You may assume that the centre of the maze is at (0,0,0) and that it has an even number of rows and columns.

Although the robot does not have a light sensor, you can use the method haveVisitedLight() to check whether it has visited the light yet.

Question

At the top of your code, in a block of comments, you must provide a brief answer (one or two paragraphs) to this Question:
Briefly describe how your program works, including any algorithms and data structures employed, and explain any design decisions you made along the way.

Submission

Once submissions are open, you should submit by typing

give cs3411 hw1 hw1Brain.java

You must put all your code into one file, which must be called hw1Brain.java. If you attempt to submit modified versions of the other files, your modified versions will be discarded and the original files used in their place.

You can submit as many times as you like - later submissions will overwrite earlier ones. You can check that your submission has been received by using the following command:

3411 classrun -check

The submission deadline is Sunday 10 April, 11:59 pm.
15% penalty will be applied to the (maximum) mark for every 24 hours late after the deadline.

Additional information may be found in the FAQ and will be considered as part of the specification for the project.

Questions relating to the project can also be posted to the MessageBoard on the course Web page.

If you have a question that has not already been answered on the FAQ or the MessageBoard, you can email it to your tutor, or to cs3411.hw1@cse.unsw.edu.au

Marking scheme

Your program will be tested on a series of mazes of various sizes (no larger than 30 by 30) You should always adhere to good coding practices and style. In general, a program that attempts a substantial part of the job but does that part correctly will receive more marks than one attempting to do the entire job but with many errors.

Plagiarism Policy

Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise and serious penalties will be applied, particularly in the case of repeat offences.

DO NOT COPY FROM OTHERS; DO NOT ALLOW ANYONE TO SEE YOUR CODE

Please refer to the Yellow Form, or to section on Originality of Assignment Submissions in the Unix Primer, as well as the CSE Addendum to the UNSW Plagiarism Policy if you require further clarification on this matter.

Good luck!