Endeavour Drive - Drivability analysis Options

[Geert]

Note 2: Taking what Geert said about time taken to cover terrain, this seems like an important point. Geert, what did you use to estimate how long it would take to travel over a given terrain type? Function based on terrain type could be easily built into this search approach to change cost to couple terrain type and traverse time.

Terrain analysis is done by standard deviation, basically the software calculates the standard deviation in the brightness of all pixels along the driving vector (distance can be set by user), this standard deviation I use as a indication of terrain 'roughness' and thus as a method to estimate maximum possible driving speed in a certain direction.



Above is the 'general options' dialog of the software, it allows the user to define certain colors to a certain stdev value, this is where the red/blue/green fields originate from (basically you can set any color for any value of stdev). I define the terrain as 'very rough', 'rough', 'moderate', 'smooth', and 'very smooth' with each of them a maximum value for stdev, all can be set by the user so you can experiment which value's will give the best terrain picture. Apart from this the resolution of the resulting analysis can be set, as well as the sampling rate and the spacing between the sampling points. Basically I try to make the whole calculation as flexible as possible, with as much as possible all settings configurable by the user, so you can 'play' with the thing to find the best settings.



The second dialog defines the route-finding options. Here you can define the distance in meters per sol that the rover can travel in each type of terrain, thus the values for 'very rough' to 'very smooth' terrain you defined earlier are now translated into maximum distances traveled per sol. Once again I leave it up to the user to set these values, so for instance if we lose one wheel, values can be changed correspondingly and the software will still function. Other values which can be set define the maximum number of cycles the software will calculate, the number of 'rovers' which start from each new position, and the maximum number of rovers allowed to continue each cycle. Once again, it's all up to the user, allowing more 'rovers' to search for a route and/or more processing cycles will result in higher accuracy but longer calculation time (on my very average laptop, the most labour-intensive calculations can take up to 15 minutes with average settings). Finally, it is important to correctly set the scale of the image (meters per pixel) in this dialog.



After loading an image (unfortunately the software can not yet handle jp2 images, so you need to convert to jpg/tif/png etc first) and setting above value's you can manually enter waypoints by checking the green cross button and clicking on the image, each time you click a new waypoint is entered and a yellow line is displayed connecting your waypoints and defining your manual route. The number of waypoints is unlimited. You 'close' the route by pressing the red cross button, where after the route is analyzed and total distance, average and maximum stdev value, and estimated travel duration are displayed. By clicking on the 'autodrive' button (highlighted in above screendump) you start the computer-calculation. Presently the software will ignore all manual waypoints apart from the first and last waypoint, so it will calculate the fastest and smoothest route between departure and destination. This route will then also be shown on the image, and distance etc will be displayed. There are a lot more possible tools and calculations, but this is the very basic of the thing.

Once again, it is still far from perfect, whenever I find the time I continue work on this but my time is very limited so quite often I have to trade functionality of the software against available coding-time... Don't expect a fully functional professional piece of software for this isn't it, it's a temperamental piece of software written primarily to get results, I don't have the time at hand to make it 'fool-prove' and 'flashy' On starting up, the software will automatically check for the latest version, and download updates if and when available.

For anyone interested: a free download and installation is via this link You will need to load the url in IE7+ for the installation to work.

[Geert]

I see this is the Von Neumann Probe method! My experience of programming route-finding like this is that the ballooning number of potential-routes, which initially look quite frightening, are quickly cullable - and that breaking down long routes into a sequence of shorter steps (such as a MER would find with science stops at likely targets) eases the time spent on calculation.

Fully agree with you, I don't intend to simply enter Victoria as departure point and Endeavour as destination, not only would this require tremendous files (you will need something like 1 mtr / pixel resolution to get reasonable results) and likewise very long calculations, but it would simply be an unrealistic approach as the true route will also be dictated by science-targets enroute.

Presently I'm working on following items:

1) allowing intermediate waypoints between departure and destination (basically: "find the best route from A to D which passes positions B and C"), this is quite simple and requires only minor changes to the software routines (the 'manual' route can already include an unlimited number of waypoints).

2) allowing other methods of terrain analysis. One method to implement this is simply offering the option to 'switch off' the stdev calculation and let the 'grade' of the terrain (from 'very rough' to 'very smooth') depend completely on either the pixel color or the pixel brightness at the present location. If I do this, the software would be able to run on a pre-processed image from any one of the other methods.

3) defining a geographical overlay of an image, which would allow waypoints and positions to be defined in latitude/longitude coordinates instead of pixel locations, this makes it easier to copy routes to different images/maps/etc.

But once again, my time is very limited so don't expect fast results

[Geert]

