CS 242 Fall 2009 : Assignment 2.3

This page last changed on Oct 05, 2009 by celliso2.

Part I

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.

Part II

Overview

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.

Submission

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*  algorithm

     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:

cost(n) = accum(n) + est(n)

where accum(currPos) and est(currPos) are as follows:

accum(currPos) - the total cost so far from the start of the maze to the  node currPos
est(currPos) - an estimate of the distance from node currPos to the goal node.

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
uphill scaling     =   100

In the above scaling,  you “regain some energy”  by going downhill, but you become twice as “exhausted”  by going  uphill.

Clarification

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:

cost(n) = accum(n) + (100 or 141) + est(n)

A* Example

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.

XXXXX
S      E
XX  XX
XX  XX

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.

Perfect Mazes

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.

xSxxxxxxxxxxxxxxxx
X*                x x x
x xx x xxx x xxx x
x x x x * x         xx
x xxxxxx xxxxxx xx
x x x*       x     * x
xx * xxx x x xx x
x xxx *xxxx xxxx
x x x               * x
XxxxxxxxxxxxxxxxEx

Implementation Notes:

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.

Other notes:

  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.

Sample Inputs

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*.

Requirements

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.

  • Usabaility
    • Your program exit cleanly in all cases: 2
    • It is clear how your program should be used: 2
    • There are no unwanted side effects (i.e. clobbered files): 2
  • Documentation
    • Your code contains ample comments: 4
    • Your program provides useful feedback to the user: 4
  • Code Design
    • Your code is modular: 4
    • Functions only do one thing: 2
    • Each function is no longer than 25 lines of code: 2
    • There were no code smells in your code (-2 for each): 10
  • Functionality
    • Each library function has a well thought out unit test (minimum of 10 tests, could be the same as last time): 4
    • Cost function is calculated reasonably: 2
    • Cost/Heuristic calculations are parameterized: 2
    • Library can solve a maze with BMP input and print the solution: 4
    • If there is a solution, your program should output the path and optionally the cost of path: 2
    • Program should be able to determine if a maze is solvable or not: 2
    • You cleaned out your svn repository: 4
    • You commited on time and to the correct location: 4
  • Participation
    • You actively participated in discussion: 4
    • You came prepared based on your assigned code reading: 4
Total 64 Points

References

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
http://java.sun.com/j2se/1.3/docs/tooldocs/solaris/jdb.html

mountains.bmp (image/bmp)

MountainView.bmp (image/bmp)

PyramidPeak.bmp (image/bmp)

colorado.bmp (image/bmp)

RedWoodPoint.bmp (image/bmp)

Tahoe.bmp (image/bmp)

SouthTahoe.bmp (image/bmp)
Document generated by Confluence on Feb 22, 2012 18:18

  1. No comments yet.

  1. No trackbacks yet.