Artificial
Intelligence

14.6 Exercises

Exercise 14.1:

Add to the situation calculus example (also available from the course web page) the ability to paint an object. In particular, add the predicate

color(Obj,Col,Sit)

that is true if object Obj has color Col in situation Sit.

The parcel starts off blue. Thus, we have an axiom:

color(parcel,blue,init).

There is an action paint(Obj,Col) to paint object Obj with color Col. For this question, assume objects can only be painted red, and they can only be painted when the object and the robot are both at position o109. Colors accumulate on the robot (there is nothing that undoes an object being a color; if you paint the parcel red, it is both red and blue - of course this is unrealistic, but it makes the problem simpler).

Axiomatize the predicate color and the action paint using situation calculus.

You can do this without using more than three clauses (as well as the aforementioned clause defining the color in the initial situation), where none of the clauses has more than two atomic symbols in the body. You do not require equality, inequality, or negation as failure. Test it in AILog.

Your output should look something like the following:

ailog: bound 12.
ailog: ask color(parcel,red,S).
Answer:  color(parcel,red, do(paint(parcel,red), 
                             do(move(rob,storage,o109),
                               do(pickup(rob,parcel),
                                 do(move(rob,o109,storage),
                                   init))))). 

Exercise 14.2:

In this question, you will add a more complicated paint action than in previous exercise.

Suppose the object paint_can(Color) denotes a can of paint of color Color.

Add the action paint(Obj,Color) that results in the object changing its color to Color. (Unlike the previous question, the object only has one color). The painting can only be carried out if the object is sitting at o109 and an autonomous agent is at position o109 carrying the can of paint of the appropriate color.

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

1. 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.
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 do not have to run cases with a large run time to do this problem.
3. 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.

Exercise 14.4:

In this question, you will investigate using event calculus for the robot delivery domain.

1. Represent the move action in the event calculus.
2. Represent each of the sequences of actions in Example 14.10 in the event calculus.
3. Show that event calculus can derive the appropriate goals from the sequence of actions given in part (b).

Exercise 14.5:

Suppose that, in event calculus, there are two actions, Open and Close, and a relation opened that is initially, at time 0, false. Action Open makes opened true, and action Close makes opened false. Suppose that action Open occurs at time 5, and action Close occurs at time 10.

1. Represent this in event calculus.
2. Is opened true at time 3? Show the derivation.
3. Is opened true at time 7? Show the derivation.
4. Is opened true at time 13? Show the derivation.
5. Is opened true at time 5? Explain.
6. Is opened true at time 10? Explain.
7. Suggest an alternative axiomatization for holds that has different behavior at times 5 and 10.
8. Argue for one axiomatization as being more sensible than the other.

Exercise 14.6:

Give some concrete specialization operators that can be used for top-down inductive logic programming. They should be defined so that making progress can be evaluated myopically. Explain under what circumstances the operators will make progress.

Exercise 14.7:

For the representation of addition in Example 14.20, it was assumed that observed z-values would all be digits. Change the representation so that the observed values can be digits, a blank, or other. Give appropriate probabilities.

Exercise 14.8:

Represent the electrical domain of previous chapters in ICL, so that it will run in AILog. The representation should include the probabilistic dependencies of Example 6.11 and the relations of Example 12.11.