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.