- A* code
- Test code (updated 9/21/99)
- ep-children function (or use your ep-children function from Assignment 2)

I encourage you to design your own heuristic --- you can create one from scratch or create some variation on a known heuristic. However, you may implement a known heuristic; I'll suggest a few later on. Your heuristic need not be admissible.

You should turn in:

- electronically: your
`ep-heuristic`function (along with your`ep-manhattan`function) to the directory`/dept/cs/ai/submit3`**Submit only these functions (and any functions they call directly)**Do not submit the A* code or the test code --- I already have it and it will just take up extra space and cause trouble.

Starting on this assignment, we will deduct for sumbissions that produce errors when loaded into Scheme. (probably a 5% penalty)

- in writitng:
- whether your heuristic is completely original, an original
variation on a known heuristic, or an implementation of a known
heuristic
- an explanation of your heuristic
- whether your heuristic is admissible or not. If it is
admissible, explain why. If not, explain why not, possibly with an
example.
- whether your heuristic is monotonic or not. Explain why or why not.

- whether your heuristic is completely original, an original
variation on a known heuristic, or an implementation of a known
heuristic

- the number of nodes expanded
- the computation time to find a solution
- whether it finds the optimal solution

Here are a few of the heuristics which I described:

- Nilsson's Sequence Score: h(n) = P(n) + 3 S(n)
P(n) is the manhattan distance of each tile from its proper position.

"The quantity S(n) is a

*sequence score*obtained by checking around the noncentral squares in turn, allotting 2 for every tile not followed by its proper successor and 0 for every other tile, except that a piece in the center scores 1."This might be easier to understand if you know that the goal state that Nilsson uses is represented by:

`(1 2 3 8 space 4 7 6 5)`. This heuristic is not admissible. - X-Y: decompose the problem into two one dimensional problems
where the "space" can swap with any tile in an adjacent row/column.
Add the number of steps from the two subproblems.
- Number out of row plus number out of column
- n-MaxSwap: assume you can swap any tile with the "space". Use
the number of steps it takes to solve this problem as the heuristic
value.
- n-Swap: represent the "space" as a tile and assume you can swap
any two tiles. Use the number of steps it takes to solve this problem
as the heuristic value.
- Distance of blank: In terms of the operator/state representation
used today in class:
- drop from xmove: xloc, yloc, ylocb
- drop from ymove: xloc, yloc, xlocb
- factor into X and Y

You could create the "perfect" heuristic by having it perform an A* search to find the exact number of steps to reach the goal, but I would not accept this as a good solution to this problem.

- A paper about ABSOLVER, a program that automatically generates
heuristics from formal descriptions of a problem. Almost all the
heuristics above are listed in this paper (either known heuristics
that were derived by ABSOLVER or original heuristics that were created
by ABSOLVER).
- A section from "Problem Solving Methods in Artificial Intelligence" by Nils J. Nilsson, McGraw-Hill, 1971, pp. 53--68. This includes some formal proofs about the A* algorithm and also includes Nilsson's Sequence heuristic described above.

You can find out how much heap space you have with the scheme command:

(print-gc-statistics)Look for the "

You can start Scheme with a larger heap either by specifying the flag
`-large`, which should start you with about 1,000,000 words, or
by specifying a heap size with `-heap < blocks>`,
where

For those of you using Windows, you'll have to edit the alias to add the appropriate flags.

whuang@cs.rpi.eduLast updates: September 14; September 16, 1999