CS322 Fall 1999
Module 10 (Representing Actions)
Assignment 10

Due: 1:30pm, Friday 19 November 1999.

In the file ~cs322/cilog/delrob_strips.pl (also available on the web) is a STRIPs representation of the delivery robot. There is also a STRIPs planner in ~cs322/cilog/strips_strips.pl (also available on the web). The bottom of this file shows some queries you can try, for example, the following is an example query (reformatted to show the plan better): 

cilog: ask achieve(at(k1,lab2),init,S,6,N).
Answer: achieve(at(k1,lab2),init,
          do(move(rob,o103,lab2),
            do(unlock(rob,door1),
              do(move(rob,mail,o103),
                do(pickup(rob,k1,mail),
                  do(move(rob,o103,mail),
                    do(move(rob,o109,o103),
                      init)))))),6,0).
You will need to play with these programs to do this assignment.

Question 1

Suppose that we also have buckets that can be filled by a tap in room o111. Assume there is an action fill(B) to fill a bucket B that the robot is carrying in room o101. Bucket b1 is initially empty in the storage room.

An autonomous agent can wet (using the action wet(Obj,B)) an object Obj by pouring water (from the bucket B) onto that object, as long as the agent is carrying the full bucket at the same location as Obj. Objects stay wet. Suppose we have the predicate is_wet(Obj) that is true if Obj is wet.

  1. Represent the actions and any needed derived relations, and the initial situation, so you can answer queries such as the following (again we have formatted the output to make it more readable): 
    cilog: ask achieve(is_wet(parcel),init,S,8,R).
Answer: achieve(is_wet(parcel),init,
     do(wet(parcel,b1),
       do(move(rob,o109,storage),
         do(move(rob,o111,o109),
           do(fill(b1),
             do(move(rob,o109,o111),
               do(move(rob,storage,o109),
                  do(pickup(rob,b1,storage),
                    do(move(rob,o109,storage),init)))))))),8,0).
  2. Explain why the STRIPS planner can't find the shortest plan. [You have to think about what is the shortest plan.]

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:

  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.]

Question 3

[Bonus] Estimating values is an important skill.

How many rain drops fall on Vancouver in a typical November?

You can get 2 marks for being within one order of magnitude and 1 mark for being within 2 orders of magnitude.

Question 4

For each question in this assignment, say how long you spent on it. Was this reasonable? What did you learn?
David Poole