CSE 150 Homework
#2
Date assigned: April 12, 2007
Date due: Beginning of class April 19,
2007
You can work
alone or in groups of at most 3. Homeworks are due at the beginning of class,
printed and stapled and should be presented in the order in which they were
assigned. 10 points will be based on style; your homework should be free of
spelling and grammatical errors and should present information in a way that
makes it easy to read. If drawing is required, the drawing may be done by hand
or using a computer. Points will be deducted for not following these
instructions. No late submissions will be accepted.
- Does a finite state space always
lead to a finite search tree? Why or why not? Can you be more precise
about what types of state space always lead to finite search trees?
(Adapted from R&N 3.6)
- R&N 3.8
- R&N 3.17
- R&N 4.3
- R&N 4.6
- R&N 4.11
- (This one is taken from a previous
midterm.) You are part of a design team for an autonomous robot named
Max. Max is to be used in
time critical applications (pizza delivery), and thus he has to move as
efficiently as possible. It
is your job to design his navigation plan. The prototype moves along a
track with a limited number of routes from one destination to
another. You decide to use
space state search. To test
your approach, you are given a sample environment, consisting of
"nodes" connected by the track that Max moves along. The nodes are labeled A through G,
and each track has an associated time cost based on how long it takes Max
to traverse its length. The
nodes, and their associated connecting nodes and costs are as follows:
|
From: |
To: |
|
A |
B with cost 50 |
|
|
C with cost 40 |
|
|
D with cost 40 |
|
|
|
|
B |
C with cost 40 |
|
|
E with cost 40 |
|
|
F with cost 50 |
|
|
|
|
C |
F with cost 30 |
|
|
B with cost 40 |
|
|
|
|
D |
G with cost 100 |
|
|
|
|
E |
G with cost 50 |
|
|
|
|
F |
G with cost 30 |
Note that the tracks are one-way.
Given that Max wants to go from A to G, using as little time as possible, you first attempt to use Breadth First Search to generate a minimal solution. The following tree represents this effort:
Nodes
in this tree have been fully expanded (although their successors are not shown
since they are not fully expanded).
This discovers a path to G
of length 140, which is not optimal, and took a good deal of effort to produce
(expanding 10 nodes to find a path which only used 3 nodes).
- What is the bug in your Breadth
First Search Algorithm, compared to the way you were shown in class?
- Which blind search technique should
you have used in this space?
- Now try DFS on this space, and see
if it provides a better solution. Assume that the open list that is
generated by DFS follows the same order as presented in the above
table. For example, the next
successors of A are (in order) B then C then D. Write the tree for DFS as above, and write the length
of the solution (if any).
- What would happen if we used DFS on
this space, but there was no link from C to F. (i.e. C only leads to B with cost 40). How could we avoid this problem?
- The demo is due tomorrow, and your
boss threatens to fire you. To placate her, you decide to try a heuristic
search. A reasonable heuristic for this might be the straight-line
distance from each node to G. This is given in the following table for
your heuristic function, h(n):
|
Node |
h(n): absolute distance
from n to G |
|
==== |
==== |
|
A |
100 |
|
B |
60 |
|
C |
50 |
|
D |
80 |
|
E |
40 |
|
F |
25 |
|
G |
0 |
A: g=0 h=100 f=100
Now using A*, complete the following heuristic search tree,
labeling values for h(n), g(n), and f(n).
