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.
Click to view attachment

-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:
Click to view attachment

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:
Click to view attachment

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
Click to view attachment

-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:
Click to view attachment

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:
Click to view attachment

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

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:
Click to view attachment

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:
Click to view attachment

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

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:
Click to view attachment

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:
Click to view attachment

The estimated drive time (= score) for the SW Passage Route is 44 days.
Click to view attachment

This is about the same as the estimated time for the SW direct route, but it traverses much less violet terrain. It crosses mostly Blue terrain. Again the small patch of red on pavement terrain is probably overestimated. Due to Oppy's current position, this entry point is probably the easiest to access (might save a day).

This is my favorite route so far.

-Mike

And I'm likin' it a lot, JM.
But I could use some reassurance regarding that nasty splotch of red on the southerly leg. (Looks malignant.)
Are we able to focus in on that stretch at a higher resolution - say 5 meter, or even 2 meter blocks - to see if it's as perilous as it looks?
Finally, can you detail the procedure for inputting (golf term) the scientists' points of interest?
TIA

The W Spur route from Victoria Crater apron through the debris field to the fast green route intersection.
Black boxes are 50 m square:
Click to view attachment

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:
Click to view attachment

The estimated drive time (= score) for the SW Passage Route is a whopping 59 days.
Click to view attachment

There is a funky dark pattern with a brighter ring in the HiRise image near the bright green area. I'm flagging this as a potential Erebus-style dust trap. But the terrain surrounding this is pretty flat (aqua or blue) and going around this area shouldn't add to the drive time.

(There are a few of these S of the indicated path where the path bends to the E. The proposed path avoids these by a wide margin.)

-Mike

Yup! I'll put together some more detailed stuff covering the SW Passage.
(The proposed routes do not take into account any scientific targets (are there any at this point?), but the SW passage does just pass to the S of the 50 m diameter "cute" crater.)

Here's a comparison chart showing selected Victoria apron escape routes, with estimated times and terrain profiles for each of the routes:
Click to view attachment

-Mike

Mike, your work is just (sorry no enough good words come to mind).
Anyway, I just want to make sure here that you're aware that, apparently, the treck has started

My money is on the SW route.
It has the least amount of potentially dangerous stuff and the southerly leg gives us the half-pipes/pavement to drive between the bigger ripples.

Funny you mention it. The current drive direction mosaic is SW.

Anyway will be fun to see what happens...

STDEV analyzes of area south of victoria for southerly driving direction, analyzes was carried out at 1 mtr resolution, red spots showing potentially dangerous areas.

Click to view attachment

Unprocessed image of same area as above for comparison

Click to view attachment

HighRes STDEV analyzes of area SW of Victoria crater for SW driving direction, red areas state potentially dangerous places

Click to view attachment

Unprocessed image of above for comparison, had to reduce scale slightly to fit within attachments limits

Click to view attachment

Figured I'd have a go at implementing a route finding algorithm. The one I had mentioned earlier, A*.

Basically I took Juramike's red/blue/green map. (Thanks a million for your efforts by the way, amazing)
Broke it down into a grid with each grid square being X pixels wide/high.
For each grid location I average the pixels it contains and get the RGB value.
I break this down into the individual colour values:
R = 'Bad' terrain
B = 'Medium' terrain
G = 'Good' terrain

Then each grid is given a score based on these values, using a function I came up with from playing around. It's completely and utterly made up.
So the score/cost of travelling through a grid location is:


The route I have in the image here has grid squares of 5x5 pixels and took about 1 minute to generate on my 1.4Ghz Pentium M Processor with 500MB RAM so it's not too bad. The route shown is from the Top Left to the Bottom Right, just for illustration purposes.

If anyone has a good way of using the R,G,B values like above then let me know and I'll plug it in!

Edit: Seems I have a few bugs. God only knows how I got the route below from the code I just spotted.

Wow! Really nice.

I'm going to guess that your algorithm is trying to find a short path from the origin (0,0) which must be at upper left, to the largest X,Y which must be at lower right.

-Mike

Yep, forgot to mention that point about the origin. It seems the code is kinda doing what I thought after all so it's not too bad.

When it comes to balancing distance and traversability I'm not sure how it works out. I'll try at some stage to do something like you have to look at the type of terrain per step and see what the overall count is like.

Not tonight though.

Here is an overlay of selected proposed routes on the Differential Shift 10E5S terrain model for the region S of Victoria Crater:
Click to view attachment

