Introduction to Artificial Inteligence

Assignment 3


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). Also part of the input is  a set of literals E  (the observed
   evidence) to be explained.    An explanation is a subset S of KB that 
   proves E. Formally, for each literal L in E and or in any rule in S, 
   there is a rule R in S where L is the consequent of R. 

   In this exercise, we wish to solve the weighted abduction version:
   each rule R has a weight w(R), and we need to find an explanation S where
   the sum of the costs of the rules in S is minimal. For example, consider
   the following KB (with costs in parenthesis):

   R1:        a -> b    (1)
   R2:          -> a   (10)
   R3:  b and c -> d    (1)
   R4:        a -> c    (1)
   R5:        x -> d    (2)
   R6:          -> b    (7)
   R7:          -> c    (6)
   R8:          -> d   (20)

   For the case where we wish to find an explanation for E = {d},
   one possible explanation is S = {R8} (with a weight of 20)
   but it is not an optimal explanation, because S = {R3, R6, R7} is
   also an explanation, with a weight of w(R3)+w(R6)+w(R7) = 15.

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

   b) Same as in (a), but allowed rules are only such that have a 
      consequent that already appear in E or in S' (but not in the
      consequent of a rule in S' - no need to explain a literal more
      than once).

   c) Same as (b), but this time a lexicographical ordering of literals
      is given (say a, then b, etc.), and only rules that have
      a consequent that is first in lexicographic ordering (among
      unexplained literals) are allowed.

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

   e) We wish to use A* to perform weighted abduction. Find an
      admissible heuristic for versions a, b, c, (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, c - your choice
      (hint: which would result in the shortest trace?)

   f) A student in the AI course suggested the following heuristic,
      called "total weight", computed as follows.

      For each literal L, initial its "total weight" T(L) to be infinite.
      If there is any rule R that has L as a consequent, and such
      that w(R) plus the sum of total weights off all its antecedents is
      less than T(L), update T(L). Keep doing so until no further
      updates are possible.

      Now, for a partial solution S', let h(S') be the sume of
      total weights for all unexplained literals in S' and E.

      For example, starting with infinite T(.) for all literals,
      we can set T(a) = 10 due to rule R2, and 
      T(b) = T(a) + 1 due to rule R1. Now, we can set T(b) = 7 due to
      rule R6, etc. Now, suppose we have E = {b} and S' is empty.
      Since there is one  unexplained literals (namely b) in E and
      S', we have h(S') = T(b) = 7.

      Is this heuristic admissible? If yes, provide a proof outline.
      If not, provide a counterexample.  


2) (FOL and situation calculus)
   We need to represent and reason within the following scenario, called
   the BGU shooting problem (based on the infamous Yale Shooting problem):
   A student in the AI course is so upset with his instructor, Fred, that
   he decides to shoot him. He therefore intends to wait outside the
   classroom with a loaded gun, and shoot Fred when he arrives.

   a) We need to represent the following facts using FOL and situation
      calculus, using successor-state axioms:

      A) The action of loading a gun makes it loaded. (Action name: Load)
      B) The action of waiting makes Fred arrive at the intended
         assasination site. (Action name: Wait)
      C) If Fred is at the intended assasination site and the gun
         is loaded, the action of shooting kills Fred.
         Shoot also makes the gun unloaded. (Action name: Shoot)
      D) In situation S0, Fred is alive, the gun is not loaded, and
         Fred is not at the assasination site.

      Use the following predicates to represent the above information:
         Loaded(s)    :  the gun is loaded in situation s
         Dead(s)      :  Fred is dead in situation s
         Loc(s)       :  Fred is at the assasination site in situation s
      Obviously, you also need to use the Result(a, s) function...

   b) Now, we need to prove that the following sequence of actions (starting
      from situation S0): Load, Wait, Shoot - results in Fred's death. 
      Proceed as follows:
      A) Represent the fact to be proved, and its negation.
      B) Convert all the knowledge you represented in A into CNF
      C) Use a refutation proof with resolution to show Fred's death.

   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)?

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

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 -> B) and (not B or C)) -> (not A or C)
   b) A -> not A
   c) X or Y or Z
   d) X and Y and Z
   e) (A -> B) and (C -> D) and (E -> F) 

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,
      under zero-sum scoring, moving in a certain direction (say, left) loses,
      but under total flags collected scoring, the optimal action is to
      move left.

   b) In the game with bullets, show a scenario where the the first agent to move loses.

   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.
     2) One that is an optimistic upper bound, but non-trivial

5)  (Game-tree search - alpha-beta pruning)
   a) Give an example of a 4-ply game tree (branching factor 2)
     where alpha-beta pruning saves NOTHING, and another where the savings
     is maximal. How many nodes are pruned in each case?
   b) Provide an example of a 2-ply + 1 chance node level game tree where
      alpha-beta saves search, and a similar example where changing the
      leaf values monotonically results in no savings for pruning. 


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 solves the 8 puzzle.
   b) An agent that plays checkers.
   c) An agent that can pass the Turing test.
   d) An autonomous robot for exploring Mars.
   e) An internet shopping agent (flight tickets domain).


Justify all answers shortly!

Deadline: Noon (12:00), Wednesday, December 6, 2006 ( strict deadline).

Submissions are to be solo.