Exercise 14.3 AILog performs depth-bounded search. You will notice that the processing time for the previous questions was slow, and we required a depth bound that was close to the actual depth bound to make it work in a reasonable amount of time.

In this question, estimate how long an iterative deepening search will take to find a solution to the following query:

ask sitting_at(parcel,lab2,S).

(Do not bother to try it – it takes too long to run.)

(a) Estimate the smallest bound necessary to find a plan. [Hint: How many steps are needed to solve this problem? How does the number of steps relate to the required depth bound?] Justify your estimate.

(b) Estimate the branching factor of the search tree. To do this you should look at the time for a complete search at level k + 1 versus a complete search at level k. You should justify your answer both experimentally (by running the program) and theoretically (by considering what is the branching factor).

You do not have to run cases with a large run time to do this problem.

(c) Based on your answers to parts

(a) and (b), and the time you found for some run of the program for a small bound, estimate the time for a complete search of the search tree at a depth one less than that required to find a solution.

Justify your solution.