NAME: SID#: Login: Sec: 1CS 188 Introduction toFall 2006 Artificial Intelligence MidtermYou have 80 minutes. The exam is closed book, one page cheat sheet allowed, non-programmable basic calculatorsallowed. 80 points total. Pace yourself, and don’t panic!Mark your answers ON THE EXAM ITSELF. Write your name, SID, login, and section number at the top of eachpage.If you are not sure of your answer you may wish to provide a brief explanation. All short answers can be successfullyanswered in a few sentences at most.For staff use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Total/17 /10 /15 /12 /16 /10 /801. (17 points.) Short AnswerAnswers should fit in a single sentence.(a) (3 pts): Give a set of broad conditions under which A∗search reduces to BFS.(b) (3 pts): When would DFS be a better choice than A∗search? Describe a broad qualitative conditionrather than a specific example.2(c) (3 pts): Why is temporal difference learning of q-values (Q-learning) superior to temporal differencelearning of values?(d) (3 pts): Write a Bellman update for q-value iteration, which is like value iteration except q-values ratherthan values are learned from previous q-value estimates, using a one-step lookahead (i.e. you shouldexpress Qi+1estimates in terms of Qiestimates).(e) (5 pts): In a Markov game, or adversarial MDP, two players, max and min alternate actions in an MDP.Assume the game is zero-sum, so that when a transition (s, a, s0) occurs, max receives R(s, a, s0), whilemin receives −R(s, a, s0), regardless of who initiated the transition. Assume that both players have thesame set of actions available in any state and that both players use the same discount per time step. LetVM AX(s) and VM IN(s) be the expected future discounted rewards for each player. Write two Bellmanequations, expressing each of VM AXand VM INin terms of adjacent lookahead values of VM AXand / orVM IN.NAME: SID#: Login: Sec: 32. (10 points.) Search and HeuristicsConsider the following variant of Mazeworld, shown below, where a single planning agent must move fourrobots from a configuration on one side of the grid to a goal configuration on the other side, shown below.In any given time step, each robot can move one square North, South, East, West, or stay where it is. Afterthe moves occur, no two robots can occupy the same result square. However, two adjacent robots can swappositions in a single time step. A possible succ es sor of the start state is shown below in which B moved North,D moved West, C moved North, and A stood still.############### ## # ## ##### ## # # ## ## ##### ####BD# # ##AC# ### ############################## ## # ## ##### ## # # ##B## ##### ####DC# # ##A # ### ############################## ## # ## ##### ## # # ## ## ##### #### # # CD## # ### AB###############Start Successor Goal(1) (2 pts): What is the branching factor for this search problem. Give the tightest (smallest) upper boundyou can.(2) (2 pts): If the grid is n by n, what is the size of the state space? Give the tightest upper b ound you can.(3) (4 pts): Propose an efficient, simple admissible heuristic for use in A∗search. The number of computationsmade by your heuristic should not depend on the size of the grid. Trivial and nearly trivial answers (e.g. “1”unless at a goal state) will not receive credit.(4) (2 pts): Propose an admissible heuristic that takes advantage of the functionality of your Mazeworld code.Your heuristic should return the correct forward cost (i.e. be the perfect heuristic) in the c ase of a single robot,but need not be c onstant time.43. (15 points.) CSPsYou are in charge of scheduling for computer science classes that meet Mondays, Wednesdays and Fridays.There are 6 classes that meet on these days and 3 professors who will be teaching these classes. You areconstrained by the fact that each professor can only teach one class at a time.The classes are:• Class 1 - Intro to Programming: meets from 8:00-9:00am• Class 2 - Intro to Artificial Intelligence: meets from 8:30-9:30am• Class 3 - Natural Language Processing: meets from 9:00-10:00am• Class 4 - Computer Vision: meets from 9:00-10:00am• Class 5 - Machine Learning: meets from 10:30-11:30amThe professors are:• Professor A, who is available to teach Classes 1, 2, and 5.• Professor B, who is available to teach Classes 3, 4, and 5.• Professor C, who is available to teach Classes 1, 3, and 4.(1) (4 pts): Formulate this problem as a CSP problem in which there is one variable per class, stating thedomains, and constraints. Constraints should be sp e cified formally and precis ely, but may be implicit ratherthan explicit.(2) (2 pts): Draw the constraint graph associated with your CSP.NAME: SID#: Login: Sec: 5(4) (4 pts): Show the domains of the variables after running arc-consistency on this initial graph (after havingalready enforced any unary constraints).(5) (1 pt): Give one solution to this CSP.(6) (2 pts): Your CSP should look nearly tree-structured. Briefly explain (one sentence or less) why we mightprefer to solve tree-structures CSPs.(7) (2 pts): Name (or briefly describe) a standard technique for turning these kinds of nearly tree-structuredproblems into tree-structured ones.64. (12 points.) Minimax SearchConsider the following minimax tree.(1) (2 pts): What is the minimax value for the root?(2) (5 pts): Draw an X through any nodes which will not be visited by alpha-b eta pruning, assuming childrenare visited in left-to-right order.(3) (2 pts): Is there another ordering for the children of the root for which more pruning would result? If so,state the order.(4) (3 pts): Propose a general, practical method for ordering children of nodes which will tend to increasethe opportunities for pruning. You should be concise, but clearly state both what to do about min nodes andmax nodes.NAME: SID#: Login: Sec: 75. (16 points.) Multi-Agent Search(1) (4 pts): For the case where ghosts move randomly, state Pacman (with Project 1 rules) as an MDP. Eachcomponent should be answered in at most one sentence:States: Configurations of the board, as given in a GameState object, including food locations, agentpositions, etc.Actions: A subset of {north, south, east, west, stop}, varying by state.Transitions:Rewards:Discount:Answer the following questions precisely, but in around one sentence.%%%%%%%%%% G% .%%%%% %% %% %% %% %% %% % <.%%%%%%%%%%⇔%%%%%%%%%%G % .%%%%% %% %% %% %% %% %% % > .%%%%%%%%%%(2) (3 pts): Pacman thrashes, alternating between the two configurations
View Full Document
Unlocking...