Project 1.1: Search in Mazeworld

Due Friday, 9/8, at 11:59pm

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.

Introduction

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.

Welcome to Mazeworld

The relevant code is in mazeworld.py. A maze is represented as a 2-d grid with a start position '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.

Search Algorithms

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 search.py. To make your algorithm complete, write a graph search algorithm that avoids expanding any already visited states (textbook section 3.5). Test your code on the maze in maze1.txt as follows:

>>> 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 search.py. Again, write a graph search algorithm that avoids expanding any already visited states. Test your code on the maze in maze1.txt the same way you did for depth-first search (except of course instantiating your BFS function instead of your DFS function). Does BFS find the best solution? Now test BFS on maze2.txt. Does BFS find the best solution for this maze? If not, what is it doing wrong, or failing to do? Does BFS expand a substantially different number of nodes than DFS?

Question 3 (3 points) Implement the uniform-cost graph search algorithm in the uniformCostSearch function in search.py. Test your algorithm on maze2.txt. Does it find the best solution? Now test your algorithm on maze3.txt. How many nodes does it expand in order to get this solution? Looking at the output, does it seem like the UCS is expanding unnecessary nodes? Which nodes are wasted exploration?

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!