CS188
Spring 1995
Midterm 2 - SOLUTION
1. The two important parts of this problem were correctly determining the
preconditions and effects of each step in the plan, and then adding the
causal and ordering links to each precondition. It was necessary to
draw each individual causal link to each precondition in the plan.
START: Preconds: none
Effects: On(A,B) ^ On(B,Table) ^ Clear(A) ^ Clear(Table)
PUTON(A,Table) : Preconds: Clear(A) ^ Clear(Table) ^ On(A,B)
Effects: Clear(A) ^ On(A,Table) ^ Clear(B) ^ ~On(A,B) ^ ~Clear(Table)
PUTON(B,A) : Preconds: Clear(A) ^ Clear(B) ^ On(B,Table)
Effects: Clear(B) ^ On(B,A) ^ Clear(Table) ^ ~On(B,Table) ^ ~Clear(A)
FINISH: Preconds: On(A,Table) ^ On(B,A)
Effects: none
Causal and ordering links:
From action To precond In action
----------- ---------- ---------
Start On(A,B) Puton(A,Table)
Start Clear(Table) Puton(A,Table)
Start On(A,B) Puton(A,Table)
Start On(B,Table) Puton(B,A)
Puton(A,Table) Clear(A) Puton(B,A)
Puton(A,Table) Clear(B) Puton(B,A)
Puton(A,Table) On(A,Table) Finish
Puton(B,A) On(B,A) Finish
2. In the first part you simply add the effects from the action PUTON(A,Table)
to the effects of START, assuming table is still clear.
START: Preconds: none
Effects: ~On(A,B) ^ On(B,Table) ^ Clear(A) ^ Clear(Table) ^ On(A,Table) ^ Clear(B)
PUTON(B,A) : Preconds: Clear(A) ^ Clear(B) ^ On(B,Table)
Effects: Clear(B) ^ On(B,A) ^ Clear(Table) ^ ~On(B,Table) ^ ~Clear(A)
FINISH: Preconds: On(A,Table) ^ On(B,A)
Effects: none
Causal and ordering links:
From action To precond In action
----------- ---------- ---------
Start On(B,Table) Puton(B,A)
Start Clear(A) Puton(B,A)
Start Clear(B) Puton(B,A)
Start On(A,Table) Finish
Puton(B,A) On(B,A) Finish
In the second part, you need to change the effects of START to reflect the presence
of C on B, then add the step PUTON(C,TABLE) with its preconditions and effects.
START: Preconds: none
Effects: ~On(A,B) ^ On(B,Table) ^ Clear(A) ^ Clear(Table) ^ On(A,Table) ^ ~Clear(B)
^ On(C,B) ^ Clear(C)
PUTON(C,Table) : Preconds: Clear(C) ^ Clear(Table) ^ On(C,B)
Effects: Clear(C) ^ On(C,Table) ^ Clear(B) ^ ~On(C,B) ^ ~Clear(Table)
PUTON(B,A) : Preconds: Clear(A) ^ Clear(B) ^ On(B,Table)
Effects: Clear(B) ^ On(B,A) ^ Clear(Table) ^ ~On(B,Table) ^ ~Clear(A)
FINISH: Preconds: On(A,Table) ^ On(B,A)
Effects: none
From action To precond In action
----------- ---------- ---------
Start On(C,B) Puton(C,Table)
Start Clear(Table) Puton(C,Table)
Start On(C,B) Puton(C,Table)
Start On(B,Table) Puton(B,A)
Start Clear(A) Puton(B,A)
Puton(C,Table) Clear(B) Puton(B,A)
Start On(A,Table) Finish
Puton(B,A) On(B,A) Finish
3. A COMPLETE plan is one in which every precondition of every step
is achieved by some other step.
A CONSISTENT plan is one in which there are no contradictions in the
ordering or binding constraints.
To demonstrate an inconsistent plan, you simply need to have a loop, where
the precondition of a step is only achieved by a later step
--------
| |
v |
action1 |
| |
| |
v |
action2 |
| |
----------
4.a) If A and B are independent, then P(A^B) = P(A)*P(B).
P(A|B) = P(A^B)/P(B) = P(A) =x
b) If A and B are mutually exclusive, then P(A^B) = 0
P(A|B) = 0/P(B) = 0
5. From the given information, we know
P(C) = 0.4
P(~C) = 1 - P(C) = 0.6
P(S|C) = 0.6
P(S|~C) = 0.3
From Bayes' Law, we know that
P(S|C) P(C)
P(C|S) = -----------
P(S)
We know both probabilities in the numerator from the given information. To
find P(S) we need to normalize.
P(S) = P(S|C)P(C) + (S|~C)P(~C)
All four of these probabilities are given, so we calculate that
P(S) = 0.6*0.4 + 0.3*0.6 = 0.42
P(C|S) = (0.6*0.4)/0.42 = 4/7 = 0.57
6) All influence arcs will go from arcs added earlier to those added later.
Arc from Arc to
--------- -------
F E,D
E D,C,B,A
D C,B,A
C B,A
B A
A none
7) There are two ways you can calculate P(A|B^C), both equally correct and simple.
First step in both methods is to expand using the product rule
P(A^B^C)
P(A|B^C) = -------
P(B^C)
Method 1: Expand again using the product rule
P(A^B^C) P(C|A^B)P(A|B)
------- = --------------
P(B^C) P(C|B)
The first probability in the numerator we get from the table P(C|A^B) = 0.1
We next recognize that A and B are conditionally independent (from the diagram),
so P(A|B) = P(A) = 0.5
To get P(C|B) we need to normalize: P(C|B) = P(C|B^A)P(A) + P(C|B^~A)P(~A)
= 0.1*0.5 + 0.2*0.5 = 0.15
Doing the math in the original equation gives us (0.1*0.5)/0.15 = 0.33
Method 2: Using the fact that in a belief net, each node is conditionally independent
of its predecessors given its parents, we have
P(x1...xn) = P(Xi|Parents(Xi)) for all i
P(A^B^C) = P(A)P(B)P(C|A^B) since A and B have no parents and are
the parents of C
We recognize that we can normalize the denominator
P(B^C) = P(A^B^C) + P(~A^B^C)
P(A^B^C) = P(A)P(B)P(C|A^B) = 0.5*0.7*0.1 = 0.035
P(~A^B^C) = P(~A)P(B)P(C|~A^B) = 0.5*0.7*0.2 = 0.070
P(B^C) = P(A^B^C) + P(~A^B^C) = 0.035+0.070 = 0.105
P(A^B^C)
P(A|B^C) = ------- = 0.035/0.105 = 0.33
P(B^C)