Introduction to Artificial Inteligence

Assignment 3 (solution *under construction *)


Homework assignment - simulators, agents, search, games, logic, inference

1) (search and logic)
   Finding an explanation for observed evidence is known as abductive
   reasoning.  The input is a KB of definite Horn clauses (i.e. "rules",
   see below), and a function that assignes each literal a
   non-negative cost.
   Also part of the input is a set of literals E (the observed
   evidence) to be explained.   
   An explanation is a set of assumed literals A, that together with KB
   proves E.

   In this exercise, we wish to solve the weighted abduction
   version: given E, find an explanation  A where
   the sum of the costs of the literals in A is minimal. For example, consider
   the following KB:

   R1:        a -> b
   R2:  b and c -> d
   R3:        a -> c
   R4:        x -> d

   The cost of assumption for literals is as follows:
      cost(b) = 7
      cost(c) = 6
      cost(d) = 20
      cost(a) = 10
      cost(x) = 100

   For the case where we wish to find an explanation for E = {d},
   one possible explanation is A = {d} for a cost of 20.
   But it is not an optimal explanation, because A = {a}
   also an explanation, with a weight of 10.

   a) Formalize the weighted abduction problem as a search problem,
      where the state is a partial solution A', and where an operator adds
      any literal not in the partial solution.

ANS: 
     Initial state: A = {}.
     Goal test: E follows from A union KB
     Operators (one of several possibilities):
          Add any literal to A that is not already in A.
     Path cost: for each operator, the cost of the added literal,
     


   b) Same as (a), but this time a lexicographical ordering of literals
      is given (say a, then b, etc.), and one can add a literal x only
      if no literal y greater than x is in A'.

ANS: 
     Initial state: A = {}.
     Goal test: E follows from A union KB
     Operators (one of several possibilities):
          Add any x literal to A that is not already in A, provided that
          for all y in A, y is "lexicigraphically before" x. Note that you need to
          this predicate for implementation, and that numerous
          definitions are possible.
     Path cost: for each operator, the cost of the added literal.
     

   c) Assume that we use uniform-cost search, are we assured of finding
      the minimal explanation using version a? If not, are we assured of such
      using option b? You need to sketch the proof for your answer.

ANS:
      Yes in both cases, ASSUMING COSTS ARE POSITIVE.
      This follows from the monotonicity of path costs and the
      monotonicity of the logic (i.e. that adding literals can never
      cause something that was provable to stop being provable).

      For case b you also need the fact that every A is reachable from
      the empty set despite the lexicographic restriction.

      (Observe that you need noth monotonicities, or this would not work!)

   d) We wish to use A* to perform weighted abduction. Find an
      admissible heuristic for versions a, b, (they may all be the
      same heuristic, and it does NOT have to be a GOOD heuristic).
      Now, show an execution of A* using your heuristic to solve the
      weighted abduction problem, given as input the above KB and
      the evidence to be explained E = {d}.
      Use only one of the search problem versions a, b - your choice
      (hint: which would result in the shortest trace?)

ANS:
      A trivial addmissible heuristic would be simply 0. However, let
      us do something a bit better:
         h(A) = 0 if A is a goal,
         h(A) = otherwise, cost of cheapest eligible literal not in A.

      We will use option b, so that we get a shorter trace... Assume
      the standard lexicographic ordering (a is smallest).

       Initialize:
          {} h = 6, f = 6
       Expand {} to get:
          {a} h =   0, f =  10
          {b} h =   6, f =  13
          {c} h =  20, f =  26
          {d} h =   0, f =  20
          {x} h = inf, f = 100
       Put them in the queue in this order.

       Now, get {a}, which is a goal state, and we are done...

       Note effectiveness of heuristic, because had we used 0 we would
       have gotten:
          {c} h =   0, f =   6
          {b} h =   0, f =   7
          {a} h =   0, f =  10
          {d} h =   0, f =  20
          {x} h =   0, f = 100

      And now we would try to expand {c}, and then try to expand {b}
      and only then get to {a}.

 

