Computer Science 302 Introduction to Artificial Intelligence Project 1

Fall 2001 Due Oct 22

Your program should take two arguments. The first one says which algorithm you should use(0 for BFS; 1 for A* with simple blocking heuristic; 2 for A* with more advanced heuristic). The second argument is the name of the input file. Then your program should gives the output on the stdout.

Your program must run/compile using gcc on the university unix machines(arizona, phoenix, ...)

Besides your program, you should also submit a report (we prefer plain text format) describing the structure of your program, the heuristic function you are using and anything else you think you should clarify. It doesn't need to be long.

Finally, speed and accuracy count

Input File Format

1. Co-ordinate System: X coordinate is the row (horizontal) ; Y coordinate is the column (vertical). The top-left square is with coordinate (0,0). So the board cells are indexed thus :
   

   +-----+-----+-----+-----+-----
   |(0,0)|(1,0)|(2,0)|(3,0)| ....
   +-----+-----+-----+-----+-----
   |(0,1)|(1,1)|(2,1)|(3,1)| ....
   +-----+-----+-----+-----+-----
   |(0,2)|(1,2)|(2,2)|(3,2)| ....
   +-----+-----+-----+-----+-----
   |(0,3)|(1,3)|(2,3)|(3,3)| ....
   +-----+-----+-----+-----+-----
   | ... | ... | ... | ... | ....
   
   

2. Input Format :
   • First line of the input file is the grid size;
   • For each line in the following lines:
     • 1st field : character : Car's direction ('h' or 'v')
     • 2nd field : integer : Car's size (e.g, 2)
     • 3rd field : integer : Car's X coordinate (for a horizontal car, it's the coordinate of the left most square; for a vertical car, it's the coordinate of top most square)
     • 4th field : integer : Car's Y coordinate
     • 5th field : integer : Is this car an icecream car? (0/1)
3. For the example in the figure below, the input would be:

   6
   v 2 2 0 0
   h 2 4 0 0
   v 3 3 1 0
   v 2 4 1 0
   h 2 1 2 1
   h 2 4 3 0
   

4. If the icecream car is horizontal, and if its initial co-ordinate is (x,y), then the outlet would be (GridSize-1, y), where GridSize is the number of rows/columns on the Rush Hour board. In the example above, the outlet is (5,2). Note that icecream car should finally be on the outlet cell (don't let the icecream car go out)
5. More sample input files: Sample1 Sample2 Sample3 Sample4 Sample5

Output Format

1. The first line of the output file has the number of moves taken to get the icecream car out. If no solution exists, this should be -1.
2. Each of the next lines gives individual moves for the solution. The format of the lines is:
   • 1st field (Car ID) : character : We associate the first car with carID "A", the second car with "B", the third car with "C", etc..
   • 2nd field (direction) : character : (L/R/U/D, denoting left/right/up/down)
   • 3rd field : integer : number of spaces to move in the direction given by the second field.
3. For the example, the output would be:

   5
   C U 1  
   F L 4
   C D 3
   D D 2
   E R 3
   

4. More output sample files: Sample1 Sample2 Sample3 Sample4 Sample5

Verifier Applet

1. Download the applet tar file.
2. Unpack it using the command tar xvf RHPack.tar.
3. This creates a "RHPack" directory. Go there ( cd RHPack )
4. Copy your input/output files to this directory
5. Run the appletviewer program with this applet (appletviewer RushHourApp.html).
6. If you find any mistakes in the applet please report them to Kedar Swadi or Gang Tan.