Question $1(3$ points$)$: Finding a Fixed Food Dot using Depth First Search

In

searchAgents.py$,$ you'll find a fully implemented SearchAgent, which plans out a path through Pacman's world and then executes that

path step$-$by$-$step. The search algorithms for formulating a plan are not implemented $--$ that's your job. As you work through the following

questions, you might find it useful to refer to the object glossary $($the second to last tab in the navigation bar above$).$

First, test that the SearchAgent is working correctly by running:

python

pacman.py $-$l tinyMaze $-$p SearchAgent $-$a fn$=$tinyMazeSearch

The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm, which is implemented in

search.py$.$ Pacman

should navigate the maze successfully.

Now it's time to write full$-$fledged generic search functions to help Pacman plan routes! Pseudocode for the search algorithms you'll write

can be found in the lecture slides. Remember that a search node must contain not only a state but also the information necessary to

reconstruct the path $($plan$)$ which gets to that state.

Important note: 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$).$

Important note: Make sure to use the Stack, Queue and PriorityQueue data structures provided to you in

util.py$!$ These data structure

implementations have particular properties which are required for compatibility with the autograder.

Hint: Each algorithm is very similar. Algorithms for DFS$,$ BFS$,$ UCS, and A$*$ differ only in the details of how the fringe is managed. So$,$

concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a

single generic search method which is configured with an algorithm$-$specific queuing strategy. $($Your implementation need not be of this

form to receive full credit$).$

Implement the depth$-$first search $($DFS$)$ algorithm in the depthFirstSearch function in

search.py$.$ To make your algorithm complete, write

the graph search version of DFS$,$ which avoids expanding any already visited states.

Your code should quickly find a solution for:

python

pacman.py $-$l tinyMaze $-$p SearchAgent

python

pacman.py $-$l mediumMaze $-$p SearchAgent

python

pacman.py $-1$ bigMaze $-$z $.5-$p SearchAgent

The Pacman board will show an overlay of the states explored, and the order in which they were explored $($brighter red means earlier

exploration$).$ Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to

the goal?

Hint: If you use a Stack as your data structure, the solution found by your DFS algorithm for mediumMaze should have a length of $130$

$($provided you push successors onto the fringe in the order provided by getSuccessors; you might get $246$ if you push them in the reverse

order$).$ Is this a least cost solution? If not, think about what depth$-$first search is doing wrong. searcnAgents.py $>\%$ searcnAgent $>$ getActionafter you fill in parts of search.py

###########################################################

class SearchAgent $($Agent$)$:

$"""$

This very general search agent finds a path using a supplied search

algorithm for a supplied search problem, then returns actions to follow that

path.

As a default, this agent runs DFS on a PositionSearchProblem to find

location $(1,1)$

Options for fn include:

depthFirstSearch or dfs

breadthFirstSearch or bfs

Note: You should NOT change any code in SearchAgent

$"""$

def $($self$,$ fn$=$'depthFirstSearch', prob$=$'PositionSearchProblem', heuristic$=$'nullHeuristic'$)$:Get the search function from the name and heuristic

if fn not in dir$($search$)$:

raise AttributeError, fn $+\text{'}$ is not a search function in

search.py$.\text{'}$

func $=$ getattr$($search$,$ fn$)$

if 'heuristic' not in func.func$\_$code.co$\_$varnames:

print$(\text{'}[$SearchAgent$]$ using function $\text{'}+$ fn$)$

self.searchFunction $=$ func

else:

if heuristic in globals$().$keys$()$:

heur $=$ globals$()[$heuristic$]$

elif heuristic in dir$($search$)$:

heur $=$ getattr$($search$,$ heuristic$)$

else:

raise AttributeError, heuristic $+\text{'}$ is not a function in

searchAgents.py or

search.py$.\text{'}$

print$(\text{'}[$SearchAgent$]$ using function $\%$s and heuristic $\%$s$\text{'}\%($fn$,$ heuristic$))$self$.$searchFunction $=$ lambda x: func$($x$,$ heuristic$=$heur$)$if prob not in globals$().$keys$()$ or not prob.endswith$(\text{'}$Problem$\text{'})$:

raise AttributeError, prob $+\text{'}$ is not a search problem type in

SearchAgents.py$.\text{'}$

self.searchType $=$ globals$()[$prob$]$

print$(\text{'}[$SearchAgent$]$ using problem type $\text{'}+$ prob$)$

def registerInitialState$($self$,$ state$)$:

$"""$

This is the first time that the agent sees the layout of the game

board. Here, we choose a path to the goal. In this phase, the agent

should compute the path to the goal and store it in a local variable.