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)