Description

Using the situation calculus, complete the following.
(a) Write a sentence describing the initial situation.
(b) Write the precondition and effect axioms for the actions.
(c) Write a sentence of the form ∃s.φ(s) that asserts the existence of the final goal situation.
(d) Write a ground situation term σ such that σ denotes the desired goal situation.
2. Consider the following blocks world planning problem. There are a collection of blocks: a block can be on the table, or on top of another block. There are three predicates: clear(x): there is no block on top of block x; on(x,y): block x is on top of block y; and onTable(x): block x is on the table. There are three actions: move(x,y,z): move block x from block y onto block z, provided x is on y, both x and z are clear; moveFromTable(x,y): move block x from the table onto block y, provided x is on the table, both x and y are clear; and moveToTable(x,y): move block x from block y onto the table, provided x is on y, and x is clear.
a
b
c
a
b
c
The initial state isThe goal state is
(a) Write the STRIPS representation of the actions, the initial KB, and the goal.
(b) Use reachability analysis to compute the heuristic value for the initial state. Draw the state and action layers. For each call of CountActions, indicate the values of G,GP,GN, and A.
3. Consider the following example: Metastatic cancer is a possible cause of a brain tumor and is also an explanation for an increased total serum calcium. In turn, either of these could cause a patient to fall into an occasional coma. Severe headache could also be explained by a brain tumor.
(a) Represent these causal links in a belief network. Let a stand for metastatic cancer, b for increased total serum calcium, c for brain tumor, d for occasional coma, and e for severe headaches.
(b) Give an example of an independence assumption that is implicit in this network.
1
(c) Suppose the following probabilities are given:
P(a) = 0.2
P(b|a) = 0.8 P(b|¬a) = 0.2
P(c|a) = 0.2 P(c|¬a) = 0.05
P(e|c) = 0.8 P(e|¬c) = 0.6
P(d|b,c) = 0.8 P(d|¬b,c) = 0.8
P(d|b,¬c) = 0.8 P(d|¬b,¬c) = 0.05
and assume that it is also given that some patient is suffering from severe headaches but has not fallen into a coma. Calculate joint probabilities for the eight remaining possibilities (that is, according to whether a, b, and c are true or false).
(d) According to the numbers given, the a priori probability that the patient has metastatic cancer is 0.2. Given that the patient is suffering from severe headaches but has not fallen into a coma, are we now more or less inclined to believe that the patient has cancer? Explain.
4. Consider the following belief network:
P(a) = 0.9 P(d|b) = 0.1
P(b) = 0.2 P(d|¬b) = 0.8
P(c|a,b) = 0.1 P(e|c) = 0.7
P(c|a,¬b) = 0.8 P(e|¬c) = 0.2
P(c|¬a,b) = 0.7 P(f|c) = 0.2
P(c|¬a,¬b) = 0.4 P(f|¬c) = 0.9
(a) Compute P(e) using VE. You should first prune irrelevant variables. Show the factors that are created for a given elimination ordering.
(b) Suppose you want to compute P(e|¬f) using VE. How much of the previous computation can be reused? Show the factors that are different from those in part (a).
2