2) (FOL and situation calculus)
   We need to represent and reason within the following scenario, called
   the Wumpus shooting problem (based on the infamous Yale Shooting problem):
   
   a) We need to represent the following facts using FOL and situation
      calculus, using successor-state axioms:

      A) The action of drawing the bow makes it ready, if we have an arrow. (Action name: Draw)
      B) The action of waiting does nothing (Action name: Wait)
      C) If the robot is facing the Wumpus and the bow is ready,
         the action of shooting kills the Wumpus.
         Shoot also makes the arrow disappear and the bow unready.. (Action name: Shoot)
      D) In situation S0, the Wumpus is alive, the bow is not drawn, and
         the robot is facing the Wumpus and has an arrow.

      Use the following predicates to represent the above information:
         Ready(s)    :   the bow is ready in situation s
         Alive(s)    :   the Wumpus is alive in situaton s.
         HasArrow(s) :   the robot has an arrow in situation s.
         FacingWumpus(s)  : the robot is facing the Wumpus in
                            situation s.
      Obviously, you also need to use the Result(a, s) function...

ANS:
     Using successor-state axioms our axioms are per predicate rather
     than per action. Note that we make (and encode) a general frame axiom that
     nothing changes unless stated that it DID change.

     1. Axiom for Alive
        forall a, s,  Alive(Result(a, s)) iff 
          (Alive(s) and 
             not (Ready(s) and =(a, Shoot) and FacingWumpus(s)))

     2. Axiom for FacingWumpus
        forall a, s,  FacingWumpus(s) implies FacingWumpus(Result(a,s)) 

     3. Axiom for HasArrow
        forall a, s,  HasArrow(s) and not =(a, Shoot) implies  HasArrow(Result(a,s)

     4. Axiom for Ready
        forall a, s,  Ready(Result(a, s)) iff
                         ((Ready(s) and not =(a, Shoot)) or
                          (HasArrow(s) and =(a, Draw)
                          
     We also need axioms for unequal actions, and for equality but we will add only:
     5. not =(Wait, Shoot)
     5' =(x, x) 

     Also, axioms for initial state:
     6. Alive(S0)
     7. not Ready(S0)
     8. FacingWumpus(S0)
     9. HasArrow(S0)


   b) Now, we need to prove that the following sequence of actions (starting
      from situation S0): Draw, Wait, Shoot - results in Wumpus' death. 
      Proceed as follows:
      A) Represent the fact to be proved, and its negation.

ANS:
    Need to show:
         not Alive(Result(Shoot,Result(Wait,Result(Draw,S0))))

      So we add to KB:
      G': Alive(Result(Shoot,Result(Wait,Result(Draw,S0))))

      B) Convert all the knowledge you represented in A into CNF

