Description

Credits: Berkeley CS188 Pacman projects
Updated By: Rahul Kunji & Jason Nie
In this assignment, you will build general-purpose search algorithms and apply them to solving puzzles. In Part 1 be in charge of a “Pacman”-like agent that needs to find a path through maze to eat a dot or “food pellet.” In Part need to find a single path that goes through all the dots in the maze.
Programming language
Contents
• Part 1: Basic Pathfinding
• Part 2: Search with multiple dots
• Extra Credit
• Provided Code Skeleton
• Deliverables
• Report checklist
Part 1: Basic Pathfinding
Consider the problem of finding the shortest path from a given start state while eating one or more dots or “food The image at the top of this page illustrates the simple scenario of a single dot, which in this case can be viewed unique goal state. The maze layout will be given to you in a simple text format, where ‘%’ stands for walls, ‘P’ fo starting position, and ‘.’ for the dot(s) (see sample maze file). All step costs are equal to one.
Implement the state representation, transition model, and goal test needed for solving the problem in the general multiple dots. For the state representation, besides your current position in the maze, is there anything else you n track of? For the goal test, keep in mind that in the case of multiple dots, the Pacman does not necessarily have a ending position. Next, implement a unified top-level search routine that can work with all of the following searc as covered in class and/or the textbook:
• Depth-first search
• Breadth-first search
• Greedy best-first search • A* search
For this part of the assignment, use the Manhattan distance from the current position to the goal as the heuristic f greedy and A* search.
Run each of the four search strategies on the following inputs:
• Medium maze
• Big maze
• Open maze
The provided code will generate a pretty picture of your solution. Your report should include
• The solution picture.
• The length of the path. Include both the start and goal positions as part of your path and path length • Number of nodes expanded by the search algorithm.
Part 2: Search with multiple dots
Now consider the harder problem of finding the shortest path through a maze while hitting multiple dots. Once a Pacman is initially at P, but now there is no single goal position. Instead, the goal is achieved whenever the Pacm manages to eat all the dots. Once again, we assume unit step costs.
As instructed in Part 1, your state representation, goal test, and transition model should already be adapted to dea scenario. The next challenge is to solve the following inputs using A* search using an admissible heuristic desig you:
• Tiny search
• Small search
• Medium search
You should be able to handle the tiny search using uninformed BFS. In fact, it is a good idea to try that first for d
purposes, to make sure your representation works with multiple dots. However, to successfully handle all the inp crucial to come up with a good heuristic. For full credit, your heuristic should be admissible and should permit y the solution for the medium search in a reasonable amount of time. In your report, explain the heuristic you chos discuss why it is admissible and whether it leads to an optimal solution.
For each maze, your report should include (as for Part 1) the solution picture, the solution cost, and the number o expanded in your search.
Extra Credit Suggestion
Sometimes, even with A* and a good heuristic, finding the optimal path through all the dots is hard. In these cas still like to find a reasonably good path, quickly. Write a suboptimal search algorithm that will do a good job on maze. Your algorithm could either be A* with a non-admissible heuristic, or something different altogether. In y discuss your approach and output the solution cost and number of expanded nodes. Note that the extra credit wil to 10% of what the assignment is worth.
Provided Code Skeleton
We have provided ( tar file or zip file) all the code to get you started on your MP, which means you will only ha the search functions. Do not modify provided code. You will only have to modify search.py.
maze.py
• getStart() :- Returns a tuple of the starting position, (row, col)
• getObjectives() :- Returns a list of tuples that correspond to the dot positions, [(row1, col1), (row2, col2)
• isValidMove(row, col) :- Returns the boolean True if the (row, col) position is valid. Returns False othe
search.py
There are 4 methods to implement in this file, namely bfs(maze), dfs(maze), greedy(maze), and astar(maze). ( need to add another named search method if you implement an additional search method for extra credit.) Each o functions takes in a maze instance, and should return both the path taken (as a list of tuples) and the number of s explored. The maze instance provided will already be instantiated, and the above methods will be accessible.
To understand how to run the MP, read the provided README.md or run python3 mp1.py -h into your termin following command will display a maze and let you create a path manually using the arrow keys.
python3 mp1.py –human maze.txt
The following command will run your astar search method on the maze.
python3 mp1.py –method astar maze.txt
You can also save your output picture as a file in tga format. If your favorite document formatter doesn’t handle such as gimp can convert it to other formats (e.g. jpg).
Tips
• In your implementation, make sure you get all the bookkeeping right. This includes handling of repeated particular, what happens when you find a better path to a state already on the frontier) and saving the opt solution path.
• You will be graded primarily on the correctness of your solution, not on the efficiency and elegance of yo structures. For example, we don’t care whether your priority queue or repeated state detection uses brutesearch, as long as you end up expanding exactly the correct number of nodes (except for small difference by differences among tie-breaking strategies) and find the optimal solution. So, feel free to use “dumb” d
structures as long as it makes your life easier and still enables you to find the solutions to all the inputs in reasonable amount of time.
Deliverables
This MP will be submitted via compass.
Please upload only the following two files to compass.
1. search.py – your solution python file
2. report.pdf – your project report in pdf format
Report Checklist
Your report should briefly describe your implemented solution and fully answer the questions for every part of t assignment. Your description should focus on the most “interesting” aspects of your solution, i.e., any non-obvio implementation choices and parameter settings, and what you have found to be especially important for getting g performance. Feel free to include pseudocode or figures if they are needed to clarify your approach. Your report self-contained and it should (ideally) make it possible for us to understand your solution without having to run y code.
Kindly structure the report as follows:
1. Title Page:
2. Section I:
Algorithms (Search). This section should describe algorithms and data structures used for all four search
Answer questions like: what is a state? what is a node? are they the same or different in your implementa
What is the frontier? Do you maintain an explored states list? How are repeated states detected and mana
3. Section II:
Algorithms (A* and Greedy BFS). This section should describe the heuristic(s) used for A* and Greedy B both the single dot and multiple-dot situations Provide proof that the heuristics for A* are admissible
4. Section III:
Results (Basic Pathfinding). For every algorithm in part 1, (DFS, BFS, Greedy, A*), and every one of the (medium, big, open), give the maze screenshot with the computed path, the solution cost and the number expanded nodes (12 cases total)
5. Section IV:
Results (Search with multiple dots). For part 2, for each of three mazes (tiny, small, medium), give the so screenshot, solution cost, and number of expanded nodes for your A* algorithm.
6. Extra Credit:
If you have done any work which you think should get extra credit, describe it here
7. Statement of Contribution:
Specify which team-member performed which task. You are encouraged to make this a many-to-many m applicable. e.g., You can say that “Rahul and Jason both implemented the BFS function, their results wer for debugging and Rahul’s code was submitted. Jason and Mark both implemented the DFS function, Ma never ran successfully, so Jason’s code was submitted. Section I of the report was written by all 3 team m Section II by Mark and Jason, Section III by Rahul and Jason.”.. and so on.
Your report must be a formatted pdf document. Pictures and example outputs should be incorporated into the do Exception: items which are very large or unsuitable for inclusion in a pdf document (e.g. videos or animated gifs put on the web and a URL included in your report.
Extra credit:
We reserve the right to give bonus points for any advanced exploration or especially challenging or creative sol you implement. This includes, but is not restricted to, the extra credit suggestion given above.