A lone adventurer, the brave SearchAgent, forges eastward through the mountains with nothing but a map and her algorithmic savvy. Only by a thorough search of her map will she reach her destination without wasting steps.

To prepare you for the more complicated domain of Pacman, this first checkpoint focuses on a classic domain in the artificial intelligence community: navigating mazes. The project will consist of building general search algorithms and applying them to mazes. If you are unfamiliar with Python, you might want to work through the Python tutorial before this project.

The code for this project consists of several Python files which you will need to understand in order to complete the assignment. You can download the code and supporting files as a zip archive.

mazeworld.py | Code for constructing, editing, displaying and searching mazes (Part A). |

search.py | Generic search code. A summary of the search API can be found here. |

util.py | Useful data structures for implementing search algorithms. |

**What to submit:** You will fill in portions of search.py during the assignment. You should submit this file along with *a text or pdf file containing answers to the discussion questions*. If you change other files, submit those as well. Directions for submitting and setting up your account are on the course website.

**Evaluation:** Your code will be autograded for technical correctness. Please *do not* change the names of any functions within the code, or you will wreak havoc on the autograder. Your short answers to discussion questions will also be graded, but need only concisely answer the questions. One sentence should suffice for each question. No in-depth analysis is required for this checkpoint.

**Academic Dishonesty:** We will be checking your code against other submissions in the class for logical redundancy. If you copy someone else's code and submit it with minor changes, we will know. Our cheat detector is quite hard to fool, so please don't try. We trust you all to submit your own work only; please don't let us down. Instead, contact the course staff if you are having trouble.

`'S'`

and exit `'E'`

. There are also obstacles `'#'`

that are impassable and water `'~'`

which is passable but expensive (5 times the step cost of moving through a blank square). You can specify a maze with a matrix or use mazeworld's `readMazeFromFile`

as follows:
```
>>> import mazeworld
```

>>> simpleMaze = mazeworld.readMazeFromFile('simplemaze.txt')

>>> print simpleMaze

------- |#######| |#S~ E#| |# #| |#######| -------

The simplest search function in this domain simply moves right until she finds the exit or hits an obstacle and gives up. This naive searcher, `brokenMazeSearch`

is provided in mazeworld.py. This agent can find a path through our simple maze.

```
>>> solver = mazeworld.brokenMazeSearch
```

>>> mazeworld.searchMaze(simpleMaze, solver)

Solution found. ------- |#######| |#SxxxE#| |# #| |#######| ------- x - cell used in solution o - cell expanded during search ------------------------------- Solution cost: 8.0 Number of nodes expanded: 4 Number of unique nodes expanded: 4

Note that `mazeworld.searchMaze`

takes `mazeworld.brokenMazeSearch`

as an argument. In Python, everything, even functions, are objects, and thus can be passed as arguments.

Next take a look at the `Maze`

class. Try these, for example:

```
>>> print 'rows:', simpleMaze.getNumRows()
```

rows: 4

```
>>> print 'cols:', simpleMaze.getNumCols()
```

cols: 7

```
>>> print 'start pos:', simpleMaze.getStartCell()
```

start pos: (1, 1)

```
>>> print 'exit pos:', simpleMaze.getExitCell()
```

exit pos: (1, 5)

```
>>> print 'pos 1,2 passable?', simpleMaze.isPassable(1,2)
```

pos 1,2 passable? True

Note that (0, 0) is the top left corner and the exit is at (1, 5) which you should read row 1, column 5. This (row, column) notation differs from the usual coordinate (x, y) notation but is standard for matrices.

Now that you understand the Maze object, we can turn our attention to searching. In the `search`

module, look at the abstract `searchProblem`

class. Any specific search problem must implement the functions here. We have provided such implementations in the `mazeworld`

module in a class called `MazeSearchProblem`

. Try these:

```
>>> problem = mazeworld.MazeSearchProblem(simpleMaze)
```

>>> startstate = problem.getStartState()

>>> print startstate

(1, 1)

```
>>> print problem.isGoalState(startstate)
```

False

```
>>> print problem.getSuccessors(startstate)
```

[((2, 1), 'S', 1), ((1, 2), 'E', 5)]

Note that in this particular case, a state is just a grid position (though in other search problems, the state could be much more complex). The `getSuccessors`

function returns a list of `(state, action, cost)`

triples. Look at the documentation in the function for more details.

Now that you've gotten your feet wet, it's time to write full-fledged generic search functions! Pseudocode for the search algorithms you'll write can be found in the lecture slides and textbook. Remember that a search node must contain the current state as well as the information necessary to reconstruct the path to that state. Each algorithm is very similar, so concentrate on getting DFS right and the rest should be relatively simple.

* Question 1 (2 points) * Implement the depth-first search (DFS) algorithm in the

`depthFirstSearch`

function in ```
>>> import search
```

>>> maze1 = mazeworld.readMazeFromFile('maze1.txt')

>>> solver = search.depthFirstSearch

>>> mazeworld.searchMaze(maze1, solver)

The solution found by your DFS algorithm should have a cost of 61 (provided you push successors onto the fringe in the order provided by getSuccessors). Is this the lowest cost solution? If not, what is depth-first search doing wrong?
* Question 2 (2 point) * Implement the breadth-first search (BFS) algorithm in the

`breadthFirstSearch`

function in * Question 3 (3 points) * Implement the uniform-cost graph search algorithm in
the

`uniformCostSearch`

function in Question 4 (3 points) Implement A* graph search in the empty function `aStarSearch`

in *search.py*. You will need to pass a heuristic function into `aStarSearch`

upon construction. The heuristic function should take two arguments: the current state and the search problem. Use the `manhattanDistance`

heuristic function provided in mazeworld.py. Now, test your A* function
on *maze3.txt*. How many nodes does
it expand compared to the uniform-cost search function you wrote for question 4? Qualitatively, what is different about the regions explored by UCS and A*?

Your agent is on a roll! Try maze_15x15.txt, maze_25x25.txt and maze_35x35.txt for more fun.

Congratulations, you've completed the first checkpoint. Pacman is waiting for you!