Homework #1: Search Me

Form into groups of two or three people, and make sure you have at least one person in your group with solid knowledge of LISP.

Your assignment has four parts. The first two can occur in parallel, the latter parts depend on the first parts.

  1. Write search algorithms to implement four of the following search techniques: breadth first search, iterative deepening, A*, iterative deepening A*, and beam search. Details of the API for your search algorithm are listed below. Each member of the group should be personally responsible for at least one of the search algorithms!
  2. Construct search problems (by hand or with programs) which demonstrate the advantages and disadvantages of your different search algorithms. You need not create more than one domain of problems (i.e., they could all be mazes), but you must create enough problems to show that each algorithm is much better than one of the other algorithms (i.e., four problems, one shows iterative deepening better than breadth first search, one shows breadth first better than iterative deepening, one shows A* better than beam, and one shows beam better than breadth first). Note: we're not necessarily looking for huge or intricate problems here. We're looking for interesting problems.
  3. Run your algorithms on your problems and at least one other group's problems (credit the group!) and record results in terms of time and memory use.
  4. Explain your algorithms, problems, and results.

API Details

In order to make constructing, grading, and sharing search engines and problems easier, we'll use a standard API for the search function.

Search Function

Each algorithm should be initiated by calling a function as follows:
(search initial #'goal-p #'generate)
or for algorithms which need a heuristic function:
(search initial #'goal-p #'generate #'rank-fun)
search should be replaced with your functions' names. The other arguments are:
initial
a state
goal-p
a function that takes a state and returns T iff the state represents a goal state
generate
Note changes: a function that takes a state and returns a list of states of the form (state1 state2 ... ) representing all possible successors of that state labeled according to the move taken to reach the successor.
rank-fun
a function that takes a state and returns a non-negative number such that lower numbers indicate a "more promising" state.
Note changes: Your search function should return the solution state reached or the symbol NO-SOLUTION in case of failure. Note that allowing states to like like the symbol NO-SOLUTION is a bad idea. You should also create a function meta-search which takes all the arguments search takes plus an initial argument specifying the type of search to use and dispatches the problem to the appropriate search algorithm. It will return the search algorithms return value. The symbols specifying search types will be: A sample call would be:
(meta-search 'a-star initial #'goal-p #'generate #'rank-fun)

Problem Format

The generality of your search function makes it so that you can use any problem format you want. All you need to do is expose a function for generating next states, a function for testing for goal states, and potentially a heuristic function. It might be a good idea to choose a standard way to extract the path taken in a search from the goal state returned, but that is entirely separate from the search algorithm. Here's two suggestions for problem formats: You may assume that generate and goal-p will be called only once on a given state per search as long as you follow that requirement in your search engines. Your ranking functions must always return the same value for the same state (and they may be called multiple times on a given state).

Submission style

You will be expected to submit all the well-documented code for your assignment along with a text file called README containing descriptions of your files, a list of all the assumptions and elaborations you made to make the assignment make sense, and your results for parts 3 and 4. You may break this up into separate files as long as README has pointers to them. More instructions on submission will be forthcoming. Have fun!

Extra credit

You can receive some extra credit by creating a visualization system for your search algorithm. The visualization system should work between the algorithm and the problem as a set of wrappers for goal-p, generate, and rank-fun. It should create output, textual or graphical, which helps the user visualize the search process; feel free to submit a cleaned-up version of your debugging code as a visualization as long as it's clear and useful and conforms to these guidelines. You will not receive extra credit for implementing extra search algorithms, but we will take the best four you submit to grade. You may implement simulated annealing as one of these "extra" submissions.