15381/681 Homework 1
Part I: Programming [75 points]
Visit the Search in Pacman page and
download the zip archive.
Do all 8 search problems.
Use the command "python autograder.py" to check your solutions
for validity as you solve each problem. Multiply the autograder
score by 3 to get the number of points you will receive for each
problem.
Notes and Clarifications:
 You will need to have Python 2.7 and tkinter installed on
your machine.
 This assignment involves three kinds of things: problems,
search agents, and search functions.
 Problems are instances of
the SearchProblem class. They define methods for
obtaining a start state, testing for goal states, and getting
successors of states. Several of the exercises below are built
on PositionSearchProblem, which defines the maze search
domain. Problems may be further specified by layouts,
e.g., PositionSearchProblem uses a layout to define the
particular maze being searched.
 Agents are instances of the SearchAgent
class. An agent solves a problem using a search
function and possibly a heuristic, and then supplies the actions
in the solution to a caller that may choose to animate the
solution. Agents come with a default problem, a default search
function, and a default heuristic, but these can be changed by
supplying arguments to the agent.
 Search functions such as BFS, DFS, AStar, etc.,
explore a state space defined by a problem, beginning with the
start state, until they find a goal state. They may use
a heuristic, supplied by the agent, to guide their
exploration.
The file pacman.py implements machinery for running a search agent,
obtaining a solution path, and then animating that solution. You
can use the p (pacman) parameter to tell it what agent
to run; the default agent implements a conventional Pacman game
you can play with keyboard inputs. If you specify an agent using
p , you can also specify a layout
with l , and you can provide arguments to
the agent (via a ) to change the problem, the
search function, or the heuristic.
 Although the textbook's version of graph search checks new
nodes against both the set of visited states and the frontier,
this exercise only expects you to check against visited states.
Do not check the frontier.
 Note that when designing a new problem with your own
state data structures, they must be tuples, not lists, because
lists are not hashable in Python.
Part II: Written Problems [25 points]
 Six node search trees. (6 points) Below is a six node search
tree with one goal node. DFS and BFS take the same amount
of time to find the goal.
 Draw a six node search tree where DFS finds the goal
in the minimum number of steps (so some nodes will be
unvisited), but BFS must visit every node.
 Draw a six node search tree where BFS finds the goal
in the minimum number of steps (so some nodes will be
unvisited), but DFS must visit every node.
 Draw a six node search tree with positive integer
costlabeled arcs where UCS finds the goal in the
minimum number of steps (so some nodes will be
unvisited), but both DFS and BFS must visit every
node.
 Uniform cost search. (4 points) Give an example of
an acyclic directed graph (possibly with negative edge costs)
on which uniformcost search does not find the optimal path.
Your graph should have no more than six nodes. Clearly label
the start and goal nodes. Find the cost of the optimal path,
and explain the path that uniformcost search generates.
 A^{*} tree search. (5 points) Give an
example of an acyclic directed graph and a heuristic
function (not necessarily admissible) with which running
A^{*} tree search does not find an optimal path.
All the edge costs should be positive. Your graph should
have no more than six nodes. Clearly label the start and
goal nodes of the graph. For the remaining nodes, write in
the heuristic value for that node. Find the cost of the
optimal path and the cost of the path that A^{*}
tree search finds.
 A^{*} graph search. (6 points) Give an
example of an acyclic directed graph and
an admissible heuristic function (not necessarily
consistent) with which running A^{*} graph search
does not find an optimal path. All the edge costs should be
positive. Your graph should have no more than eight nodes.
Clearly label the start and goal nodes of the graph. For
the remaining nodes, write in the heuristic value for that
node. Find the cost of the optimal path and the cost of the
path that A^{*} graph search finds. Note that while
UCS tests whether a node is a goal state when popping it off
the priority queue, A^{*} does this test at the time
the node is generated because it must calculate h(s), which
is 0 for goal nodes if the heuristic is admissible.
 Pacman question 8. (4 points) Come up with a small, simple
example where repeatedly going to the closest dot does not
result in finding the shortest path for eating all the
dots.
Collect your answers in a file called answers.pdf.
Handin Instructions
Create a zip archive containing exactly these three files: search.py, searchAgents.py, and answers.pdf.
Note: do not use other archive formats such as tar, rar, or bz2; you must submit a zip file.
Submit your zip file via Autolab.
