2006 solutions

Question 5

a) Having a heuristic value of zero everywhere is not optimistic because if the value is negative, the algorithm will overshoot its distance estimate.

b) No, you can't write a bound. There is no guarantee to find a path with greedy search (as alpha approaches infinity).

c) Speed up the search by relaxing the problem— trade speed for optimality.

d) If q is on the optimal path, then the algorithm won't find the optimal path since it won't be visited. Unless the algorithm visits node q, it won't know whether or not its optimal.

e) Relax constraints of the problem. For example, an algorithm could ignore walls in a map as its finding a path.

Question 6

(a) (on A Table) (clear B) -> (on A B)

(b) (on C Table) (clear A)

(c) Any intermediate step — (on B C)

(d) Yes. (fill out)

(e) puton(c,d) interferes with newtower(D) and (1) threatens (2), labeling left to right

(f) # threats - # goals satisfied

Question 7

a) If the probability of going toward the goal is high, then the algorithm could potentially spend a lot of time getting stuck in obstacles. If the probability is low, then the algorithm will spend a lot of time exploring without going to the goal. The optimal probability depends on the search space.

Question 8

a) You can't guarantee an algorithm will find a global minimum with a finite number of samples. Diagram

Question 10

Question 11

(c) Both try to ascribe a value to a future state without knowing its accuracy or not.