CSE 150 Winter 2004 Assignment 1

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

Assignment 1

DUE WEDNESDAY OCTOBER 13 AT 5 PM.

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

First, you should implement the A* algorithm and apply it to the eight-puzzle (EP) problem, using heuristics h₁ and h₂as explained on page 106 of AIMA (our textbook). Do experiments with your code to reproduce approximately the columns labeled A*(h₁) and A*(h₂) in Figure 4.8. In your report, answer Exercise 3.4 on page 89 of AIMA.

Second, you should extend your code to solve using A* two-dimensional Euclidean robot navigation (RN) problems, as explained in Exercise 3.15 on page 91 of AIMA. In your report, answer questions 3.15a and 3.15b. Invent and explain precisely a reasonable heuristic function to use with A*, to solve these navigation problems. Give a table similar to Figure 4.8 showing how A* with your heuristic performs on these robot navigation test cases.

Third, you should extend your code to solve using A* the missionaries-and-cannibals (MC) problem described in Exercise 3.9 of AIMA. Answer questions 3.9a, b, and c in your report.

In order for us to execute and test your code, please follow these interface instructions:

You should have separate programs (with reused A* code) for the EP problem (e.g. named eight_puzzle), the RN problem (e.g. named robot_navigation), and the MC problem.
The EP and RN programs should input one argument which is the Unix path of a text file. This file will specify multiple problem instances to solve, separated by blank lines. Each program should solve each problem contained in the file, first using heuristic h₁ then using heuristic h₂. Here are example Eight Puzzle and Robot Navigation input text files.
After solving each problem instance, each program should output the required fields to the Unix standard output, stdout. The required fields are the solution path, the solution cost, the depth of the solution, and the number of nodes generated. Make your output easy to understand.

You must write general code for the A* algorithm which you reuse for all three 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 four pages single-spaced, not counting the title page. The recommended length is about three pages single-spaced. Remember to check the class web page and WebCT regularly for possible updates to this project description.

This project will be graded as follows:

1/3 for the completeness and quality of your report,
1/3 for the correctness and quality of your code,
1/3 for the correctness and completeness of your experimental results.

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.