Introduction

This week, you will continue to work on your Mars Pathfinding algorithm on MATLAB or Octave. However, this time, you will implement A* heuristic search to try to increase the speed of your search over the standard UCS algorithm.

No Loops

As the scenario provided to us is realistic depiction of the terrain map on Mars, we can safely assume that there are no negative cycles in our graph. This means that the weight of any node on the graph will never approach negative infinity.

This is based on the fact that the energy used by the rover to travel upwards will always be greater than the energy returned back to the rover by travelling downwards for the same distance delta.

Cost Functions

Unfortunately, the cost functions given in the starter code does not accurately represent the situation given above. There are edge cases to consider.

function [cost] = costFN_up(delta)
    cost = delta^2;
end

function [cost] = costFN_dn(delta)
    cost = delta;
end

Warning: What if delta is rounded to 0? What about 1?

Stopping Condition

Contrary to popular belief, depending on how you define your weights, you actually CAN stop the search on any iteration of which your algorithm clears the goal node. We can safely assume that once a node is cleared that no shorter path exists.

This can be derived from the assumption that the energy to travel upwards in elevation will always be greater than the energy gained from travelling downwards in elevation.

-- proof removed --

Feasible Heuristic Function

Location will be involved, but it is not clear how.

Height difference will be involved, but is not clear how.

You are allowed to do pre-processing on the map and pass additional information to the graph_search() function. The pre-processing must be reasonable.