Prev Up Next
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/ (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:

  1. 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.
  2. 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.
  3. 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.]
  • Solution

  • David Poole

    Prev Up Next