NAME: SID#: Login: Sec: 1CS 188 Introduction toSpring 2006 Artificial Intelligence MidtermYou have 80 minutes. The ex am is open-book, open-notes, no electronics. 100 points total. Don’t panic!Mark your answers ON THE EXAM ITSELF. Write your name, SID, login, and section number at the top of eachpage.For tr ue/false questions, CIRCLE True OR False.If you are not sure of your answer you may wish to provide a brief explanation. All short answer sections can besuccessfully answered in a few sentences at most.For official use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Total/20 /24 /16 /20 /20 /1001. (20 points.) True/FalseEach problem is worth 2 points. Incorrect answers are worth 0 points. Skipped questions are worth 1 point.(a) True/False: The action taken by a ra tional agent will always be a deterministic function of the agent’scurrent perce pts.(b) True/False: An optimal solution path for a se arch problem with positive costs will never have repeatedstates.(c) True/False: Depth-first graph search is always complete on problems with finite search graphs.(d) True/False: If two search heuristics h1(s) and h2(s) have the same averag e value, the heuristic h3(s) =max(h1(s), h2(s)) could give better A* efficiency tha n h1or h2.(e) True/False: For robots with only rotational joints, polygonal obstacles will have polygonal images inconfiguration spa ce.(f) True/False: There exist constraint satisfaction problems which can be expressed using trinary (3-variable)constraints, but not binary constraints.(g) True/False: Fo r all random varia bles W, X, Y and ZP (Y, Z|W, X)P (W, X)P (Y, Z)= P (W, X|Y, Z)(h) True/False: For any se t of attributes, and any training set generated by a deterministic function f ofthose attributes, there is a decision tree which is consistent with that training se t.(i) True/False: There is no hypothesis space which can be PAC learned with one exa mple.(j) True/False: Smoothing is needed in a Naive Bayes classifier to compute the maximum likelihood estimatesof P (feature | class).22. (24 points.) SearchConsider the following search problem:SGABCD5221525Node h0h1h2S 0 5 6A 0 3 5B 0 4 2C 0 2 5D 0 5 3G 0 0 0(a) (3 points) Which of the heuristics shown are admissible? Circle all that apply: h0, h1, h2.(b) (8 points) Give the path A* search will return using each of the three heuristics? (Hint: you should notactually have to execute A* to know the answer in some cases .)h0:h1:h2:(c) (3 points) What path will gre e dy best-first search return using h1?NAME: SID#: Login: Sec: 3Mazeworld: From the MazeWorld domain of Project 1, consider the following maze configuration:-----------------| || || S || ||~~~~~~~~~~~~ ||~~~~~~~~~~~~ ||~~~~~~~~~~~~ E |-----------------Recall that states are cells o f this maze. The agent starts at S and tries to reach the goal E. Valid actions aremoves into adjacent cells that are e ither clear (step c ost of 1) or marked as ~ (step cost of 5 ).Below ar e the outputs of the function mazeworld.t estAgentOnMaze, tested with several agents that imple-mented graph search algorithms. Overlaid on the original maz e , an x is placed on a cell that is used alongthe solution path, and an o denotes a cell tha t was expanded but not was not part of the solution path. Forthis problem, DFS and BFS explore successors acco rding to a fixed ordering o f moves: right, down, left, up.Greedy and A∗search use the Manhattan distance heuristic.A different s e arch strategy (BFS, DFS, UCS, Gre e dy, or A∗) was us e d to produce each of the outputs below.Specify which strategies were used (2 points ea ch):-----------------|ooooooooooooooo ||oooooooooooooooo ||ooooooSoooooooooo||ooooooxxxxxxxooo ||~~ooooooooo~xooo ||~~~~~~~~~~~~xo ||~~~~~~~~~~~~xE |-----------------Strategy:-----------------| || || S || x ||~~~~~~x~~~~~ ||~~~~~~x~~~~~ ||~~~~~~xxxxxxxE |-----------------Strategy:-----------------| || || Sxxxxxxx xxx|| x||~~~~~~~~~~~~ x||~~~~~~~~~~~~ x||~~~~~~~~~~~~ Exxx|-----------------Strategy:-----------------| || || Soooooo || xxxxxxxo ||~~~~~~~~~~~~xo ||~~~~~~~~~~~~xo ||~~~~~~~~~~~~xE |-----------------Strategy:-----------------|oooooooooooooooo ||ooooooooooooooooo ||ooooooSoooooooooo ||ooooooxooooooooo ||ooooooxoooooooo ||ooooooxooooooo ||ooooooxxxxxxxE |-----------------Strategy:43. (16 points.) CSPsTwo trains, the A-line and the B-line, use the simple rail network shown below. We must schedule a singledaily departure for each train. Each departure will be on an hour, between 1pm and 7pm, inclusive. The tr ainsrun at identical, constant speeds, and each segment takes a train one hour to cover.We can model this problem as a CSP in which the variables r e present the departur e times of the tr ains fromtheir sourc e stations:Variables: A, BDomains: {1, 2, 3, 4, 5, 6, 7}For example, if A = 1 and B = 1, then both trains leave at 1pm.The complication is that the trains cannot pass each other in the region of the track that they share, and willcollide if improperly s cheduled. The only points in the shared region where trains trains can pass or touchwithout a collision are the terminal sta tions (square s) and the intersection Y .Example 1: The A-line and B-line both depart at 4pm. At 6pm, the A-line will have reached Y , clearing theshared section of the track. The B train will have only reached Z. No collision will occur.Example 2: The A-line leaves at 4pm and the B-line at 2pm. At 5pm, the A-line will be at node X and theB-line at the intersection Y . They will then collide ar ound 5:30pm.Example 3: The A-line leaves at 4pm and the B-line at 3pm. At 5pm, the A train will be at node X a nd theB train at node Z. At 6pm they will pass each other safely a t the intersection Y with no collision.(a) (2 points) If the B-line leaves at 1 pm, list the times that the A-line can safely leave without caus ing acollision.(b) (6 points) Implicitly state the binary co nstraint between the variables A and B for this CSP. Yo ur statementshould b e precise, involving variables and inequalities, not a vague assertion that the trains should notcollide.NAME: SID#: Login: Sec: 5(c) (2 points) Imagine the A-line must leave be tween 4pm and 5pm, inclusive, and the B-line must leavebetween 1pm and 7pm, inclusive. State the varia bles’ domains after these unary constraints have beenimpo sed.A ∈ { }B ∈ { }(d) (6 points) Put an X through a ny domain value above tha t is removed by applying arc co ns istency to thesedomains.64. (20 points.) Probability and Naive BayesYou’ve been hired to
View Full Document
Unlocking...