Go backward to Question 1
Go up to Top
Go forward to Question 3
Question 2
Using SLD resolution directly on the on the
situation calculus or STRIPs
representation can be very slow. How slow? That is what we'll try
to estimate here.
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