CS 188 Introduction toSpring 2009 Artificial Intelligence Midterm ExamINSTRUCTIONS• You have 3 hours.• The exam is closed book, closed notes except a one-page crib sheet.• Please use non-programmable calculators only.• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide abrief explanation. All short answer sections can be successfully answered in a few sentences at most.Last NameFirst NameSIDLoginGSISection TimeAll the work on thisexam is my own.(please sign)For staff use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Total/16 /15 /20 /10 /21 /18 /10021. (16 points) True/FalseFor the following questions, a correct answer is worth 2 points, no answer is worth 1 point, and an incorrectanswer is worth 0 points. Circle true or false to indicate your answer.a) (true or false) If g(s) and h(s) are two admissible A∗heuristics, then their average f (s) =12g(s) +12h(s)must also be admissible.b) (true or false) For a search problem, the path returned by uniform cost search may change if we add apositive constant C to every step cost.c) (true or false) The running-time of an efficient solver for tree-structured constraint satisfaction problems islinear in the number of variables.d) (true or false) If h1(s) is a consistent heuristic and h2(s) is an admissible heuristic, then min(h1(s), h2(s))must be consistent.e) (true or false) The amount of memory required to run minimax with alpha-beta pruning is O(bd) forbranching factor b and depth limit d.f) (true or false) In a Markov decision process with discount γ = 1, the difference in values for two adjacentstates is bounded by the reward between them: |V (s) − V (s0)| ≤ maxaR(s, a, s0).g) (true or false) Value iteration and policy iteration must always converge to the same policy.h) (true or false) In a Bayes’ net, if A ⊥⊥ B, then A ⊥⊥ B | C for some variable C other than A or B.NAME: 32. (15 points) Search: Crawler’s EscapeWhilst Pacman was Q-learning, Crawler snuck into mediumClassic and stole all the dots. Now, it’s trying toescape as quickly as possible. At each time step, Crawler can either move its shoulder or its elbow one positionup or down. Both joints s and e have five total positions each (1 through 5) and both begin in position 3.Upon changing arm positions from (s, e) to (s0, e0), Crawler’s body moves some distance r(s, e, s0, e0), where|r(s, e, s0, e0)| ≤ 2 mete rs (negative distance means the crawler moves backwards). Crawler must travel 10meters to reach the exit.A BCF! GA GC A GCA GCA GCX1!X2!Xn!E1!E2!En-1!…!P!CE!T!NADr(3, 3, 3, 4) 10 meters exit EA!Action: increase elbow position In this problem, you will design a search problem for which the optimal solution will allow Crawler to escapein as few time steps as possible.(a) (3 pt) Define a state space, start state and goal test to represent this problem.(b) (3 pt) Define the successor function for the start state by listing its (succes sor state, action, step cost)triples. Use the actions s+and s−for increasing and decreasing the shoulder position and e+and e−forthe elbow.4(c) (2 pt) Would depth-first graph search be complete for the search problem you defined? Explain.(d) (3 pt) Design a non-trivial, admissible heuristic for this problem.(e) (4 pt) Crawler’s shoulder overheats if it switches direction more than once in any three consecutive timesteps, making progress impossible. Describe how you would change your search problem so that an optimalsearch algorithm would only return solutions that avoid overheating.NAME: 53. (20 points) CSPs: Constraining Graph StructureHired as a consultant, you built a Bayes’ net model of Cheeseboard Pizz a customers. Last night, a corporatespy from Zachary’s Pizza deleted the directions from all your arcs. You still have the undirected graph of yourmodel and a list of dependencies. You now have to recover the direction of the arrows to build a graph thatallows for these dependencies. Note: X 6⊥⊥ Y means X is not independent of Y .A BCF! GA GC A GCA GCA GCX1!X2!Xn!E1!E2!En-1!…!P!CE!T!NADr(s0, e0, s0, e0+1) 10 meters exit EA!Distribution properties (dependencies):A 6⊥⊥ GB 6⊥⊥ FB 6⊥⊥ G | Ca) (1 pt) Given the first constraint only, circle all the topologies that are allowed for the triple (A, C, G).A BCF! GA GC A GCA GCA GCX1!X2!Xn!E1!E2!En-1!…!P!CE!T!NADr(s0, e0, s0, e0+1) 10 meters exit EA!b) (3 pt) Formulate direction-recovery for this graph as a CSP with explicit binary constraints only. Thevariables and values are provided for you. The variable EAstands for the direction of the arc between Aand the center C, where out means the arrow points outward (toward A), and in means the arrow pointsinward (toward C).Variables: EA, EB, EF, EGValues: out, inConstraints:c) (1 pt) Draw the constraint graph for this CSP.d) (2 pt) After selecting EA= in, cross out all values eliminated from EB, EFand EGby forward checking.EAEBEFEGin out in out in out ine) (2 pt) Cross out all values eliminated by arc consistency applied before any backtracking search.EAEBEFEGout in out in out in out inf) (1 pt) Solve this CSP, then add the correct directions to the arcs of the graph at the top of the page.6Now c onsider a chain structured graph over variables X1, . . . , Xn. Edges E1, . . . , En−1connect adjacentvariables, but their directions are again unknown.A BCD E!A E!C A E!CA E!CA E!CX1!X2!Xn!E1!E2!En-1!…!g) (4 pt) Using only binary constraints and tw o-valued variables, formulate a CSP that is satisfied by onlyand all networks that can represent a distribution where X16⊥⊥ Xn. Describe what your variables mean interms of direction of the arrows in the network.Variables:Constraints:h) (6 pt) Using only unary, binary and ternary (3 variable) constraints and two-valued variables, formulate aCSP that is satisfied by only and all networks that enforce X1⊥⊥ Xn. Describe what your variables meanin terms of direction of the arrows in the network. Hint: You will have to introduce additional variables.Variables:Constraints:NAME: 74. (10 points) Multi-agent Search: Connect-3In the game of Connect-3, players X and O alternate moves, dropping their symbols into columns 1, 2, 3, or 4.Three-in-a-row wins the game, horizontally, vertically or diagonally. X plays first. XOX XXOO XO4321 XOX XXOO XO4321 XOX XXOO XO4321 XOX XXOO XO4321 XOX XXOO XO4321(a) (1 pt) What is the maximum branching factor of minimax search for Connect-3?(b) (1 pt) What is the maximum tree
View Full Document
Unlocking...