AI MidTerm 1, solutions
----------------------------
Question 1:
-----------


a)  Branch A1 on left gives 20, as opposed to 0 for A2. So
    A1 is the best move for A.

b)  Once the value 30 is found, A can get at least 30 in this
    choice for B. So no need to look at the 0
    branch since B will not pick this option anyway.
    Also, in the A2 branch, once B can get 0 there is no need to
    look at the other choice for B, since B is guaranteed better (less) than
    0, so A will never take this move anyway.

c) In A1 branch, the choices for B are 20 and 30, expected value 15.
   In A2 branch, cjoices for B are 0 and 100, expected value 50. So
   in this case the best move for A is A2.


Question 2:
-----------

a) KB in FOL:

Statement 1 is best described using 2 separate sentences:
1a. forall x Printer(x) => Elect(x) 
1b. forall x Router(x) => Elect(x) 

2.   forall x (SFY(x) and Elect(x)) =>  exists y HasPart(x,y) and Bomb y

3.   forall x (exists y HasPart(x,y) and Bomb(y)) => Bomb(x)

4.   SFY(Pack1) and (Printer(Pack1) or Router(Pack1))

b) In CNF:

1a.  not Printer(x) or Elect(x) 
1b.  not Router(x) or Elect(x) 

2a. not SFY(x) or not Elect(x) or HasPart(x,BPO(x)) 
2b. not SFY(x) or not Elect(x) or Bomb(BPO(x))

Where BPO() is a Skolem function replacing the existentially quantified
variable y  which is in the scope of the universally quantified x.

3.  not HasPart(x,y) or not Bomb(y) or Bomb(x)

Here y is actually universally quantified, as the existential
quantification of y is in the LHS of an implication which is
in essence a negation.

4a. SFY(Pack1)
4b. Printer(Pack1) or Router(Pack1)


c) Need to prove:

Q:  Bomb(Pack1)

We thus add its negation in CNF to the KB:

Q': not Bomb(Pack1)

Proof proceeds as follows:

Resolve 4a with 2a, unifier {x|Pack1}:

5:  not Elect(Pack1) or HasPart(Pack1,BPO(Pack1)) 

Resolve 4a with 2b, unifier {x|Pack1}:

6:  not Elect(Pack1) or Bomb(BPO(Pack1))

Resolve 4b with 1a, unifier {x|Pack1}:

7: Router(Pack1) or Elect(Pack1)

Resolve 7 with 1b, unifier {x|Pack1}:

8: Elect(Pack1) or Elect(Pack1)

which is equivalent to:

9: Elect(Pack1)

Resolve 9 with 5, empty unifier:

10: HasPart(Pack1,BPO(Pack1)

Resolve 9 with 6,, empty unifier:

11: Bomb(BPO(Pack1))

Resolve 10 with 3, unifier {x|Pack1, y|BPO(Pack1)}

12: not Bomb(BPO(Pack1)) or Bomb(Pack1)

Resolve 11 with 12, empty unifier:

13: Bomb(Pack1)

Actualy proving what we needed to prove directly. But to complete
the refutation proof, Resolve 13 with Q' to get the empty clause
(a contradiction).


d) Proof with forward chaining:

   a) Not possible, since we must use 4b, which is not a Horn clause
      in the proof.

   b) Possible, if we have Printer(Pack1) can use 1a to get
      Elect(Pack1). Then with 2a and 4a we get HasPart(Pack1, BPO(Pack1)) and
      with 2b and 4a get Bomb(BPO(Pack1)). Finally using the latter facts in 3 we
      get Bomb(Pack1).

      All steps used only clauses in Horn form and GMP in the forward direction.
 


Question 3:
-----------

a) Not admissible. For example, the following state:

    2  3

 4  5  6

 7  8  1

Is one move away from the goal, and can be reached with a cost of
h*=1 by trasporting the "1" tile into the final position. However,
the Manhattan distance heuristic gives a value h=4 for this
position. We have h > h* so h is not admissible.


b) The same heuristic h is admissible for this new problem statement.
   That is because a transport operation can decrease the Manhattan distance
   value by 4 at most, and costs 4. So no operator can decrease the
   Manhattan distance h by more than its cost. Also, h(goal) = 0.
   So h is admissible.


c) Initial state I:

 8  2  3

 4  5  6

    7  1

Has h=8 and thus f=8. There are 5 successors:

S1: h=7, g=1, f=8

 8  2  3

 4  5  6

 7     1

S2: h=9, g=1, f=10

 8  2  3

    5  6

 4  7  1

S3: h=6, g=1, f=7

 8  2  3

 4  5  6

 1  7

S4: h=12, g=1, f=13

 8  2

 4  5  6

 3  7  1

S5: h=6, g=1, f=7

    2  3

 4  5  6

 8  7  1

Now there are 2 cases with f=7, S3 and S5 (neither on the optimal path, BTW),
say we pick S3. Again 5 successors, including I again, which we assume is dropped
to to duplicates check.

S6: h=7, g=2, f=9

 8  2  3

 4  5  6

 1     7

S7: h=7, g=2, f=9

 8  2  3

 4  5  

 1  7  6

S8: h=4, g=2, f=6

    2  3

 4  5  6

 1  7  8

S9: h=8, g=2, f=10

 8  2  

 4  5  6

 1  7  3


No pick f(S8)=6. Again 5 successors,
including S3 which is dropped. 

S10: h=5, g=3, f=8

 2     3

 4  5  6

 1  7  8

S11: h=5, g=3, f=8

 4  2  3

    5  6

 1  7  8

S12: h=2, g=3, f=5

 1  2  3

 4  5  6

    7  8

S13: h=6, g=3, f=9

 3  2

 4  5  6

 1  7  8

This time, only one best f(S12) = 5, so we expand it. 5 Successors, of
which one is S3 which is dropped.

S14: h=2, g=4, f=6

 1  2  3

 4  5  6

 8  7 

S15: h=1, g=4, f=5

 1  2  3

 4  5  6

 7     8

S16: h=6, g=4, f=10

 1  2

 4  5  6

 3  7  8

S17: h=3, g=4, f=7

 1  2  3

    5  6

 4  7  8

Now best is f(S15) = 5, with 5 successors including  S12 (dropped).

S18: h=0, g=5, f=5

 1  2  3

 4  5  6

 7  8

S19: h=4, g=5, f=9

    2  3

 4  5  6

 7  1  8

S20: h=2, g=5, f=7

 1  2  3

 4     6

 7  5  8

S21: h=4, g=5, f=9

 1  2  

 4  5  6

 7  3  8

And this completes 5 expansions. If continued, we pick S18,
which is a goal so the algorithm returns this node as a solution,
but not an optimal solution.