Midterm 1: solutions (draft) Question 1: 1) False. There are 4 models with A false, and one model with A, B, C true. Total 5 models. 2) True. Genetic algorithms have a random element that allows them to escape from local optima. (Note: if you stated: FALSE, because they have a random element that allows them to escape from local MAXIMA (of the fitness function), this still earns credit). 3) True. Let h*(n) be the true value. We have h(n) <= h*(n) and h(goal) = h*(goal) = 0. So h(n)/2 <= h*(n), and is still addmissible. 4) False. Alpha-beta pruning only prunes branches that are provably redundant in minimax. Question 2: Part A: 1) Forall (x) Dragon(x) => Flies(x) 2) Forall (x) (Exists (y) Has(x,y) and Wing(y)) => Flies(x) Equivalently this can be written as: Forall (x,y) Has(x,y) and Wing(y) => Flies(x) 3) Foarll (x) Green(x) => Dragon(x) 4) Forall (x) Bird(x) => ((Exists (y,z) Has(x,y) and Has(x,z) and Wing(y) and Wing(z) and not =(y,z)) and (Forall (w,y,z) (Has(x,y) and Has(x,z) and Has(x,w) and Wing(y) and Wing(z) and Wing(w)) => (=(y,z) or =(w,z) or =(y,w)))) 5) (not Green(Tweety)) => Bird(Tweety) Part B: Conversion to CNF (variables are all the lower-case names with numerals) 1. not Dragon(x1) or Flies(x1) 2. not Has(x2,y2) or not Wing(y2) or Flies(x2) 3. not Green(x3) or Dragon(x3) Number 4 gets split into numerous clauses. Note that Wing1, Wing2, etc. are Skolem functions. 4a. not Bird(x4) or Has(x4, Wing1(x4)) 4b. not Bird(x4) or Has(x4, Wing2(x4)) 4c. not Bird(x4) or Wing(x4, Wing1(x4)) 4d. not Bird(x4) or Wing(x4, Wing2(x4)) 4e. not Bird(x4) or not =(Wing1(x4),Wing2(x4)) 4f. not Bird(x4) or not Has(x,y4) or not Has(x,w4) or not Has(x,z4) or not Wing(y4) or not Wing(w4) or not Wing(z4) or =(y4,z4) or =(y4,w4) or =(w4,z4) 5. Green(Tweety) or Bird(Tweety) Part C: Proving that Tweety, i.e. proving G: Flies(Tweety). Add negated version of G, that is: G': not Flies(Tweety) Resolve 1 with G', substitution {x1|Tweety), to get: 6. not Dragon(Tweety) Resolve 6 with 3, substitution {x3|Tweety}, to get: 7. not Green(Tweety) Resolve 7 with 5, empty substitution, to get: 8. Bird(Tweety) Resolve 8 with 4a, substitution {x4|Tweety}, to get: 9. Has(Tweety,Wing1(Tweety)) Resolve 8 with 4c, substitution {x4|Tweety}, to get: 10. Wing(Wing1(Tweety)) Resolve 9 with 2, substitution {x|Tweety,y2|Wing1(Tweety)}, to get: 11. not Wing(Wing1(Tweety)) or Flies(Tweety) Resolve 10 with 11, empty substitution, to get: 12. Flies(Tweety) Resolve 12 with G', empty substitution, to get the empty clause (contradiction). Part D: Proving using backward chaining. Cannot be done, as we need to prove that it is a dragon, for which we need to prove that it is green, and the only way to get green is using 5 which is not in Horn form and cannot be used. Alternately, we need to prove that it has a wing, which can only be done if it is a bird, which cannot be shown (only match uses 5, which is not Horn). Part E: Proving using forward cahining, with the added fact 0. Bird(Tweety) can be done, as follows: Using 0 fires rule 4a, to get 6. Has(Tweety,Wing1(Tweety)) Using 0 fires rule 4c to get 7. Wing(Wing1(Tweety)) Using 6 and 7 fire rule 2 to get 8. Flies(Tweety) Question 3: Part A: No, because e.g. in the provided initial state the Manhattan distance is 7, but the goal can be reached in 2 steps, for a cost of 2. This means that the heuristic is not optimistic, and thus not addmissible. Part B: Still no, using the above example, where the sequence of operators: SWITCH 8-1, LEFT has a cost of 5. (actually, I intended the answer here to be "yes", but what came out is the above. But if the exchange move had cost 8 or more, we could prove that the heutistic would be addmissible). Part C: Initialize agenda, with the initial state, with h=7 and f=7. Pop initial state, and since it is not a goal, generate its 5 successors: 823 456 71 h = 4, g=1, f=5 823 456 71 h = 8, g=1, f=9 823 4 6 751 h = 8, g=1, f=9 123 456 7 8 h = 1, g=1, f=2 827 456 3 1 h = 15, g=1, f=16 Now, A* pops the fourth state above, since it has lowest f value. Since that state is not a goal state, it generates 5 successors: 123 456 78 h = 0, g=2, f=2 123 456 78 h = 2, g=2, f=4 123 4 6 758 h = 2, g=2, f=4 823 456 7 1 h = 7, g=2, f=9 127 456 3 8 h = 9, g=2, f=11 Now A* pops the first of the above 5 states, since it has the lowest overall f cost. This is a goal state, so it (and thus the path to this node) is returned.