ANS: Everything except 1-4 already in CNF so:

     1. Axiom for Alive
        not Alive(Result(a, s)) or
          (Alive(s) and 
             not (Ready(s) and =(a, Shoot) and FacingWumpus(s))) and
        (Alive(Result(a, s)) or
          not (Alive(s) and 
               not (Ready(s) and =(a, Shoot) and FacingWumpus(s))))

        This needs to be split, and we will ignore the 2nd part, as it
        will not be used in the proof. So:
     1.1'  not Alive(Result(a, s)) or Alive(s)
     1.2'  not Alive(Result(a, s)) or  not Ready(s)
               or not =(a, Shoot) or not FacingWumpus(s)

     Actually, we will only be using 1.2'

     2'. not FacingWumpus(s) or FacingWumpus(Result(a,s)) 

     3'. not HasArrow(s) or =(a, Shoot) or  HasArrow(Result(a,s)

     4. Axiom for Ready
        not Ready(Result(a, s)) or
                         ((Ready(s) and not =(a, Shoot)) or
                          (HasArrow(s) and =(a, Draw)))
        and (Ready(Result(a, s)) or
                       not  ((Ready(s) and not =(a, Shoot)) or
                          (HasArrow(s) and =(a, Draw)))

        This needs to be split:
     4.1 not Ready(Result(a, s)) or
                         ((Ready(s) and not =(a, Shoot)) or
                          (HasArrow(s) and =(a, Draw)))

        We will innore 4.1 (needs additional simplification), as it
           will not be used in the proof.
     4.2 (Ready(Result(a, s)) or
                       not  ((Ready(s) and not =(a, Shoot)) or
                          (HasArrow(s) and =(a, Draw)))
        Need to apply additional de-Morgans to get:

     4.2'   Ready(Result(a, s)) or  not Ready( s) or  =(a, Shoot)
     4.2''  Ready(Result(a, s)) or  not HasArrow(s) or not =(a, Draw)


      C) Use a refutation proof with resolution to show the Wumpus'
      death.

ANS:
Res. G', 1.2 with {a|Shoot, s|Result(Wait,Result(Draw,S0))} to get:

    10.  not Ready(Result(Wait,Result(Draw,S0)))
               or not =(Shoot, Shoot)
               or not FacingWumpus(Result(Wait,Result(Draw,S0)))
Res. 10, 5' with {x|Shoot} to get:
     11. not Ready(Result(Wait,Result(Draw,S0)))
           or not FacingWumpus(Result(Wait,Result(Draw,S0)))

Res. 11, 2' with {s|Result(Draw,S0)} to get:
     12. not FacingWumpus(Result(Draw,S0)) or 
             not Ready(Result(Wait,Result(Draw,S0)))

Res. 12, 2' (yes, again!) with {s|S0} to get:
     13. not FacingWumpus(S0) or
             not Ready(Result(Wait,Result(Draw,S0)))

Res 13, 8, empty substitution, to get:
     14. not Ready(Result(Wait,Result(Draw,S0)))

Res. 14, 4.2', with {a|Wait, s| Result(Draw,S0)) to get:
     15. not Ready(Result(Draw,S0)) or =(Wait, Shoot)  

Res. 15, 5, empty substitution to get:
     16. not Ready(Result(Draw,S0))

Res. 16, 4.2'' with {a|Draw, s|S0} to get:
     17. not HasArrow(S0) or not =(Draw, Draw)

Res. 17, 5' empty substitution to get:
     18.  not HasArrow(S0)

Finally resolve 18 with 9 to get the empty clause, which completes
the proof.


   c) What would be a potential problem in the proof if we did not
      have "frame axioms" in our representation (i.e. stating what
      did not change)?

ANS:
      We would not be able to conclude, e.g. that: 
         Ready(Result(Wait,Result(Draw,S0))) which is needed in the proof.

   d) Would we be able to do the proof using only forward chaining?

ANS:
  Note that 4.2' is not Horn (it has 2 positive literals),
  and we would not be able to use it! Thus, the answer is NOT AS IS.

  (Oddly enough, if we used explicit frame axioms we would not need
  this additioanl clause and then we could complete the proof using
  only forward chaining. But this part is an answer to a different question).
      

3) (Propositional logic)
   For each of the following sentences, determine whether they are
   satisfiable, unsatisfiable, and/or valid. For each sentence that
   is satisfiable, determine the number of models (over the propositional
   variables in the sentence).
   a) A and (A -> B) and not B
ANS: not satisfiable

   b) A -> not A
ANS: satisfiable, 1 model (A false)

   c) A or B or C or D
ANS: satisfiable, 15 models

   d) (A or B) and (C or D)
ANS: satisfiable, 9 models 
(3 for each "independent" subformula, thus
we can multiply)

   e) ((A -> B) and (B -> C)) -> (A -> C)
ANS: valid

