Project #1 -- Heuristic Search

This project is time-consuming! Start NOW!

Bug Alert in Allegro Lisp

The Assignment:

1. The number of tiles in an incorrect position.
2. Manhattan distance (sum of distances of all tiles from goal).
3. Manhattan distance + 1 for each juxtaposed, transpositioned pair.
4. A heuristic of your own design (does not need to be admissable).

To complete the assignment, you should hand in:

1. A documented listing of any code you modified or wrote for this assignment.
2. A graph plotting the average number of node expansions needed to find a solution vs. the cost of a (optimal) solution. The graph should show the data for each of the four heuristics.
3. A graph plotting the average number of node generations needed to find a solution vs. the cost of a (optimal) solution. The graph should show the data for each of the four heuristics.
4. For your own (possibly inadmissable) heuristic, for how many of the problem instances did A find an optimal solution? For any suboptimal solutions, how near were the solutions to optimal (e.g., "the inadmissable heuristic found suboptimal solutions 15% of the instances, but of these, the solution was always within 110% of the optimal cost.") (Optimal solution cost is determined by the results of the A* runs using the Manhattan Distance metric.)
5. A one page analysis/commentary of the observed results: which heuristic appeared to work best? Why? Attempt to explain any anomolies.

To make it easier to collect and manipulate your data, you should write a function that runs you search algorithm and returns a list comprised of the three datum to be collected with each run. Of course, you might want to print out this information in a nice format with each run, too.

The source code for programs in the Russell/Norvig textbook is located in the directory /usr/tools/cse.pub/matt/AIMA-lisp-code/. You should feel free to browse through the source code there, taking what you need for theassignment.

Speaking of which, you should copy the file search-setup.lisp into your directory (just follow the link here and copy & paste). You should load this file whenever you first start lisp with the intention of doing this assignment! Also, examine the contents of that file for many helpful hints as to how to do your assignment.

Ths file search-setup.lisp (above) was modified on 10/29/96 to accomdate new system software. (Basically, a change in the subdirectory structure on the departmental machines.) Please get a new copy of it if your copy is out of date.

As you examine search-setup.lisp you should see how you can go about generating your 40 problem instances [look in puzzle8.lisp,too.] For determining the number of expansions the occur during a run, refer to the function (see above) PROBLEM-NUM-EXPANDED. As for solution path length, see NODE-G-COST, above. As for easily changing which heuristic function you use, see the argument list of the function 8-PUZZLE-PROBLEM in puzzle8.lisp.

Because most people's programs will run slowly on the departmental workstations, keep the difficult of the problems to be solved reasonable. You can do this by changing the "num-moves" argument to random-8-puzzle-state from 100 to 50, or even 40. The solution paths will be smaller, and the results not so interesting, but you should be able to get your 40 iterations done in a timely fashion. If you are working on a decently powerful machine at home, you can probably relax this restriction to get more interesting results.