In the file `~cs322/cilog/back_strips.pl`

(also available
on the web) is a direct meta-interpreter for
STRIPs in CILog.

Note that cilog does depth-bounded search.
The command *bound N.* sets the depth-bound to *N*.

Consider the query:

ask holds_in(carrying(rob,parcel)& sitting_at(rob,lab2),S).

Assume that we are using CILog to do an iterative deepening search. You are to
estimate for how long the search takes for the complete search at depth
*D-1* where *D* is the depth needed for the shortest solution. To do
this you should:

- Estimate the smallest bound needed to find a plan. Hint: how many actions are needed to solve this problem? How does the number of steps relate to the depth-bound needed? [If you know the shortest plan it's not computationally difficult to find the depth-bound needed to prove it.] Justify your estimate.
- 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 don't need to run cases with a large runtime to do this. - Based on your answers to parts 1 and 2, 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 the highest depth that you won't find a solution. Justify your estimate. [Also say what computer you are using.]

David Poole