CS 242 Fall 2009 : Assignment 2.3
CS 242 Fall 2009 : Assignment 2.3
This page last changed on Oct 05, 2009 by celliso2.
Spend 10 minutes and go through your subversion repository. Clean out any files that you find that are binaries, generated, or not needed. This includes output from programs, eclipse workspace and plug-in settings, and other junk that hogs space on the svn server.
Last week, we suggested that you use the wall-following algorithm to find a solution to the maze. Yet, since the focus was on correctness, testing and modularity, we did not focus much on performance. This week we will use a better strategy than the wall-following algorithm. Before using this strategy, it’s important to realize why it’s effective in solving this kind of problem. Fundamentally, the maze problem is an example of a deterministic search problem; there will always be a path from the start to finish. There should not be a case where we get stuck in a never-ending cycle, so that the strategy will always find a solution, no matter how long it takes. Yet, we also want to go along the path that is least expensive, so that after looking at all the other options, we can guarantee that the final solution is the best. Let’s take a step back and think about naive ways to solve this puzzle. What could we do? We could just use trial and error and stop at the first solution we find. Yet, this may not guarantee we’ve found the cheapest solution. An extremely time-consuming but systematic way to find the best (even sub-optimal) solution to this maze is to just start enumerating all possible paths with their costs and then choose the cheapest one.
There are many different techniques to search techniques that have been developed over time, but we’re not asking you to come with them. We’re giving you the technique which guarantees that the search will not keep going forever. What we are asking you to do is write a program that implements it for the given maze problem. For this assignment, the strategy we would like you to use to solve the maze is the A* (A-star) algorithm. The justification for why A* works for these problems is based on an elegant and formal proof, but this is beyond the scope of this course. Nevertheless, in the next section, we will guide you through understanding how it works and how it can be applied to the maze problem.
Please note that this assignment is due Wednesday, October 7th, 2009 at 8AM. Please be sure to submit in SVN, and ask your moderator or TA before the deadline if you have any questions. Also, make sure to place your work in a folder called Assignment2.3. This is critical so that we can export everyone’s code for code reading.
A* is a graph search algorithm, where the nodes in the graph represent the position in the grid. It searches the graph for a specific path to a goal node, where the goal node marks the end of the maze. The choice of which intermediate nodes to move to, or expand, next is determined by some overall cost function, Cost(currPos). This cost function is defined in terms of two other functions:
where accum(currPos) and est(currPos) are as follows:
In our case, accum(currPos) would be a (weighted) sum of the steps needed to get from starting point to the current position, with each step weighted by the change in elevation. The start and end will be specified from the beginning. The step cost will be calculated by determining the difference in elevation of one point to the other.
The est(currPos) would be an estimated cost to get from the current position to the goal. For this assignment, the heuristic cost function, est(currPos), will be pre-defined. Specifically, we want you to use the manhattan distance from the current position to the endpoint. As an example, if the current position is (2, 3) and the end position (10, 7) then the cost of travelling the manhattan distance is (10 -2) + (7 -3) = 12. Note that the travelling the “manhattan distance route” may not actually be legal in your maze; we use this distance only as a rough estimate to our goal so that it will give the optimal solution.For the cost function, use the diagonal shortcut.
We also want you to consider a more sophisticated heuristic function. In this heuristic function, we estimate the distance from current position to the goal by calculated the diagonal distance with change in elevation. The diagonal distance is the “hypotenuse” of the two “legs” of the manhattan path. So, in the above example, the diagonal distance is sqrt[ (10-2)^2 + (7-3)^2] = sqrt(80) = 8.94 In this case, you will be given two separate uphill scaling and downhill scaling constants, which will be specified from some external source.
est(x, goal) = diag_distance(x,goal) + [elevation(goal) – elevation(x) ] * (vertical scaling)
In the above, if the change in elevation is negative (going downhill) then your vertical scaling uses downhill scaling. If the change in elevation is positive(going uphill), then you use uphill scaling. You can use the following downhill and uphill scaling factors as initial/default values, but note that you will still need to read these in from some external source file.
downhill scaling = -50
In the above scaling, you “regain some energy” by going downhill, but you become twice as “exhausted” by going uphill.
The cost should include a constant factor of 100 for moves to the north, south, east, or west, and 141 for moves diagonally. This makes your cost function something like:
Consider the following example (taken from last semester), where we represent X’s to be black and blanks to be white in the maze. Also, S denotes the start position, and E denotes the end position. Please note that this is a representation of the maze. Note that the input will be different from the previous assignment; namely, it will be a BMP file derived from a DEM file. This means that each cell has , in addition to color property and location, an elevation associated with it. In this way, the cost of getting from one cell to the other depends on how much total ascending or descending you have to do. So, for getting from cell c to c’, you will need to weight your step cost by the ratio of elevation of c’ to the elevation of c. In this way, moving from a lower elevation to a higher elevation should give you a weight of greater than 1, and moving from a higher elevation to a lower elevation should give you a weight of less than 1. In your code, you should be sure to translate the BMP into this representation before running your algorithm on the maze.
With the “A*” algorithm, assume your heuristic cost function is manhattan distance, and that (for the sake of simplicity) there is no elevation change on the maze. With no elevation change, we know that the step cost is weighted by 1 because the weight is determed by the ratio of the elevation of the current position in the maze to the elevation of the next position that you move to. In the example above, your algorithm would follow the optimal path [(0,1), (1,1), (2,1), (3,1), (4,1)], and the path cost would be 4. So, when the algorithm completes, you should output this path that it traversed and also give the total path cost. Note that this is significantly better than the wall-follower and gives you the optimal path.
A perfect maze is defined as a maze which has one and only one path from any point in the maze to any other point no inaccessible sections, no circular paths, and no open areas. The example shown in class illuminates clearly how such mazes are defined. It is important to realize that you will get a fixed starting point and a fixed ending point. Below is the example, and you can also refer to slide 5 of lecture 4.2 for more details on this.
The following are notes about your implementation, and the choices you should consider in implementation. Be sure to justify your design decisions here.
1. When searching for a path through the maze, A* can use breadth-first search approach or depth-first search approach.
2. Think about which data structure is well-suited to store the “next” nodes
3. An evaluation function can be written in many different ways; some are more suited for fast numerical computation while others are not.
4. Your heuristic , or est() function, should use manhattan distance. Please note, however, that you should write your program so that you are able to plug in another heuristic function very easily.
We don’t expect any fancy, enhanced versions of A* or any other bold approaches. The most important neccessity for your program is to output some answer; specifically, your program should be able to stop and give some error message if it cannot find a solution. If there is a solution, the program should output the corresponding maze path in some readable format, and this should be the optimal solution. To make it easier to deal with, we have defined the idea of perfect mazes. Refer to the lecture notes on mazes for clarification on this. If you have implemented A* properly, you should be able to satisfy these three requirements.
Ultimately, we want to be able to traverse elevation maps. They will be in the form below (output BMPs from assignment 1). The input format should not change your implementation of the underlying logic for implementing A*.
Below are the exact requirements for completing this assignment. You will be graded primarily on your design, documentation, and usability of your library and functions. You must be able to run all your unit tests and inform the user if they have passed or failed. You need to have some way to demonstrate that the code you wrote works using the A* search algorithm. You will be secondarily graded on your implementation.
An example of A* in action is given by the graphic below (source: http://en.wikipedia.org/wiki/A*). Additionally, http://www.policyalmanac.org/games/aStarTutorial.htm has a good explanation of how A* applies to a grid.
JDB Can be used to debug your java program in a GDB-like environment
|Document generated by Confluence on Feb 22, 2012 18:18|