In this assignment, you will build general-purpose search algorithms and apply them to solving puzzles. In Part 1 (for everybody), you will be in charge of a "Pacman" agent that needs to find paths through mazes while eating one or more dots or "food pellets." In Part 2 (for four-credit students), you will tackle small instances of the Sokoban puzzle.
As stated in the beginning of the course, you are free to use any high-level programming language you are comfortable with. This includes (but is not limited to) Java, C++, Python, and MATLAB. The focus of this course is on problem solving, not programming, and the grading will primarily be based on the quality of your solutions and your analysis, as evidenced by your written report.
You have the option of working in groups of up to three people. Three-credit students must work with three-credit students and four-credit students must work with four-credit students. To form groups, feel free to use Piazza. Needless to say, working in a group will not necessarily make your life easier, as the overhead of group coordination can easily outweigh the benefits.
Part 1: For everybody
1.1 Basic pathfindingConsider the problem of finding the shortest path from a given start state while eating one or more dots or "food pellets." The image at the top of this page illustrates the simple scenario of a single dot, which in this case can be viewed as the unique goal state. The maze layout will be given to you in a simple text format, where '%' stands for walls, 'P' for the 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 case of multiple dots. For the state representation, besides your current position in the maze, is there anything else you need to keep track of? For the goal test, keep in mind that in the case of multiple dots, the Pacman does not necessarily have a unique ending position. Next, implement a unified top-level search routine that can work with all of the following search strategies, as covered in class:
Run each of the four search strategies on the following inputs:
Part 1.2: Search with multiple dots Now consider the harder problem of finding the shortest path through a maze while hitting multiple dots. Once again, the Pacman is initially at P, but now there is no single goal position. Instead, the goal is achieved whenever the Pacman manages to eat all the dots. Once again, we assume unit step costs.
As instructed in Part 1.1, your state representation, goal test, and transition model should already be adapted to deal with this scenario. The next challenge is to solve the following inputs using A* search using an admissible heuristic designed by you:
You should be able to handle the tiny search using uninformed BFS -- and in fact, it is a good idea to try that first for debugging purposes, to make sure your representation works with multiple dots. However, to successfully handle all the inputs, it is crucial to come up with a good heuristic. For full credit, your heuristic should be admissible and should permit you to find the solution for the medium search in a reasonable amount of time. In your report, explain the heuristic you chose, and discuss why it is admissible and whether it leads to an optimal solution.
For each maze, give the solution cost and the number of nodes expanded. Show your solution by numbering the dots in the order in which you reach them (once you run out of numbers, use lowercase letters, and if you run out of those, uppercase letters).
Part 1 extra credit: Suboptimal searchSometimes, even with A* and a good heuristic, finding the optimal path through all the dots is hard. In these cases, we'd still like to find a reasonably good path, quickly. Write a suboptimal search algorithm that will do a good job on this big maze. Your algorithm could either be A* with a non-admissible heuristic, or something different altogether. In your report, discuss your approach and output the solution cost and number of expanded nodes. You don't have to show the solution path unless you want to come up with a nice animation for even more extra credit.
Part 2 (For four-credit students): Sokoban
In this part of the assignment, you will adapt your A* search to solve tiny instances of the Sokoban puzzle. Here is the description of the rules from Wikipedia:
The game is played on a board of squares, where each square is a floor or a wall. Some floor squares contain boxes, and some floor squares are marked as storage locations. The player is confined to the board, and may move horizontally or vertically onto empty squares (never through walls or boxes). The player can also move into a box, which pushes it into the square beyond. Boxes may not be pushed into other boxes or walls, and they cannot be pulled. The number of boxes is equal to the number of storage locations. The puzzle is solved when all boxes are at storage locations.You need to solve the four Sokoban instances below. In the following input files, '%' denote walls, 'b' denote boxes, '.' denote storage locations, and 'B' denote boxes on top of storage locations. The initial position of the agent is given by 'P'.
In the report, describe your heuristic(s) and justify whether they are admissible. For each input and each method of search, give the number of moves needed to reach a goal configuration, the number of nodes expanded, and the running time.
Part 2 Extra Credit
Report ChecklistYour report should briefly describe your implemented solution and fully answer the questions for every part of the assignment. Your description should focus on the most "interesting" aspects of your solution, i.e., any non-obvious implementation choices and parameter settings, and what you have found to be especially important for getting good performance. Feel free to include pseudocode or figures if they are needed to clarify your approach. Your report should be self-contained and it should (ideally) make it possible for us to understand your solution without having to run your source code. For full credit, in addition to the algorithm descriptions, your report should include the following.
Part 1 (for everybody):
Part 2 (for four-credit students):
Statement of individual contribution:
Submission InstructionsBy the submission deadline, one designated person from the group will need to upload the following to Compass2g:
Compass2g upload instructions:
Late policy: For every day that your assignment is late, your score gets multiplied by 0.75. The penalty gets saturated after four days, that is, you can still get up to about 32% of the original points by turning in the assignment at all. If you have a compelling reason for not being able to submit the assignment on time and would like to make a special arrangement, you must send me email at least four days before the due date (any genuine emergency situations will be handled on an individual basis). If you receive an approved extension, be sure to make a note of it at the top of your report.
Be sure to also refer to course policies on academic integrity, etc.