You've got sendRover(direction, position)... your stop case is arriving at the destination, at which point you stop all the other recursive calls. You might not be doing this recursively, but that's really a matter of using the OS stack versus using your own data structure of routes.

Nope, the calls do not stop when one or more 'rovers' arrive at the destination, it just continues for a user-defined number of programming cycles. What happens is that each rover which 'arrives' is dumped into a list and "stopped", and only after completing the set number of programming cycles all arrived rovers are questioned and their routes analyzed. This allows for selecting routes on other criteria then 'fastest route' alone. You might wish to set values to maximum or average terrain encountered, etc, etc, so the first rover which arrives might not have traveled along the desired route. Each software rover keeps track of various factors (average stdev value, maximum stdev value, etc) and these can be questioned afterward.

So to sort of adapt what I was saying from the recursive algorithm to your problem of having your existing route-finding program: You already have, for each location, a value that corresponds to how long it takes to traverse. What you need to introduce are functions that modify those values, not new "intelligence" or new algorithmic magic. If you try a more exponential function, you will probably start to see routes that steer around obstacles that were previously traversed.

Fully agree with you. What I have been trying to do is keep as much as possible all these choices to the software user itself, so almost any variable in the whole calculation can be changed by the user. And indeed, changing these variables often completely changes the route which is calculated, trick is in finding the 'correct' values...

With regards to your location-value, note that in fact each vector has a certain 'weight', this is also my problem in incorporating other analyze-methods into the software. In one position you might run in to big problems on a westerly course while running in a southerly course will be okay, so you can't say "this position is okay", you need to say "this position is okay for a southerly course".

The red/blue/green maps are wonderful and extremely important for getting an overview of the terrain but they don't work on the scale of route-finding as they are non directional. In my opinion we should take the following steps:

1) Manually define a number of waypoints and a 'general' route from the various earlier produced colored analysis.
2) Use the various route-finding methods to create a route from one waypoint to the next along the route found under option 1 (Note this is not only software calculations but can just as well include manual analysis of terrain!).
3) Analyze the defined route using various options (total length, estimated duration, terrain encountered, etc).

After step 3, try to think of a different route and repeat steps 1 to 3, until there are various routes, then finally compare all routes found.

Although I enjoy discussing all the software-issues of route-finding, we should not forget to take step 1 first ! As yet there is not much discussion on the 'general route' and I think that should come first before we start to discuss how to get from one waypoint to the next!

Also we need a better method to 'analyze routes', a set of criteria by which we can compare the various route-options, and finally we need some sort of coordinate-system by which we can describe routes ('turn left after the third crater' is a bit vague..). If we all work on the same HiRISE images and on the same scale we could simply use pixel-locations (X,Y) but I think it would be better if we could somehow relate them the 'real' latitude/longitude coordinates or some other type of 'universal' locator-descriptions. Any comment is more then welcome!

All in all I think there is still lots and lots of work to be done, and we must be careful not to get lost along the way...

[Shaka]

All in all I think there is still lots and lots of work to be done,

I hear ya', Geert, and fully agree. Of course, a lot of that work is waiting on the arrival of the HiRISE images (when are they due in again?). Then human eyes are going to have to pore over them at maximum resolution looking for those "waypoints" of scientific interest. I'm willing to do my share, but someone with the smarts and 'heavy iron' is first going to have to convert and subdivide the massive image files into a mosaic of readily handleable jpegs, or whatever, that we can load into Photoshop Elements (sorry! ), and cruise around putting gold, silver or bronze stars on top of large cobbles, clusters of cobbles, fractured bedrock with exposed edges, craters with exposed bedrock, etc. (I'm assuming even Tesh can't spot festoons from orbit )
Lacking other clues at the outset, the most logical order of search would start with grid sections along the SE diagonal connecting Victoria with Endeavour (or that part of the Endeavour rim that is our ultimate destination). Then the searched diagonal would be expanded through adjoining sections to the NE and SW of the diagonal, until an adequate SE corridor to encompass the journey had been searched. That will complete your step 1, and then the area drivability map can be overlaid to cull out points of interest in impassable areas.

It's all good, though I can't guess how long it will take. Still, I'm already wildly impressed with the rate of progress of you and your fellow 'pattern-analysis gurus'.
It is a Grand Odyssey, and I can almost feel the Spirit of Our Exalted Steersman, Paolo, smiling down on us in approval.

[Juramike]

Here is a grayscale differential shift 10E5S terrain model that might be useful for route-algorithm development.

This terrain model is for the region S of Victoria. There is no terrain overlay. The pixel brightness is based solely on predicted "drivability". (Black = good; white = bad). Rock pavement is zeroed out and considered like "parking lot", but the dunes on the pavement are incorporated into the model .


The edge artifacts have been removed and background set to black (so's not to mess up any algorithms and make a "bright wall")

Here are links to larger versions at 12.5% resolution:
As a TIFF file (10 Mb): http://www.speedyshare.com/792752906.html
As a JPEG (4 Mb): http://www.speedyshare.com/262238303.html

Enjoy!

-Mike

[Juramike]

Previously traversed examples of Blue terrain in the green-blue-red color scheme of the differential shift terrain model.
These are drive headings that predominantly run the troughs of the N-S dune crests (half-pipe direction)
This is blue terrain in the half-pipe in dunes.


Also shown is a view perpendicular to the drive direction.

Sol 412 was a record drive in Blue Terrain. Post-Purgatory drives in Blue terrain were much more conservative: Sol 627 is a better example.

-Mike

[Juramike]

Previously traversed examples of Blue terrain in the green-blue-red color scheme of the differential shift terrain model.
These are drive headings that predominantly run the troughs of the N-S dune crests (half-pipe direction)
This is Blue terrain in the half-pipe on rock pavement.


Also shown is a view perpendicular to the drive direction.

(Note rut depth in foreground of Sol 781)

-Mike

[Juramike]

Previously traversed examples of Violet terrain in the green-blue-red color scheme of the differential shift terrain model.
These are drive headings that predominantly run the troughs of the N-S dune crests (half-pipe direction)
This is Violet terrain in the half-pipe in dunes.


Also shown is a view perpendicular to the drive direction.

-Mike

[Juramike]

Previously traversed examples of Violet terrain in the green-blue-red color scheme of the differential shift terrain model.
These are drive headings that predominantly run the troughs of the N-S dune crests (half-pipe direction)
This is Violet terrain in the half-pipe on rock pavement.


Also shown is a view perpendicular to the drive direction.

-Mike

[Juramike]

Previously traversed examples of Red terrain in the green-blue-red color scheme of the differential shift terrain model.
These are drive headings that predominantly run the troughs of the N-S dune crests (half-pipe direction)
This is Red terrain in the half-pipe in the dunes.


A view perpendicular to the drive direction is shown.

-Mike

[Juramike]

Previously traversed example of Red terrain in the green-blue-red color scheme of the differential shift terrain model.
These are drive headings that predominantly run the troughs of the N-S dune crests (half-pipe direction)
This is Red terrain in the half-pipe on rock pavement.


A view perpendicular to the drive direction is shown.

-Mike

[Juramike]

Montage of comparison Navcam views for each terrain type:
Traversing dune direction:


Half-pipe direction in dunes:


Half-pipe on rock pavement:


-Mike

[Juramike]

Taking the data from the selected* indicated drives, here is a list of distances achieved for the drives shown in the historical navcam images in the above posts:


(*I tried to use selected data that was representative of each terrain type. Drives were selected that consistently covered the same terrain type throughout the drive, drives that had distances reported, drives tracks that could be confirmed by navcam images, and drives that seemed "typically long" for that terrain type. Bias is my own.)

My estimates for amount that could be consistently covered per day for each terrain type. (In most cases, this is half the amount covered in the example drives above):

[EDIT 20081017 0904 EDT: Revised estimates see below post]

Scoring functions for each terrain type based on estimated drive speeds. This is the amount of time (in drive*days) that will be required to cover a 50 m distance.

[EDIT 20081017 00904 EDT: Revised scoring function see below post]

I'll be using these scoring function values to compare and evaluate routes.
By multiplying the number of each terrain type/drive direction with the scoring function, it should be possible to estimate the total time required to complete a given route. Low score will be the faster, more efficient route.

-Mike

[Geert]

Taking the data from the selected* indicated drives, here is a list of distances achieved for the drives shown in the historical navcam images in the above posts:

Wonderful job Mike, this will allow us to compare routes and get estimates of driving-times, etc!

So, can I pre-order your book about this research?
Really, a printed copy of all these pages is just what we need next to the computer when studying the HiRISE images.

Although my free time is very limited I have been quite busy these days (or nights, more often) with what amounted to a major re-write of the software toolkit, as mentioned earlier I have been busy to relate all image-data to latitude/longitude coordinate data. All previous analyzes and routes were pixel-related, but as they often are in a different scale, different projection, and/or at a different crop they are hard to compare. By converting all data (pixels) to latitude/longitude coordinates I can now basically compare any analyzes with any other analyzes no matter the scale etc and I can 'stitch' together images, combine them, etc, etc. It's a hell of a job but first results are now starting to look hopeful, as soon as I got more I'll post it.

[Juramike]

Based on some suggestions and to help simplify things, here are revised drive estimate as well as a revised scoring function:

Revised estimated drive distance per terrain type/heading (m/day):


Scoring function (days/50 m box):


(Thank you to all who PM'd me!)

-Mike