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