Homework 02: Application of Uninformed and Informed Search
The goal of this homework assignment is to implement two uninformed search strategies and one informed search strategy for a video game. If your search algorithms work correctly, then you'll be able to see your AI capabilities win the game (at varying levels of efficiency).
For this assignment, record your responses to the following activities in the
README.md file in the homework02 folder of your assignments GitLab
repository and push your work by 11:59 PM Monday, September 30.
Activity 0: Branching
As discussed in class, each homework assignment must be completed in its own git branch; this will allow you to separate the work of each assignment and for you to use the merge request workflow.
To create a homework02 branch in your local repository, follow the
instructions below:
$ cd path/to/cse-40171-fa19-assignments # Go to assignments repository $ git remote add upstream https://gitlab.com/wscheirer/cse-40171-fa19-assignments # Switch back over to the main class repository $ git fetch upstream # Toggle the upstream branch $ git pull upstream master # Pull the files for homework02 $ git checkout -b homework02 # Create homework02 branch and check it out $ cd homework02 # Go into homework02 folder
Once these commands have been successfully performed, you are now ready to add, commit, and push any work required for this assignment.
Activity 1: Implement and Test Depth-First Search (15 Points)
Write a python method for depth-first search that takes three parameters as input: a graph,
a starting vertex, and a target vertex (i.e., the vertex you are searching for). The method
should return a valid search path from the starting vertex to the target vertex. Hint: Fig. 3.16
in Russell and Norvig demonstrates the operation of the algorithm. Include an if __name__
== '__main__': block that calls your search method and is able to pass two command line
arguments to it: the starting vertex and the target vertex. Name your program
depth-first-search.py.
The following graph, which will be used as a test case, can be coded directly into the program:
If your program is working as expected, you should be able to call it, for example, in the
following manner: python depth-first-search.py A F, and receive the following
output for the search path: [['A', 'B', 'E', 'F']].
Activity 2: Implement and Test Breadth-First Search (15 Points)
Write a python method for breadth-first search that takes three parameters as input: a graph,
a starting vertex, and a target vertex (i.e., the vertex you are searching for). The method
should return a valid search path from the starting vertex to the target vertex. Hint: Fig. 3.11
in Russell and Norvig presents pseudocode for the algorithm. Include an if __name__
== '__main__': block that calls your search method and is able to pass two command line
arguments to it: the starting vertex and the target vertex. Name your program
breadth-first-search.py.
The graph above from Activity 1 can be coded directly into the program. If everything is working
with your breadth-first search program, you should get the same output as you did with depth-first
search: calling python breadth-first-search.py A F results in the following search path: [['A', 'B', 'E', 'F']].
Activity 3: Depth-first Search for a Maze Game (20 Points)
The next three activities in this assignment will make use of some code developed by John DeNero and Dan Klein for a Pacman-style game that can be used to evaluate different AI algorithms. After cloning this assignment's repository and changing to its directory homework02/search, you should be able to play a game of Pacman by typing the following at the command line:
$ python pacman.py
If the program does not execute properly, check your python version: the code was developed for Python 2.
The objective of this assignment is to test some search algorithms that can solve various maze problems supported by the Pacman code, like the one shown above. The code already implements a fully-functional Search agent in SearchAgents.py. However, the search algorithms are not implemented. It will be your job to fill in three of these algorithms.
First, verify that SearchAgent is working correctly by running the following:
$ python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch
Next, using your code from Activity 1 as a basis, implement the depth-first search algorithm in the depthFirstSearch function in search.py. Note that 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).
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 -l bigMaze -z .5 -p SearchAgent
Hint: class SearchProblem contains the following methods that will be helpful to you in your implementation:
getStartState(self): Returns the start state for the search problem.
isGoalState(self, state): Returns True if and only if the state is a valid goal state.
getSuccessors(self, state): For a given state, this should return a list of triples, (successor, action, stepCost).
getCostOfActions(self, actions): This method returns the total cost of a particular sequence of actions.
Activity 4: Breadth-first Search for the Maze (20 Points)
Using your code from Activity 2 as a basis, implement the breadth-first search algorithm in the breadthFirstSearch function in search.py. You can test your code the same way you did for depth-first search:
$ python pacman.py -l tinyMaze -p SearchAgent -a fn=bfs
$ python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs
$ python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5
Activity 5: A* Search for the Maze (30 Points)
Now it's time to turn our attention to informed 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). Use the Manhattan distance heuristic (implemented already as manhattanHeuristic in searchAgents.py) in your implementation. The test cases for this activity are:
$ python pacman.py -l tinyMaze -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
$ python pacman.py -l mediumMaze -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
$ python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic
Feedback
If you have any questions, comments, or concerns regarding the course, please
provide your feedback at the end of your README.md.
Submission
To submit your assignment, please commit your work to the homework02 folder
of your homework02 branch in your assignment's GitLab repository:
$ cd path/to/cse-40171-fa19-assignments # Go to assignments repository $ git checkout master # Make sure we are in master branch $ git pull --rebase # Make sure we are up-to-date with GitLab $ git checkout -b homework02 # Create homework02 branch and check it out $ cd homework02 # Go to homework02 directory ... $ $EDITOR README.md # Edit appropriate README.md $ git add README.md # Mark changes for commit $ git commit -m "homework02: complete" # Record changes ... $ git push -u origin homework02 # Push branch to GitLab
Procedure for submitting your work: create a merge request by the process that is described here, but make sure to change the target branch from wscheirer/cse-40567-sp19-assignments to your personal fork's master branch so that your code is not visible to other students. Additionally, assign this merge request to our TA (sabraha2) and add wscheirer as an approver (so all class staff can track your submission).