And here is the same overlay on the HiRise image of the region S of Victoria Crater:
Click to view attachment


-Mike

SW Passage route overlay onto HiRise image of area S of Victoria Crater:
Click to view attachment

Zoom of SW Passage route overlay onto HiRise image of debris apron section just S of Victoria Crater apron:
Click to view attachment

-Mike

jaredGalen's initial algorithm result matches nicely with initial sections (at least through the worst of the debris field) of the SE Direct route!
(jaredGalen's route in yellow)
Click to view attachment

Nice!

-Mike

Zoom of the Victoria Crater debris field traverse in the SW Passage route, 50 cm/m resolution.
(The worst part of the whole route)
Click to view attachment

Note that the S end of the passage has a darker zone that could be a small dust trap. Switching to the rock pavement area immediately to the E 30% of the way though the "180 S-heading zone" might be a better move.

The entire SW passage route overlaid on the HiRise image of the southern section of Victoria Crater at 12.5% resolution can be downloaded here (30 Mb TIFF file): http://www.speedyshare.com/982913244.html

-Mike

Isn't it odd, the way this exercise has evolved. The 'safest' paths have turned out to be those that stay upon sand, and avoid exposed bedrock. Yet I would think that the areas of greatest interest to mars geologists would be the exposed bedrock. I suppose it follows that only the biggest (most dangerous and red) ripples excavate deeply enough to expose the bedrock - Big Surprise . Yet the bedrock itself is scientifically important and also makes a fine highway. It's only the ripple crests to the east and west that are hazardous.
What to do?
It's starting to look like an argument is imminent such as: "What do you want to do? Get to Endeavour or do science?
I wonder who will win?

I'll have a go at changing my scoring to match up with Mike's scoring-by-color with regards to traverse time.

As a quick thing I tried using non-square grids to to break the space up, instead of grid squares of 5x5 pixels I tried 3x9 to see what would happen.

The result was surprising, in a good way. Bit rough though. It really is just a matter of getting the scoring mechanism right I think.

Now we're about to get going, and after posting a section in another thread, I thought it would be of interest to post the section of my latest terrain map overlaid onto the HiRISE image for the land that we are about to traverse. The colour overlay is now at 4m/pixel resolution, which is comparable to the larger ripple size.



James

I'd think the scoring you really want is of the form a*bad + b*medium + c*good, where the result should be a time. (It's an estimate of the time to cross the square). If you allow diagonal paths, then multiply by square root of 2 for those. If you've got actual drive times across other squares, then a least-squares fit should easily give estimates for a, b, and c. (And I think you'd want to stick with square squares -- the smaller the better.)

With A* you need to make an estimate from any given square to the destination. What are you using for the estimator? If the side of a square is length s and the distance from a given square to the target is d then I'd expect d*c/s for the estimate. (Note that if you don't allow diagonal paths, then d is the "Manhattan distance" not the Euclidean distance.)

--Greg

Hi Greg,
Thanks for the advice. I've fiddled around with different estimators. In the current implementation it is Euclidean distance I think. I'm not 100% sure.
I'll give more details when I get back home and double check what I did.

I'm using the Euclidean distance as the estimator right now.
I changed the function to be 3*bad+2*medium+good just to see and used a grid square of 5x5 and got the following result.
I'll play a bit more with it tonight.

We have to be careful with this, part of this effect might be caused by the fact that analyze methods quite often tend to get confused by bedrock and tend to give it a wrong scoring. That's why 'eyeballing' the route remains very very important...



Agree, which once again illustrates the fact that terrain-scoring also depends on driving-direction, in one location you might have 'flat' terrain in one direction and 'rough' terrain when driving in an other direction.



Getting to Endeavour is the long-term goal, doing science is the day to day business, I don't think there is that much of a conflict, but in the present discussions I'm indeed missing a bit of the 'scientist view', what are we seeing in the HiRISE images that 'looks interesting' , can we name a number of positions which might be worthwhile to visit? Presently all suggested routes are more or less traveling directly towards Endeavour but we might have to include a number of 'waypoints' on the way.

"Talking code" you might even have to give each potential science-target a certain 'score', and then re-design your route-finding process to get the highest score on science targets while still keeping the lowest score on terrain-grade...

Another thought on the estimator (especially if we want to use least-squares later) is we really only have two independent variables, not three. That is, if we know how much bad and how much medium there is, then we already know how much good there is. So a model more like a*bad + b*medium + c is probably a bit cleaner. In fact, since all "bad" terrain is at least as bad as medium terrain, something like a*bad + b(bad + medium) + c is even cleaner, in the sense that we're measuring the incremental costs.

