CMSC 671

Artificial Intelligence -- Fall 2003

HOMEWORK THREE
out 9/29/03 due 10/13/03 (Part I due 10/20/03)

http://www.cs.umbc.edu/671/fall03/hw/hw3.html

I. A* Search (30 points)

This part of the homework (and only this part) is to be done with your project team.

You should implement A* search on the Empire Builder map, using the infrastructure code provided for the class.  (More documentation on how to download and use this code will be distributed on Wednesday.) You should use, as your cost function, the cost to build a path.

Reporting your results: Submit your Lisp code and a script file showing the path your code finds on the test cases (to be announced). As always, all parts of the homework should be submitted in hardcopy; in addition, your Lisp code should be submitted electronically.

II. Search (20 points)

(1) (10 points) Russell & Norvig Exercise 3.7(a,b). Note: For (b), assume that when a node is expanded, the successor nodes are generated in numerical order.

(2) (10 points) A* terminates when a goal node is selected for expansion. Why shouldn't the search be stopped when a goal node is first generated? Illustrate your answer with an example.

III. Constraint Satisfaction (20 points)

Russell & Norvig Exercise 5.5. Note: Your formulation should clearly state what the variables are, the domain of each variable, and the set of constraints on the variables.  Your formulation should be general (i.e., it should apply to any set of rectangles, classes, professors, etc.).

IV. Game Playing (30 points)

(1) (15 points) Russell & Norvig Exercise 6.1(a-e).

(2) (15 points) Russell & Norvig Exercise 6.2. Note: Your proof should consist of a convincing argument, stated clearly.