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.

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-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

Once these commands have been successfully performed, you are now ready to add, commit, and push any work required for this assignment.

Activity 1: Depth-first Search for a Maze Game (25 Points)

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

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 2: Breadth-first Search for the Maze (25 Points)

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

Activity 3: A* Search for the Maze (50 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

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 folder of your 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.