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), 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) = 21
      cost(a) = 9
      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 21.
   But it is not an optimal explanation, because A = {a}
   also an explanation, with a weight of 9.

   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.

   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'.

   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.

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

2) (FOL and situation calculus)
   We need to represent and reason within the scenario defined by assignment 1.
   a) Write down the axioms for the behavior of the world using FOL and
      situation calculus. Assume only one agent, no sentry, and no shooting.
      Use the propositions:
        Wall(x,y)   ; Location x, y is a wall
        Ice(x,y)    ; Location x, y is ice
        Free(x,y)   ; Location x, y is neither a wall nor ice
     Also use the fluents (situation-dependent propositions)
        Loc(x,y,s)  ; Agent is at x,y in situation s
        Dir(d, s)   ; Agent last motion was d at s (one of: left, right, up, down, none,
                      where the latter can happen only after hittin a wall).
        Flag(x,y,s) ; There is a flag that has not been collected at x, y, in situation s.
        CollectReward(s)  ; Agent receives reward in situation s (only when stepping
                            into a location that contained a flag in a previous situation).
        +, -  (in order to compute adjacent locations).
     And the actions: left, right, up, down.

   b) Write down the additional facts representing the following scenario
      (with x starting at 0 on the left, and y starting at 0 on the bottom,
       F is a flag, i is ice, A is the agent, initially on a free square.):

c) Now, we need to find a sequence of actions that will result in collecting a reward, and prove a theorem that it will do so. Do the following steps: A) Convert the knowledge base to conjunctive normal form. B) Formally list what we need to prove, and state its negation. C) Use resolution to reach a contradiction, thus proving the theorem. d) 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)? e) 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 and (A -> B) and (B-> C)) -> C b) A and (not (A or B)) c) A or (not (B or C)) d) (A and B) or (C and D) e) A -> not A 4) (Game trees and search. Note, this is the same question as last year, but the domain is a bit different!) 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. b) In the game with bullets and zero-sum scoring, show a scenario where whoever is 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) Consider the tic-tac-toe position (with O to move): X | | O ----------------- 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). 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 | 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 plays billiards ion a real table. b) An agent that plays go. c) An agent that can play peg-and-hole solitaire. d) An autonomous robot that can win the DARPA challenge (driving in a city). e) An internet shopping agent (car rental domain). f) An agent that plays tic-tac-toe (3X3). Justify all answers shortly!

Deadline: Noon (12:00), Tuesday, January 6, 2009 ( strict deadline).

Submissions are to be solo.