Introduction to Artificial Inteligence

Question 1)

   1) FALSE. There are well known problems in AI where simple FOL fails, such
             as dealing with uncertainty, etc. Additionally, the reasoning in FOL is not
             guaranteed to be efficient (undecidable!)

   2) FALSE. Nevertheless, there exist applications where FOL is useful, in particular
             specific problem instances can be easy in practice.

   3) FALSE. Knowing a bound on terminal node values allows for pruning in many cases
             (for example, if an operator that results in a maximum score with high probability
             is known in one branch, and an operator that results in a worst score with high
             probability, there is no need to examine other branches in these subtrees).

   4) TRUE.  An admissible heuristic leads to the optimal solution in A*. If
             h(n) is admissible, then h1(n) = h(n)/2 is even MORE optimistic
             (and also 0 for a goal state) and is also admissible.


Question 2)

      a) FOL representation:

      1.   Person(Moshe) and Forall(x)   Person(x) => Exists(y)  Owns(x,y) and Vehicle(y)

      2.   Forall(x) Vehicle(x) => Boat(x) or Aircraft(x)

      3.   Forall(x) (Person(x) and Exists(y) Boat(y) and Owns(x,y)) => CanSail(x)

      Observe that the English sentence is ambiguous, it does not necessarily imply that
      the owner is a person, although this is how we usually interpret it. The alternate
      meaning is also OK, in which case we would have:

           Forall(x) (Exists(y) Boat(y) and Owns(x,y)) => CanSail(x)

      4.   Forall(x) (Person(x) and Exists(y) Aircraft(y) and Owns(x,y)) => CanFly(x)

      5.   Forall(x) (CanFly(x) or CanSail(x)) => Rich(x)


      b) Conversion to CNF:

      1a.   Person(Moshe) 
      1b.   not Person(x1) or Owns(x1,V(x1))
      1c.   not Person(x2) or Vehicle(V(x2))

      Where V(.) is a Skolem function of one argument due to the existential y within the scope of
      the universally quantified x.

      2.    not Vehicle(x3) or Boat(x3) or Aircraft(x3)

      3.    not Person(x4) or not Boat(y1) or not Owns(x4,y1) or CanSail(x4)

      4.    not Person(x5) or not Aircraft(y2) or not Owns(x5,y2) or CanFly(x5)

      5a.   not CanFly(x6) or Rich(x6)
      5b.   not CanSail(x7) or Rich(x7)


      c) We will use reolution to prove WITHOUT contradiction, first, in order to save
         space and time...

      Resolve 1a and 1b, unifier {x1/Moshe} to get:

      C1.   Owns(Moshe,V(Moshe))

      Resolve 1a and 1c, unifier {x2/Moshe} to get:

      C2.   Vehicle(V(Moshe))

      Resolve C2 with 2, unifier {x3/V(Moshe)} to get:

      C3.   Boat(V(Moshe)) or Aircraft(V(Moshe))

      Resolve 1a with 3, unifier {x4/Moshe} to get:

      C4.   not Boat(y1) or not Owns(Moshe,y1) or CanSail(Moshe)

      Resolve 1a with 4, unifier {x5/Moshe} to get:

      C5.   not Aircraft(y2) or not Owns(Moshe,y2) or CanFly(Moshe)

      Resolve C1 with C4, unifier {y1/V(Moshe)} to get:

      C6.   not Boat(V(Moshe)) or CanSail(Moshe)

      Resolve C6 with 5b, unifier {x7/Moshe} to get:

      C7.   not Boat(V(Moshe) or Rich(Moshe)

      Resolve C1 with C5, unifier {y2/V(Moshe)} to get:

      C8.   not Aircraft(V(Moshe)) or CanFly(Moshe)

      Resolve C8 with 5a, unifier {x6/Moshe} to get:

      C9.   not Aircraft(V(Moshe) or Rich(Moshe)

      Resolve C3 with C7, to get:

      C10.  Aircraft(V(Moshe)) or Rich(Moshe)

      Resolve C10 with C9 to get:

      C11. Rich(Moshe) or Rich(Moshe)

      Which simplifies to:

      C12. Rich(Moshe)
 
      which is what we need to prove, WITHOUT using refutation.

      To complete a FEFUTATION proof, we need to add the negated form of the query "Rich(Moshe)":

      CNEG.  not Rich(Moshe)

      Obviously, CNEG resolves with C12 to get the empty clause, completing the
      refutation proof.

     Note that many other proofs are available, e.g. starting by resolving CNEG with 5a, etc.
     which would also earn full credit, but we simply chose one where both proof types are the
     same (except for 1 more step in the refutation proof).

     d) Sentence 2 cannot be represented as a Horn formula, and forward chaining needs
        the KB as Horn formulas. Since sentence 2 is necessary for the proof, forward chaining
        alone cannot be used to prove Rich(Moshe).  Note that this is essentially the same
        example from the book that shows why generalized modus ponens is incomplete,
        with a few extras...
      

Question 3)

     a) For the problem as stated, sum of Manhattan distances is NOT an admissible heuristic.
        For example, consider the following counterexample:

            123             123
            486             456
            75              78

          Node n        Final state

         In this example, the true path cost from n to the goal is 1 (just 1 exchange),
         but the total Manhattan distance is 2 (1 for each of the tiles 5, 8).

     b) If the search problem is reformulated such that the cost of the exchange operator is 2,
        in the new search space the Manhattan distance heuristic is admissible, because no
        operator can change the Manhattan distance by more than the operator cost, and
        the heuristic is exact for the goal state.

     c) Using the search problem of (a), and the Manhattan distance heuristic with A* search,
        we get the following seach tree (only first 3 expansions shown):

                     153
                     48
                     726

     Initial state, f=h=5  (2 for the tile 2, and 1 each for tiles 8, 5, 6). Expanded into:

   15          153         153         183         153
   483         4 8         486         45          42 
   726         726         72          726         786
                                                    *
  h=6,f=7    h=6,f=7     h=4,f=5     h=5,f=6     h=3,f=4   

      The last state has f=4, which is lowest, and is thus the one expanded, to get:

   153        123        153        15         153     
   48         45         426        423        4 2
   726        786        78         786        786     
               *
  h=5,f=7   h=1,f=3    h=2,f=4    h=4,f=6    h=4,f=6   

      Now, the second state * above has f=3, which is lowest of all, and is expanded, to get:

   123        123        153        12         123     
   48         456        42         453        4 5
   756        78         786        786        786     
               *
  h=3,f=6   h=0,f=3    h=3,f=5    h=2,f=5    h=2,f=5

Now, if we attempt another expansion, we have the 2nd state above with f=3, which is
a goal state, and is thus returned as the optimal solution (frequently, an inadmissible
heuristic will also cause an optimal solution in A*, although there is NO GUARANTEE that
the optimum will be found).