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.

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

uphill scaling = 100

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

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.

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.

No comments yet.