The goal of this homework assignment is to try out the two uninformed search strategies you coded up in the last assignment in the context of a video-game, and to implement an informed search strategy for the game.
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 Wednesday, September 19.
To create a
homework02 branch in your local repository, follow the
$ cd path/to/cse-40171-fa18-assignments # Go to assignments repository $ git remote add upstream https://gitlab.com/wscheirer/cse-40171-fa18-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
The 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
homework01 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
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.
Again using your code from
homework01 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
Now it's time to turn our attention to informed search. Implement A* graph search in the empty function
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
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
If you have any questions, comments, or concerns regarding the course, please
provide your feedback at the end of your
Please see the note below on an important revision to the homework submission process.
To submit your assignment, please commit your work to the
homework02 branch in your assignment's GitLab repository:
$ cd path/to/cse-40171-fa18-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
New 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-40171-fa18-assignments to your personal fork's master branch so that your code is not visible to other students. Additionally, assign this merge request to your TA and add wscheirer, agraese, and AndroidKitKat as approvers (so all class staff can track your submission). Your assigned TA is agraese if you have a last name starting with A through Ki, or AndroidKitKat if you have a last name starting with Kl through W.