Introduction to Artificial Intelligence (Computer Science ,Python)

Module: CSE 5120 Introduction to Artificial Intelligence

Assessment brief: The code and resources provided in this homework

Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman’s first step in mastering his domain.

The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore. You can download all the code and supporting files as a zip folder from homework 1 link given on Blackboard.

Your homework is based on two parts as given below:

1. Code implemented for search algorithms in given search.py file (in specific sections as indicated in detail below)

2. A brief report on what you did for each algorithm (i.e., how you implemented with screenshots from autograder script given in the folder)

After downloading the code, unzipping it, and changing to the directory, you should be able to play a game of Pacman by running the following command.

python pacman.py

pacman.py supports a number of options (e.g. --layout or -l). You can see the list of all options and their default values via python pacman.py -h.

All the commands you will need in this homework can be found in the file commands.txt for easy copying and pasting. You can use Spyder (installed through Anaconda from week 1 Thursday’s lecture) or other IDE for this work.

Files to Edit and Submit: You will need to edit and submit (search.py) and (searchAgents.py only if required) files to implement your algorithms. Once you have completed the homework, you are welcome to run automated tests using an autograder.py given in the folder before you submit them for accuracy. You do not need to submit autograder.py file in your code submission but will need to test your algorithms with autograder.py to copy screenshots in your report. Please do not change the other files in this distribution or submit any of the original files other than these files.

Academic Dishonesty: Your code will be checked against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, they will be detected easily, so please do not try that and submit your own work only. In case of cheating, the University’s academic policies on cheating and dishonesty will strictly apply which may result from the deduction in your grade to expulsion.

Figure 1: Breadth First and Uniform Cost search algorithms - pseudocode

Figure 2: Tree Search algorithm pseudocode

1

Tasks for homework 1

1. Understanding the code base (not graded)

In searchAgents.py, you will find a fully implemented SearchAgent, which plans out a path through Pacman's world and then executes that path step-by-step. The search algorithms for formulating a plan are not implemented: your task is to implement them.

First, test that the SearchAgent is working correctly by running the following command.

python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch

The command above tells the SearchAgent to use tinyMazeSearch as its search algorithm. This algorithm is implemented in search.py. Pacman should navigate the maze successfully.

Now you will need to implement different search algorithms to help Pacman plan its routes and reach its goal. Remember that a search node must contain not only a state but also the information necessary to reconstruct the path (plan) which gets to that state from the start state.

Important note: 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).

Important note: Make sure to use the Stack, Queue and PriorityQueue data structures provided to you in util.py! These data structure implementations have particular properties that are required for compatibility with the autograder.

Hint: The algorithms we covered so far are quite similar. DFS, BFS, UCS, and A* algorithms differ only in the details of how the fringe (or frontier) is managed. So, concentrate on getting DFS right and the rest should be relatively straightforward. Indeed, one possible implementation requires only a single generic search method which is configured with an algorithm-specific queuing strategy. (Your implementation need not be of this form to receive full credit.)

2. Depth First Search (1%)

Implement the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py.

Your code should be able to solve these tasks quickly.

1. python pacman.py -l tinyMaze -p SearchAgent

2. python pacman.py -l mediumMaze -p SearchAgent

3. python pacman.py -l bigMaze -z .5 -p SearchAgent

Evaluation: Run the following command to test your solution: python autograder.py -q q1. The first 4 test cases are basic test cases. Together they account for 0.8%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.2%.

3. Breadth First Search (1%)

Implement the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py.

Your code should be able to solve these tasks quickly.

1. python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

2. python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

Evaluation: Run the following command to test your solution: python autograder.py -q q2. The first 4 test cases are basic test cases. Together they account for 0.8%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.2%.

4. Uniform Cost Search (1%)

BFS tries to minimize the number of actions taken, but not necessarily the least-cost path. By varying the cost function, the Pacman can be encouraged to explore different paths. By changing the cost function, we can encourage Pacman to find different paths. For example, we can charge more for dangerous steps in ghost-ridden areas or less for steps in food-rich areas.

Implement the uniform-cost search (UCS) algorithm in the uniformCostSearch function in search.py (the agents and the cost functions are implemented for you).

You should now observe successful behavior in all three of the following layouts.

1. python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs

2. python pacman.py -l mediumDottedMaze -p StayEastSearchAgent

3. python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

Evaluation: Run the following command to test your solution: python autograder.py -q q3. The first 4 test cases are basic test cases. Together they account for 0.8%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.2%.

5. A* Search (2%)

Implement the A* search algorithm in the aStarSearch function in search.py. A* takes a heuristic function as an argument.

You need to test your A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic (already implemented).

python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar, heuristic= manhattanHeuristic

Evaluation: Run the following command to test your solution: python autograder.py -q q4. The first 5 test cases are basic test cases. Together they account for 1.5%. If any one of them fails, the fifth test case will not be evaluated. The fifth test case accounts for 0.5%.

Report

Brief description of your work here acknowledging your collaboration with your class fellow (or a friend from other CSE 5120 section), and the capacity at which he/she collaborated with you, followed by the algorithms you implemented.

1. Depth First Search

Your brief explanation (e.g., does DFS expand the shallowest or deepest unexpanded node? did you use Stack, Queue, or PriorityQueue in your code?) with screenshots of your code Evaluation (results from autograder.py)

2. Breadth First Search

Your brief explanation (e.g., does BFS expand the shallowest or deepest unexpanded node? did you use Stack, Queue, or PriorityQueue in your code?) with screenshots of your code Evaluation (results from autograder.py)

3. Uniform Cost Search

Your brief explanation (e.g., does BFS expand the cheapest or closest node to the goal state? What function did you use to expand the cheapest or closest node in this algorithm and at which line?) with screenshots of your code Evaluation (results from autograder.py)

4. Breadth First Search

Your brief explanation (e.g., does A* use g(n) or h(n)? Where in the code are using retrieving the cost of an unexpanded node to plan and which function did you implement/use to get g(n), h(n), f(n) etc?) with screenshots of your code Evaluation (results from autograder.py)