COMPSCI 188 Study Guide - Midterm Guide: Cheat Sheet, Reinforcement Learning, Edx
CS 188
Spring 2015 Introduction to
Artificial Intelligence Midterm 1
•You have approximately 2 hours and 50 minutes.
•The exam is closed book, closed calculator, and closed notes except your one-page crib sheet.
•Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide a
brief explanation. All short answer sections can be successfully answered in a few sentences AT MOST.
First name
Last name
SID
edX username
First and last name of student to your left
First and last name of student to your right
For staff use only:
Q1. Pacman’s Tour of San Francisco /12
Q2. Missing Heuristic Values /6
Q3. PAC-CORP Assignments /10
Q4. k-CSPs /5
Q5. One Wish Pacman /12
Q6. AlphaBetaExpinimax /9
Q7. Lotteries in Ghost Kingdom /11
Q8. Indecisive Pacman /13
Q9. Reinforcement Learning /8
Q10. Potpourri /14
Total /100
1
THIS PAGE IS INTENTIONALLY LEFT BLANK
Q1. [12 pts] Pacman’s Tour of San Francisco
Pacman is visiting San Francisco and decides to visit N different landmarks {L1, L2, . . . , LN}. Pacman starts at L1,
which can be considered visited, and it takes tij minutes to travel from Lito Lj.
(a) [2 pts] Pacman would like to find a route that visits all landmarks while minimizing the total travel time.
Formulating this as a search problem, what is the minimal state representation?
minimal state representation:
The minimal state representation is Pacman’s current location and which landmarks he has visited (boolean
indicators or a set or an unordered list) OR the inverse, which landmarks Pacman has not visited.
(b) [2 pts] Ghosts have invaded San Francisco! If Pacman travels from Lito Lj, he will encounter gij ghosts.
Pacman wants to find a route which minimizes total travel time without encountering more than Gmax ghosts
(while still visiting all landmarks). What is the minimal state representation?
minimal state representation:
The minimal state representation is the visited (or unvisited) landmarks (as above), Pacman’s current landmark
(as above), and the number of ghosts encountered thus far (or the inverse, the number of ghosts that can be
encountered in the future).
(c) [4 pts] The ghosts are gone, but now Pacman has brought all of his friends to take pictures of all the landmarks.
Pacman would like to find routes for him and each of his k−1 friends such that all landmarks are visited by
at least one individual, while minimizing the sum of the tour times of all individuals. You may assume that
Pacman and all his friends start at landmark L1and each travel independently at the same speed. Formulate
this as a search problem and fill in the following:
minimal state representation:
The state representation is the landmarks visited by at least one agent, stored as Nboolean indicators, a set,
or an unordered list (or the inverse – the unvisited landmarks) and the current location of each of the kagents.
actions between states:
An action can be a single agent moving from one landmark to another or a number of the agents moving from
their respective landmarks to new landmarks. The new landmarks need not be unvisited or unoccupied.
cost function c(s, s′) between neighboring states:
The cost function is the sum of the time traveled by each agent between state sand s′(or just a single term if
only one agent moves per action)
(d) [4 pts] Pacman would now like to find routes for him and each of his k−1 friends such that all landmarks
are still visited by at least one individual, but now minimizing the maximum tour time of any individual.
Formulate this as a search problem and fill in the following:
minimal state representation:
The state representation is the landmarks visited and the current location of each agent (both as above), as
well as the tour time for each agent.
actions between states:
An action is when a single agents moves from one landmark to another or some number of the agents move
from their current landmark to another landmark.
cost function c(s, s′) between neighboring states:
Let tmax be the maximum tour time of any individual at state sand t′
max be the equivalent at state s′. Then
the cost between sand s′is t′
max −tmax.
3
Document Summary
Midterm 1: you have approximately 2 hours and 50 minutes, the exam is closed book, closed calculator, and closed notes except your one-page crib sheet, mark your answers on the exam itself. If you are not sure of your answer you may wish to provide a brief explanation. All short answer sections can be successfully answered in a few sentences at most. First and last name of student to your left. First and last name of student to your right. Pacman is visiting san francisco and decides to visit n di erent landmarks {l1, l2, . Formulating this as a search problem, what is the minimal state representation? minimal state representation: If pacman travels from li to lj, he will encounter gij ghosts. Pacman wants to nd a route which minimizes total travel time without encountering more than gmax ghosts (while still visiting all landmarks). What is the minimal state representation? minimal state representation:
