Project 1: Search in Pacman Solution

Arti cial Intelligence




In this project, your Pacman agent will nd paths through his maze world, both to reach a particular location and to collect food e ciently. You will build general search algorithms and apply them to Pacman scenarios. As in Project 0, this project includes an autograder for you to grade your answers on your machine. This can be run with the command:

python autograder.py

The code for this project consists of several Python les, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore. Download search.zip from here http://ai.berkeley.edu/search.html which will contain all the code and supporting les.


    • Files to edit

For all the problems in this project, you would have to edit just two python    les namely:

    1. search.py: where all of your search algorithms will reside.

    2. searchAgents.py: where all of your search-based agents will reside.


    • Supporting  les

The following python les would help you in understanding the problem and the get you familiar with the di erent data structures and games states in Pacman.


    1. pacman.py: The main le that runs Pacman games. This le describes a Pacman GameState type, which you use in this project.

    2. game.py: The logic behind how the Pacman world works. This le describes several support-ing types like AgentState, Agent, Direction, and Grid.

    3. util.py: Useful data structures for implementing search algorithms.


    • Search in Pacman (120pts)

For all the problem titles described below, please refer to the link http://ai.berkeley.edu/ search.html for the problem description and what is expected of each problem. As always auto-grader has di erent test cases against which you can run your program to check the correctness. For the questions asked below, please ensure your response is brief and to the point. Please don’t write paragraphs of text as responses to these questions.




1

3.1    Depth First Search (12pts)

    1. (10pts) Code Implementation

    2. (1pt) Is the exploration order what you would have expected? Does Pacman actually go to all the explored squares on his way to the goal?

    3. (1pt) Is this a least cost solution? If not, think about what depth- rst search is doing wrong.


3.2    Breadth First Search (11pts)

    1. (10 pts) Code Implementation

    2. (1 pt) Does BFS  nd a least cost solution? If so explain why ?


3.3    Uniform Cost Search (11pts)

    1. (10pts) Code Implementation

    2. (1 pt) Specify the data structure used from the util.py for the uniform cost search


3.4    A* search (12pts)

    1. (10pts) Code Implementation

    2. (2 pts) What happens on openMaze for the various search strategies? Describe your answer in terms of the solution you get for A* and Uniform cost search.


3.5    Finding All the Corners (12pts)

    1. (10pts) Code Implementation

    2. (2 pts) Describe in few words/ lines the state representation you chose or how you solved the problem of nding all corners?


3.6    Corners Problem: Heuristic (11pts)

    1. (10pts) Code Implementation

    2. (1 pt) Describe the heuristic you had used for the implementation.


3.7    Eating All Dots (15pts)

    1. (13pts) Code Implementation

    2. (2 pt) Describe the heuristic you had used for the FoodSearchProblem.



2

3.8    Suboptimal Search (11pts)

    1. (10pts) Code Implementation

    2. (1 pt) Explain why the ClosestDotSearchAgent won’t always nd the shortest possible path through the maze.


    • Self Analysis (5pts)

        1. What was the hardest part of the assignment for you?

        2. What was the easiest part of the assignment for you?

        3. What problem(s) helped further your understanding of the course material?

        4. Did you feel any problems were tedious and not helpful to your understanding of the material?

        5. What other feedback do you have about this homework?


    • Evaluation

Your code will be auto-graded for technical correctness. Please do not change the names of any provided functions or classes within the code, or you will wreak havoc on the autograder. If your code passes all the test cases in the autograder you would receive full points for the implementation.

However even if your code does not necessarily pass all the test cases, we would evaluate your code and then award you partial points accordingly. In such cases it would be even more bene cial if you could give a short description of what you tried and where you had failed and that would help us in giving you better points.


    • Submission Instructions

For the nal submission you would be turning in a single zipped folder which should contain: { Folder having all the python les.(Search folder in this case)
{ PDF document containing your responses to the questions in Section 3 and 4.

For those of you who are doing it in teams, it is enough that one of the team members makes a submission. We would soon have groups created in Canvas for this and you could use that to upload your submission.

Please ensure all the submissions are done through canvas. Please do not email the instructor or the TA’s with your submission. Submissions made via email would not be considered for grading.

Naming: Your nal upload should be named in the format < uid >-Proj1.zip where < uid > is your Utah uid. Ex: u0006300-Proj1.zip

3

For this project you should rst unzip search.zip and then will ll in portions of search.py and searchAgents.py. Do not delete any of the les or change the names of any of those les in the project directory.

Written Answers: Place all written answers to questions in Section 3 and 4 in a single PDF document. This should be clearly named in the format < uid >-Proj1-answers.pdf, where < uid > is your Utah uid. Ex: u0006300-Proj1-answers.pdf. Please make sure to write your name at the top of the document!
























































4