Department of Computer Science and Engineering CSE 150
University of California at San Diego Winter 2004

 Assignment 1

DUE THURSDAY JANUARY 22 AT 2 PM.


The purpose of this project is to implement the A* algorithm, and to do interesting experiments with it.  The project has two parts.  You will write code and also a short report.

First, you should implement the A* algorithm and apply it to the 8-puzzle, using heuristics h1 and h2 as explained on page 106 of AIMA (our textbook).  Do experiments with your code to reproduce the columns labeled A*(h1) and A*(h2) in Figure 4.8.

Second, you should extend your code to solve using A* two-dimensional robot navigation problems, as explained in Problem 3.15 on page 91 of AIMA.  In your report, answer questions 3.15a and 3.15b.  Also invent and explain precisely two different reasonable heuristic functions to use with A*, to solve these navigation problems.

On January 15, we will publish several navigation test problems.  In your report, give a table similar to Figure 4.8 showing how A* with your two heuristics performs on the test problems.  Also include columns showing the number of steps in each plan, and the total length of each plan.  The input for a navigation test problem will look like this example:

start 15.0 19.5
goal 100.0 100.0
obstacle 12.0 12.0, 40.0 30.0, 25.0 50.0
obstacle 60.0 60.0, 60.0 70.0, 70.0 70.0, 70.0 60.0

In the example above there are two obstacles, a triangle and a square.

You must write general code for the A* algorithm which you reuse for both parts of this project.  In other words, your A* implementation must be modular and organized well enough so that it can be reused with any problem formulation and any heuristic function.  For this project, you may use any of the following programming languages: Java, C, C++, or Python.  If you want to use a different language, contact the instructor.


GENERAL INSTRUCTIONS

Here are detailed instructions for how to submit your code.  You will submit a printout of your report at the start of class on the due date.  The maximum length of the report is three pages single-spaced, not counting the title page.  The recommended length is about two pages single-spaced.  Remember to check the class web page and discussion group regularly for possible updates to this project description.

This project will be graded as follows:

Your software should have good organization, useful comments, and decent speed.  It must be as concise and straightforward as possible.  For this project, you should work by yourself or in a team of two students.  You may get assistance from the TAs, the 134A discussion board, the web, and books, but not from students outside your team.  You should not copy any existing code.  Complete academic honesty is always required.

Your report should be written using a word processor and printed on 8.5x11 paper.  It should be concise but complete enough to be understandable by itself, and written in good English.  The report should include a short introduction and be divided into appropriate sections.  Use diagrams, tables, and charts when necessary.  Avoid spelling and grammar mistakes by repeated proofreading.  Remember that these mistakes and incorrect vocabulary tend to make readers underestimate the value of your technical work.