CS121
Introduction to Artificial Intelligence
Winter 2004
Homework #4
(Search Problems)
Out: 2/4/04 — Due: 2/11/04
How to complete this HW: This homework is a programming assignment to be done individually. You can download the C starter files from /afs/ir.stanford.edu/class/cs121/hw4. After writing the program you should submit using the submission script at /afs/ir.stanford.edu/class/cs121/bin/submit. You must submit before 2/11 at midnight. You must make sure your program works on the SUN solaris machines, as that is where we’ll be grading the programs. Your submission should include a README that includes your name, e-mail, SUNet ID, answers to the questions, and any comments you might have.
Note on Honor Code: You may discuss this program with other students in the class and/or look into other documents (books, web sites), with the exception of published solutions, without taking any written or electronic notes. However, all code and answers must be your own work. If you have discussed the program with other students, indicate their name(s) in the README. Any intentional transgression of these rules will be considered an honor code violation.
In this assignment, you will implement a solution to
a navigation problem, which is as follows:
A robot represented as a point moves in a
regular two-dimensional NxN grid (e.g., N = 100). Each point of the grid is
either "free" or "forbidden" (obstacle). From any position
(i,j) in the grid the robot can reach each of the 4 adjacent positions (i,j-1),
(i,j+1), (i-1,j), (i+1,j), if it is not forbidden. A navigation problem
consists of finding a path in the grid (sequence of adjacent free points) that
connects a given initial position to a given goal position. Each move has a
cost of 1.
Write a program implementing the Best-First Search
algorithm to solve this problem. To do this, first formulate the navigation
problem as a search problem: what are the states, the successor function, the
initial and goal states? Allowing the search tree to contain nodes labeled by
the same state leads to an infinite search tree. So, the program should avoid
duplicating states.
- f(N) = Euclidean distance from N to the goal
(Strategy 1)
(i.e. the length of a straight line between two
points, E((i,j),(i',j')) = sqrt[(i-i')^2+(j-j')^2])
- f(N) = Manhattan distance to the goal (Strategy 2)
(i.e. the length of the shortest path obtainable by
traversing only in the cardinal directions, ignoring any obstacles,
M((i,j),(i',j')) = |i-i'| + |j-j'|)
- f(N) = g(N) + h(N), where: - g(N) is the cost of
the path found so far from the initial node to N - h(N) is: - the Euclidean
distance from N to the goal (Strategy 3) - the Manhattan distance to the goal
(Strategy 4)
Answer the following question in the README:
Is the algorithm A* with the
last two functions? If yes, which of the two h should produce the smallest
search tree?
For each problem-function pair, your program should output the
generated path, its cost, and the number of nodes in the search tree when the
solution was found.
Answer in the README:
Compare the costs and sizes of search trees for the
various functions.
We have provided some C stub code as well as a
Makefile; they are available at /afs/ir.stanford.edu/class/cs121/hw4. While it is your prerogative to do your
development on any platform, it is your responsibility to make sure that your
solution works on a SUN solaris machine (tree, saga, myth, Elaine, fable, epic,
etc.), as we will be testing your programs on one of these.
You can compile the program and create the
executable by entering:
Fable10:~> make
The name of the program is navi and should be invoked
as:
Fable10:~> ./navi <filename>
where <filename> is the name of the file
containing the map you want the robot to navigate.
The input files will contain information about the
map that the robot will traverse. The first line will have a number N that is
the width and the height of the map (all maps are NxN, i.e. same height and
width). The following N lines will
detail the map. Each line will have N characters, representing the N spaces in
that row. The first line will be row N and the first character in each row will
be in column 0. The characters in the rows will be as follows:
. empty space (traversable)
i initial space (traversable, robot start here)
g goal space (traversable, robot’s goal here)
+ obstacle (not traversable)
A sample input file might be as follows:
5
...g.
.++..
.i+..
..+..
+...+
Every input file is expected to have at least one
possible path to the goal. We have provided some sample input files in the
download directory to give you a start. The code to read input files is already
in place in the stub code. Your robot cannot move diagonally; it can only move
to the spaces immediately up, down, left, and right. The robot cannot enter a
space occupied by an obstacle.
The maps that you will generate as output should be the same as the maps in the input files, except that each step in the path taken will be represented as an ‘o’ (the lower case letter o). The goal and initial spaces should remain ‘g’ and ‘i’ respectively. As an example, a solution map to the above input map might be:
ooog.
o++..
oi+..
..+..
+...+
The stub code is set up to print to the screen and
write to files the solution in a specific way.
We will be testing your output, and as such, it needs to be formatted
correctly. Note that some situation can yield different answers depending on
exactly how you implemented the search. As long as your program yields one of
the correct answers, it should be fine.
Your
program will be tested for correctness for various maps. The correctness is
worth 90 points. Some sample inputs are available in the starter file folder.
Correctness testing
will be done with scripts. Your program must compile and run on the specified
grading machines without us making any modifications. If it does not, you will get no correctness
points.
10 points will be awarded for code quality. (Your
code will need to be exceptionally badly designed to lose these points, so
don’t stress too much about this.)
In addition to the program code, you should supply a README that includes your name, e-mail, SUNet ID, answers to the questions, and any comments you might have.
To submit your assignment, clean out all object files and executables from your directory, so that all you are submitting is the Makefile, code, and README, and issue the following command, and follow the instructions of the script at:
Please only submit from inside your working
directory. Try not to submit sample input or output files.