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.
-
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!
-
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.
-
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.
-
Explain your algorithms, problems, and results.
- Why did certain
algorithms work better?
- Is there one algorithm that was always best?
- Would that algorithm be best in every domain?
- Were certain search
algorithms easier to write than others (and why)?
- What properties of a
problem make it hard for different algorithms to search?
- Do you hate
LISP? Why did it work well or poorly as a language for implementing
search?
- Are there other questions that are important?
- What's your TA's middle name?
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:
- breadth first search =
breadth
,
- iterative deepening =
deepen
,
- A* =
a-star
,
- iterative deepening A* =
deepen-a-star
, and
- beam search =
beam
.
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:
- A tree created on the fly. Have parameters to tune the average
branching factor, depth, and a function that takes the depth of a
state and returns T if it's a goal state. You can even embed that
information in the state. Note, however, that since
this is generated on the fly, it's a hard domain to test your
solutions on!
- Airline flights between cities. Make a file format for describing
cities and the airline connections between them (including ticket
cost). Now, you can read the map (graph, really) into memory and have
your algorithm search for the cheapest fares between cities.
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.