4) (Game trees and search)
   Consider the stochastic game to be implemented in assignment 2:
   grid based environment, agents can move up, down, left, or right, or shoot,
   but where walking deliberately into a wall or waiting
   is not possible.
   You may assume a time limit as desired for the length of the game in
   each scenario.

   a) Show a scenario (with no bullets) where for the first agent to
      move (Clarification: not "whoever is the first to move", i.e. this need be
      shown only for one of the agents) under zero-sum scoring, 
      moving in a certain direction (say, left) loses,
      but under total flags collected scoring (i.e. each player
      scores its own flags, no penalty for flags collected by an opponent), the optimal action is to
      move left.

ANS:
Assume a short game (only 3 ply for each player),
and the scenario, with A to move (numbers are flag values):

3A6
.B.
.52

Note that if A moves left (collecting 3) B moves up to block A from
collecting 6, as otherwise A would collect 9 and win (since B can only
collect 7). A would win if it collected 6 immediately, and then
dependening on B's move (D to be optimal) would still collect 3 to
win.

But if each player collected its own score, since B cab never get more
than 7, it would go for 5 first, so A moving left would be optimal
for a score of 9 (but moving R would also be optimal).


   b) In the game with bullets and zero-sum scoring, show a scenario
   where whoever is the first agent to move, loses.

ANS:
Assume exactly 1 bullet each,
and the following initial position:

A.......9
.B#######

Either A or B can move (and get shot and lose)
or shoot immediately, after which the other player can safely move to
the flag and win.

   In both cases, you must PROVE the scores by generating the respective game tree, either
   to a terminal position or prove that you can prune some branches.

   c) Suggest heuristic evaluation functions for the total-flags scoring version of the game without bullets:
     1) One that is a lower bound, but non-trivial.

ANS:
Total flags collected by the player until now.

Anything beyond that is not easy, e.g. can add to the above:
value of highest-valued flag that is closer to this agent than to
the other agent.


     2) One that is an optimistic upper bound, but non-trivial

ANS:
Total flags collected by the player until now plus total flags not
yet collected by anybody,

Anything beyond that is not easy, e.g. can use: total flags already
collected plus value of all flags within reach withing the number
of turns remaining in the game (either true distance, or
Manhattan distance).

5)  (Game-tree search - alpha-beta pruning)
   a) Consider the tic-tac-toe position (with O to move):

 X |   |  
-----------------
 O |   | 
-----------------
 X |   |

     Give an example in ordering the complete search tree starting from this position 
     where alpha-beta pruning saves as little as possible, and another where the savings
     is maximal. How many nodes are pruned in each case?
     You may denote moves by Xxy or Oxy in order to save space.
     (Clarification: in the case with no pruning, no need to specify
     the tree explicitly, only estimate the number of nodes).


ANS: assuming y axis 1 is at the bottom...

Tree with best pruning is (note also initial bounds plus-minus 1 on
alpha and beta!), value of each node in parenthesis, with "-"
indicating -1 and "+" indicating +1.

MAX     MIN     MAX     MIN     MAX 

(0) O22 (0) X32 (0) O21 (0) X23 (0)  O33 (0) X31 score: 0 (alpha=0)
                        (+) X33 (+)  O23         score: 1 (alpha=1)
                                    (O31 pruned)
                        (+) X31 (+)  O23         score: 1 (alpha=1)
                                    (O22 pruned)
                (0) O31 (0) X33 (0)  O23 (0) X21 score: 0 (setting beta to 0)
                                (-)  O21 (-) X23 score: -1
                           (X23, X21 pruned)
                (0) O23 (symmetric to O21)
                (0) O33 (symmetric to O31)

        (+) X33 (+) O32               score: 1 (settting alpha to 1)
           (O21, O23, O23 and children - pruned)
        (+) X23 (+) O32               score: 1 (settting alpha to 1)
           (O21, O23, O23 and children - pruned)
        (+) X21 (symmetric to X23)
        (+) X31 (symmetric to X33)

