There's a much easier way to do this, though. The trick is, you figure the route backwards from the destination. For each position on your map, you end up with a minimum cost route to the destination. During computation, you have to keep a list of "boundary" points (starting with just the destination point) each time you iterate through this list, the boundary expands. When it reaches the start point, you're done. A boundary point has a known minimum-cost path to the destination, but it has neighboring points for which this hasn't been computed yet.

The rule to expand a boundary point, X, is, first, find each of its neighbors (even the neighbors that already have costs -- this is very important) and compute the cost from that neighbor (call it Y) to X. Add the known cost from X to the destination, and see if this estimate of the cost from Y to the desination is better than the cost that Y already has. If it is, store that cost in Y. If there's already a better route from Y to the destination, don't bother. If Y had no cost in it at all (that is, this is the first time we've added a cost to Y) or if you improved the cost, add Y to the end of the boundary list. Finally, when we've processed all the neighbors of X, delete X from the boundary list.

It may be safer to store the new boundary in a separate structure from the old one, just because you must be very sure that you don't start using any new boundary point until ALL of the old ones have been fully processed. Another point is that the program ends not when the start point BECOMES a boundary point, but when it ceases to be one. (That is when it becomes an interior point.) For something like the rover, that's a fine detail, though.

This is called dynamic programming, and it is far and away the best way to handle a problem of this type. I can't see any reason anyone would consider using a different algorithm, unless the memory constraints are very, very tight.

--Greg

Not sure here, but couldn't this process get locked into local minimum rather than finding a global minimum?

-Mike

Here is the REALLY BIG picture showing Victoria Crater to Endeavour Crater with the terrain model and E Corridor route indicated in black.


-Mike

Again, here is the E Corridor Route proposed earlier in the thread. The key section will be getting through the Victoria Crater debris apron to where this route joins with some of the other proposed routes at the yellow square. (From the yellow square to the end of this terrain modeled section it is a fast green route all the way to the SE corner.) This section is shown below, black boxes are 50 m square:


Taking the most difficult terrain in the 50 m box to be the terrain type of the entire box (worst case scenario), here is the box-by-box terrain evaluation for the E Corridor route:

Finally, with these 50 m box terrain classification the entire route can be scored based on historical drive data.

The estimated drive time (= score) for the E Corridor Route is 53 days


-Mike

Eegads, man. I can't believe how industriously you have been promoting the Eastward First Route. I'm almost convinced. We need more HiRise imagery to see the endgame, but I'm still onboard with your suggestion.

I think it is coming down to the two questions we had from the beginning. Should the rover take one of the three easy, southerly paths and then hope it can punch through the relatively short sections of tricky terrain beyond, or should it skirt the potentially dangerous stuff with a somewhat longer drive?

I hate to say it, but the odds are against Oppy completing this trip. The good news is that whichever direction is chosen, we'll see something new.

You are right, the reason I didn't implement it in the first place was simply constraints on the amount of time I can spend on this 'job' and I was worried it would indeed use up a lot of memory (I wanted to avoid working with a grid), but as I'm rewriting most of the code now anyway I might add it as an extra feature. It will be a bit easier now as I'm now using latitude/longitude coordinates instead of pixel locations so I'm no longer 'stuck' to one image only.

It all comes down a bit to how much faith you place on software-generated routes, originally I started this toolkit only for image-analyzes, and the 'route finding' option was only a quick add-on. But I see what I can do

Regards,

Geert.

The SE Direct route from Victoria Crater apron through the debris field to the fast green route intersection.
Black boxes are 50 m square:


Taking the most difficult terrain in the 50 m box to be the terrain type of the entire box (worst case scenario), here is the box-by-box terrain evaluation for the SE Direct route:

The estimated drive time (= score) for the SE Direct Route is 43 days.


This is 10 days shorter than the E Corridor route, but proportionally more difficult terrain needs to be traversed. There is a larger percentage of slow terrain (violet and above). A small patch of bigger dunes is crossed by pavement.

-Mike

The South Central route from Victoria Crater apron through the debris field to the fast green route intersection.
Black boxes are 50 m square:


Taking the most difficult terrain in the 50 m box to be the terrain type of the entire box (worst case scenario), here is the box-by-box terrain evaluation for the South Central route:

The estimated drive time (= score) for the South Central Route is 47 days.


Some of the "Red terrain on pavement squares" may be overcautious. A visual inspection of the original HiRise image shows that they are most likely Violet on pavement terrain. Being uber-conservative, I kept them as red terrain. (In this drive direction it doesn't affect the estimated drive time).

-Mike

Grin. Nope. It's provably optimal. Dynamic programming really has extensive applications. It's a key part of any modern algorithms class. It doesn't work for everything, but it's great for route-finding problems.

--Greg

Let me know if you want some help with it. (Send me a private message, if you like.) I know some tricks that'll let you keep the grid on disk (mostly) and just work with the boundary in memory. I'll need to know things like how you're storing the grid-related info and what programming language you're using.

As for how reasonable it is, I hear you. There's every chance that there just isn't enough info in the HiRise images for the result to be meaningful. On the other hand, it ought to provide some entertainment to be able to offer an estimated "fast track" time from the rover's location to the target -- even if it's not perfect.

--Greg

At the expense of making three posts in a row, it just occurs to me that the A* algorithm was pretty much made for this kind of problem.

http://en.wikipedia.org/wiki/A*_search_algorithm

The extra thing that this gives you is that it lets you use the fact that from any point you can make an optimistic estimate of the drive time from that point just by taking the straight-line distance and assuming perfectly flat terrain. A* will also get the optimal result, and, in this case, it ought to use less computation and less memory.

Note that our cost function (driving time) is monotonic -- a negative cost would mean there's terrain that takes negative time to cross -- so we can make use of the "closed set" the Wikipedia article talks about. (This is similar to the "memoization" that makes dynamic programming work, and without it, this will NOT run in reasonable time or memory.) That just means you don't ever recompute the distance to the same node twice. Since A* hits nodes in increasing distance order, if a point in the grid has ever been visited before, then you know it had a better route. A bit-map of the grid would be enough.

Sigh. This stuff is MUCH easier to explain in person in front of a white-board . . .

--Greg

The SW Passage route from Victoria Crater apron through the debris field to the fast green route intersection.
Black boxes are 50 m square:


Taking the most difficult terrain in the 50 m box to be the terrain type of the entire box (worst case scenario), here is the box-by-box terrain evaluation for the SW Passage route: