CSC 550: Introduction to Artificial Intelligence
CSC 650: Advanced Artificial Intelligence
Spring 2003
HW2: State Space Search
This assignment involves solving state space problems and
comparing the
performance of the different search strategies discussed in class.
MzScheme provides a utility function, time, that can be
useful in profiling
code. The time function, when given an expression as
input, evaluates
that expression and reports the number of milliseconds of CPU time
taken for
the evaluation. It even identifies the amount of CPU time taken by
garbage
collection, so that number can be subtracted out to determine the
amount of time spent doing actual computation.
Unfortunately, the time function does not produce
meaningful results if
the execution is extremely fast, as will be the case in some
instances here.
Instead, you will want to use the following function:
(define (time-reps expr numreps)
(define (time-help rep)
(let ((val (eval expr)))
(if (= rep numreps)
val
(time-help (+ rep 1)))))
(time (time-help 1)))
The first input to the time-reps function is a quoted expression to be
evaluated, and the second input is a number of repetitions. For example, the call
(time-reps '(reverse '(1 2 3 4 5 6))
1000)
would reverse the list 1000 times and
report the total CPU time. Subtracting out the garbage collection
time then dividing
by 1000 will give a fairly consistent and accurate timing for each
reverse.
- For each of the three state space problems discussed in class:
- travel.scm: 'Omaha --> 'LosAngeles
- jugs.scm: '(0 0) --> '(2 0)
- tiles.scm: '(1 2 3 8 6 space 7 5 4) --> '(1 2 3 8 space 4
7 6 5)
compare the performances of the search strategies:
DFS, DFS-nocycles,
BFS, BFS-nocycles, and DFS-deepening.
That is, when
the strategy produces an answer, report the execution time (not
counting
garbage collection). Comment on the apparent tradeoffs between the
strategies.
- Consider the following problem:
Three missionaries and three cannibals seek to cross a river, say
from the
left bank to the right bank. A boat that may be navigated by any
combination
of one or two people is available on their side of the river. If the
missionaries on either side of the river are outnumbered at any time
by
cannibals, the cannibals will indulge in their anthropophagic
tendencies
and do away with the missionaries. Find a sequence of boat trips
that will
permit all the missionaries and cannibals to cross the river safely.
- Define a state space for this problem. In particular,
determine how a state
will be represented and define the GET-MOVES function to generate
all states
reachable from a given state.
- Attempt to solve this problem using the various uninformed
search
control strategies provided, i.e. DFS,
DFS-nocycles,
BFS, BFS-nocycles, and DFS-deepening.
Discuss the behaviors of each of these approaches. For example,
if a strategy
fails, explain why this would happen. Similarly, if one strategy
outperforms another, explain why.
- Consider a generalization of the previous problem where there
are five
missionaries and five cannibals that need to cross the river. The
boat can
handle up to three people, but the number of cannibals on the boat
must never
exceed the number of missionaries. As in the previous question,
define a
state space for this problem, implement the GET-MOVES function, attempt to solve the
problem using
each of
the uninformed strategies, and explain your results.
ADDITIONAL QUESTION FOR GRADUATE STUDENTS:
- The implementation of DFS with iterative deepening that was provided for
you has one undesirable feature. As is, this function will never halt with an answer
of #f, even with a finite search space. Instead, it will just keep extending
the depth bound and repeating the same search. Modify this code so that it is able to
recognize when the search space is exhausted and terminate accordingly. Note: your
modification should not utilize destructive assignments.