(-) O23 (-) X22 (-) O21 (-) X33           score: -1 (setting beta to -1)
                           (X anything pruned now)
                (-) O31 (-) X33           score: -1
                           (X anything pruned now)
                (-) O23 (symmetric to O21)
                (-) O33 (symmetric to O31)
            (X anything pruned now since X can win)

etc. (similar to main branch starting with O23)

Final result: O can draw by playing O22 initially, otherwise
can be forced to lose.
With bad ordering, no pruning, tree has a bit less than 6! leaves. 

 
   b) Consider the same scenario as above, except that after every move by
      X, a random mark (equally probable to be X or O, uniformly distributed
      over the free locations) is generated. Draw and evaluate the
      search tree, and state where pruning is possible.


      (Since the above is too large, you may start from the following
       position for b, with O to move, instead).

 X | X | O
-----------------
 O |   | 
-----------------
 X |   | 


ANS:

MAX      MIN     CHANCE

(0) O32 ( 0) X21   (+)  O31     score: 1
                   (+)  O22     score: 1
                   (-)  X31     score: -1
                   (-)  X22     score: -1
       (>=0) X22   (+)  O31  score: 2
                   (+)  O21  (0)  O22  score: 1
                       (X21, X31 pruned)
       (>=0) X31   (+)  O22      score: 1
                   (+)  O21  (+)  O22  score: 1
                       (X21, X22  pruned)

(0) O22  (0) X32   (0)  O21  (0)  O31  score: 0
                   (0)  O31  (0)  O21  score: 0
                   (0)  X21  (0)  O31  score: 0
                   (0)  X31  (0)  O21  score: 0
       (>=0) X31   (+)  O32      score: 1
                   (+)  O21  (+)  O32  score: 1
                     (X21, X32 pruned)
       (>=0) X21   (+)  O32     score: 1
                   (+)  O31  (+)  O32  score: 1
                     (X31, X32 pruned)

(0) O31  (0) X32   (0)  O21  (0)  O22  score: 0
                   (0)  O22  (0)  O21  score: 0
                   (0)  X21  (0)  O22  score: 0
                   (0)  X22  (0)  O21  score: 0
       (>=0) X21   (+)  O32     score: 1
                   (+)  O22  (+)  O32  score: 1
                     (X31, X32 pruned)
             X22   (+)  O32     score: 1
                   (+)  O21  (+)  O32  score: 1
                     (X21, X32 pruned)

(0) O21 (-.25) X31   (0)  O32 (0) X22   score: 0
                     (0)  O22 (0) X32   score: 0
                     (-)  X22    score: -1
                     (0)  X32 (0) O22   score: 0
            (X22, X32 pruned, since O will never play O22)

Result: game is a draw, as long as O does not play O21.
(strange, as in a regular game O32 would be a winning move for O)


6)  (agents and environment simulators)
   For each of the following domains, which type of agent is appropriate
   (table lookup, reflex, goal based, or utility based). Also, indicate the
   type of environment:
   a) An agent that detects faces in images.
ANS:
Can be reflex, goal based, utility based, rule based, but NOT
table lookup!

   b) An agent that plays go.
ANS:
Should probably be utility based. Reflex rule based MAY be possible,
but not realistically.

   c) An agent that can plays solitaire.
ANS:
Goal base, usually. State space too large for table lookup.

   d) An autonomous robot that can win the DARPA challenge (driving in
      a city).
ANS:
Utility based, and even then we don;t know how to do it well yet.
   e) An internet shopping agent (flight tickets domain).
ANS:
Utility based.

   f) An agent that plays tic-tac-toe (3X3).
ANS:
Can be done as a reflex agent, even with a lookup table.

Note: in logic problem done in class Wed. March 12, the conclusion actually cannot be proved, as we are missing Does(x, a, s) for some x, a, s. This was discovered at the beginning of the exam at the time, and time was added...