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.
'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
>>> 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
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()
>>> print 'cols:', simpleMaze.getNumCols()
>>> 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
>>> print problem.isGoalState(startstate)
>>> 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 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
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?
>>> maze1 = mazeworld.readMazeFromFile('maze1.txt')
>>> solver = search.depthFirstSearch
>>> mazeworld.searchMaze(maze1, solver)
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
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!