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:
For greedy and A* search, use the Manhattan distance from the current position to the goal
as the heuristic function.
- Depth-first search;
- Breadth-first search;
- Greedy best-first search;
- A* search.
Run each of the above algorithms on the
big maze, and the
For each problem instance and each search algorithm, report the following:
You can display the solution by putting a '.' in every maze square visited on the
path (example solution to the
- The solution and its path cost;
- Number of nodes expanded;
- Maximum tree depth searched;
- Maximum size of the fringe.
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:
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
small search, and
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!).
- 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
- 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.
You will need to turn in the following:
- 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.
- 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:
Log in to Blackboard and access COMP590.096.
Select Tools | Digital Dropbox from the navigation menu on the left.
Use Send file to submit an assignment for grading. Add file merely stores a file in your personal dropbox.
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.