By the way, for estimating these things, given that we do have these maps for the terrain already crossed, how hard is is to measure the actual times? That is, if we know the rover crossed (say) 50 squares in a day, and we know what percentage (of ALL those squares) was good, medium, and bad, then we have something we can work with. That is, if we could get a spreadsheet with data like this

.5 .4 .1 50
.4 .4 .2 10

Meaning "on 50% good, 40% medium, and 10% bad, we covered 50 squares, but on 40% good, 40% medium, and 20% bad, we only covered 10". Obviously you'd need to only include days that were driving days, but I'd bet someone could come up with that info.

Anyway, from that spreadsheet, a number of us could compute the three constants for you.

--Greg

I understand that the near-term science plan includes a long delayed "cobble campaign"; the cobbles in question are just below HiRISE resolution though so pancam/navcam will be the prime "seekers" for that. Hence, progress to Endeavour may not be as swift initially as some member here might like :-)

Airbag

HiRes STDEV analyzes of the area SE of Victoria based on a SE driving direction.

E-Corridor and SE-direct routes are plotted in this image.

Click to view attachment

HiRes STDEV analyzes of the area East of Victoria, based on an easterly driving direction. Proposed East-corridor route is plotted in this image.

Click to view attachment

Mike, I should say that originally I was quite skeptical on both of these easterly routes, based on 'eyeballing' the terrain in IASViewer, but it starts to look like you were correct in your analyzes, it's not as bad as it looks and my own software doesn't show that many 'red spots' compared to the S and SW routes and the ones I find can easily be avoided (there might be a slight mis-alignment in my plotting of the E-corridor route, I had to down-scale it from your overview and it's late at night here, probably you avoided the red spots you now seem to hit but that's peanuts).

The argument against both easterly routes in my opinion is that they 'postpone' the moment oppy hits the 'debris' field, we know we will have to cross some ripples anyway (not matter which route is selected) and the longer this is postponed the more chance there is that one of the wheels fails. I tend to think that crossing the 'bad' spots as soon as possible gives the best chance of being on flat terrain by the time a wheel breaks down...

I didn't get a chance to do anything this evening except for trying to use James Canvin's terrain map briefly. Posted the result below.

Cost function of (bad*bad + 3*medium + good) and grid dimension of 15x20 (not square I know )

-Ed

Science wins! Always does.

Nice work Mike. You have done some tremendous work in narrowing down the choice of routes. Once we get to this point, it is here is where 'eye balling the route' pays off.
However, if I may be able to express an opinion, I think a better refinement of this route is to trend more SW from the N end of your proposed route. This will put us are directly North of the pavement just W of the marked route.

This will give a nice bedrock highway to drive on, as well as an opportunity for science on any rocks or cobbles that we should happen upon.

Now everyone can play "Choose your own path"

I've put together coordinated terrain models in a Powerpoint presentation (both as .ppt 97-2003 and .pptx 2007 files).
I've also included little scale 50 m boxes drawn to cut/copy/paste to your hearts delight onto your favorite terrain model. Then group/copy/paste onto all the other models and the HiRise image as well.

Easy step-by-step instructions on Slide 2.
Scoring function table is included (Slide 10).

Powerpoint 97 (.ppt 25.7 Mb): http://www.speedyshare.com/371972901.html
Powerpoint 2007 (.pptx 25.2 Mb): http://www.speedyshare.com/666678727.html

Y'all have fun!

-Mike

(BTW: I'm really lovin' that cute little 50 m crater. It makes a great centerpoint for coordinating the images, too!)

Don't forget, JM, I was her first love! But I'm not the jealous type where craters are concerned.

The important thing is: Now the whole family can play along with the rocket scientists!
(We'll never know how many marriages you saved today, Mike.)

Regarding scientific 'points of interest', many cobbles of interest may be too small to resolve in HiRISE, but others can be detected: i.e.
1) Bigger cobbles - boulders, really.
2) Rubble fields left from the secondary impacts of local ejecta. (Some were seen on the trip south to Victoria.)
3) Areas of bedrock that are uplifted or undermined to expose fractured edges. (This often occurs around small craters.)
4) Any other abrupt visible transitions in the terrain that may reflect underlying geological discontinuities.

I expect that a spirit of compromise will resolve any dilemmas between geologists and NASCAR drivers.