COMP 590-096 Fall 2011

Assignment 1: Maze Search

Due date: September 27, 11:59PM



This assignment is adapted from Berkeley CS 188 projects.

Part 1: Basic pathfinding

To begin with, you will consider the problem of finding a path through a maze from a given start state to a given goal state. This scenario is illustrated in the figure above, where the start position is indicated by the "Pacman" icon and the goal state is a dot. 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 goal (see sample maze file). For this part of the assignment, all step costs are equal to one.

Implement the following search algorithms for solving different mazes:

  • Depth-first search;
  • Breadth-first search;
  • Greedy best-first search;
  • A* search.
For greedy and A* search, use the Manhattan distance from the current position to the goal as the heuristic function.

Run each of the above algorithms on the small maze, medium maze, big maze, and the open maze. For each problem instance and each search algorithm, report the following:

  1. The solution and its path cost;
  2. Number of nodes expanded;
  3. Maximum tree depth searched;
  4. Maximum size of the fringe.
You can display the solution by putting a '.' in every maze square visited on the path (example solution to the big maze).

Part 2: Search with different cost functions

In general, we may want to penalize the agent differently for going to different maze cells. Consider the medium maze and these two cost functions:
  • c1 = 1/2^x;
  • c2 = 2^x.
Intuitively, c1 should cause the agent to prefer the right side of the maze, and c2 should cause it to prefer the left side. Implement uniform cost search and run it on the medium maze, reporting items a-d from Part 1 for both c1 and c2.

Part 3: Search with multiple goals

Now we consider a harder problem of finding the shortest path through a maze while hitting multiple goals (that is, you want to make the Pacman, initially at P, eat all the dots). Here is a sample problem instance. Once again, in this part, we assume unit step costs.

Revise your code from Part 1 to deal with this scenario. This will require changing the goal test (have you eaten all the dots?) and the state representation (besides your current position in the maze, is there anything else you need to know?).

Run the four search algorithms from Part 1 on the tiny search, small search, and tricky search. For each search method and problem instance, report the solution cost and number of nodes expanded.

You will be surprised how inefficient the uninformed searches are even on the very small problems! For the uninformed searches, feel free to put some reasonable upper limit on the number of nodes expanded, and quit without reporting a solution if this limit is exceeded. To be able to find a solution in a reasonable amount of time, it is crucial to design a good heuristic. You should spend some time thinking about this. In the report, discuss the heuristic that you chose and explain why it is admissible. Feel free to propose multiple heuristics and show results for all of them. For reference, my implementation of A* search on the tricky search found a path of length 61 after expanding around 7600 nodes. Try to design a heuristic that will do even better!

Part 4 (bonus): Suboptimal search

Sometimes, 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 medium search and big search. To get bonus points, you should be able to find a path of length around 350 on the big search after expanding around 700 nodes (of course, you're welcome to try to do even better than that!).

Tips

  • Make sure you get all the bookkeeping right. This includes handling of repeated states (in particular, what happens when you find a better path to a state already on the fringe) and saving the optimal solution path.

  • Pay attention to tiebreaking. If you have multiple nodes on the fringe with the same minimum value of the evaluation function, the speed of your search and the quality of the solution may depend on which one you select for expansion.

  • You will be graded on the correctness of your solution, not on the efficiency and elegance of your data structures. For example, I don't care whether your priority queue or repeated state detection uses brute-force search, as long as you end up expanding (roughly) the correct number of nodes and find the optimal solution. So, feel free to use "dumb" data structures as long as it makes your life easier and still enables you to complete the assignment in a reasonable amount of time.

  • Make your report easy to understand and interesting to read. Feel free to note any interesting observations you made or insights you gained while doing the assignment. The goal of the assignments is to get you to explore and to learn, and I would like to see what you learned reflected in your report.

  • I reserve the right to give bonus points for any advanced methods or especially challenging solutions that you implement. For this assignment, I may give you bonus points if you decide to do a nicer graphical visualization of the mazes and the found solutions.

Submission Instructions

You will need to turn in the following:
  1. A report in PDF format. The 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 me to understand your solution without having to run your source code.

    The name of the report file should be lastname_firstname_assignment1.pdf.

  2. Your source code compressed to a single ZIP file. The code should be well commented, and it should be easy to see the correspondence between what's in the code and what's in the report. You don't need to include executables or various supporting files (e.g., utility libraries) whose content is irrelevant to the assignment. If I find it necessary to run your code in order to evaluate your solution, I will get in touch with you.

    The name of the code archive should be lastname_firstname_assignment1.zip.

Submit both your files through Blackboard as follows:

  1. Log in to Blackboard and access COMP590.096.
  2. Select Tools | Digital Dropbox from the navigation menu on the left.
  3. Use Send file to submit an assignment for grading. Add file merely stores a file in your personal dropbox.
  4. In Digital Dropbox, the file should be listed as Submitted, and not just Posted.

Late policy: You lose 25% of the points for every day the assignment is late. 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 let me know at least a week before the due date (any genuine emergency situations will be handled on an individual basis).

Academic integrity: Feel free to discuss the assignment with each other in general terms, and to search the Web for general guidance (not for complete solutions). Coding should be done individually. If you make substantial use of some code snippets or information from outside sources, be sure to acknowledge the sources in your report.