PART 1

Problem 1: Consider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n + 1.

(a). Draw the portion of the state space for states 1 to 15.

(b). Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search.

Problem 2: (Provide derivations of your answer, that is, draw the search tree, and write down the list of visited nodes and the corresponding frontier nodes). Execute Tree Search through this graph (i.e. do not remember visited nodes). S is the start node, and G is the goal node. Step costs are given next to each arc. Heuristic function values are given in the table on the right. The successors of each node are indicated by the arrows out of that node. Use the alphabetical order as tie-breakers, i.e. if nodes A, B, and C are available to expand, expand A before B, B before C. For each search strategy below, show the order in which nodes are expanded, ending with the goal node that is found. Show the solution path from start to goal, and give the cost of the solution path that is found.

2.a depth-first search

Order of node expansion: ____________________________________________________________

Path found: _________________________________ Cost of path found: _____________________ 2.b uniform-cost search

Order of node expansion: ____________________________________________________________

Path found: _______________________________________ Cost of path found: _______________

2.c greedy (best-first) search with h(n)

Order of node expansion: ____________________________________________________________

Path found: ____________________________________ Cost of path found: __________________

2.d iterative deepening depth-first search

Order of node expansion: ____________________________________________________________

Path found: _________________________________ Cost of path found: _____________________ 2.e A* search with h(n)

Order of node expansion: ____________________________________________________________

Path found: __________________________________ Cost of path found: ____________________

Problem 3: (Provide derivations of your answer, that is, work on the search tree, write down the list of visited nodes and the corresponding frontier nodes). Consider the search tree below. The two goal states G1 and G2 are indeed the same goal. The numbers on the edges represent step-costs. You also know the following heuristic estimates: h(BG2) = 9, h(DG2) =10, h(AG1)=2, h(CG1)=1. In what order will A* search visit the nodes? Explain your answer by giving the value of the evaluation function f(n) for those nodes that the algorithm considers. Also give the solution path.

PART 2

Problem 1: Iterative Deepening

In the iterativeDeepeningSearch function in search.py, implement an iterative-deepening search algorithm

(iterative deepening depth-limited depth-first graph search). You will probably want to make use of the Node class in search.py. Figure 3.17 and Figure 3.18 from the textbook (also given at the end of this document) may help.

Experiments: Test your code using:

python pacman.py -l threeByOneMaze -p SearchAgent -a fn=ids python pacman.py -l testMaze -p SearchAgent -a fn=ids python pacman.py -l tinyMaze -p SearchAgent -a fn=ids python pacman.py -l smallMaze -p SearchAgent -a fn=ids python pacman.py -l mediumMaze -p SearchAgent -a fn=ids python pacman.py -l bigMaze -p SearchAgent -a fn=ids

A few additional notes:

x If Pacman moves too slowly for you, try the option frameTime 0.

x All of your search functions need to return a list of actions that will lead the agent from the start to the goal. These actions all have to be legal moves (valid directions, no moving through walls).

x We are implementing graph search, not tree search, so IDS might not return the optimal path.

Problem 2: A* Search

Implement A* graph search in the empty function aStarSearch in search.py. A* takes a heuristic function as an argument. Heuristics take two arguments: a state in the search problem (the main argument), and the problem itself (for reference information). The nullHeuristic heuristic function in search.py is a trivial example.

You will probably want to make use of the Node class in search.py and the PriorityQueue class in util.py.

You can test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic (implemented already as manhattanHeuristic in searchAgents.py).

Note: The following (from the textbook) may be helpful for you to implement the Iterative Deepening depthfirst search algorithm.