15-381/681 Homework 1

Part I: Programming [75 points]

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.
  1. 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.

  2. 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.

  3. 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]

1. 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.

   
   

   1. 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.

   2. 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.

   3. Draw a six node search tree with positive integer cost-labeled 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.

2. Uniform cost search. (4 points) Give an example of an acyclic directed graph (possibly with negative edge costs) on which uniform-cost 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 uniform-cost search generates.

3. 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.

4. 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.

5. 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.

Hand-in Instructions

Submit your zip file via Autolab.