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)