New Software Stops Mars Rover Confusion

MattSparkes writes "The Mars rover Spirit used to get quite confused when it came upon a rock. Because it could only plan routes of a metre or two it couldn't understand how to navigate around large objects, and frequently used to rock back and forth for hours trying to figure it out. NASA have written new software called D* for the rover Opportunity, which should allow it to autonomously plan routes up to 50 metres long. The new software still won't be able to avoid sand-traps, though."

Comments

The new software

[Timesprout]

actually controls the rail gun which will be used to 'eliminate' obstacles

Based on A*?

[benhocking]

I'm guessing the name is meant to suggest similarities to A*, but you think they'd mention that in the article.

Re:Based on A*?

[Xerotope]

It is based on A*, in fact it stands for "Dynamic A*".

It's designed for efficient re-planning as costs change due to information collected as the robot moves. It leverages the fact that cost updates occur close to the vehicle, so it's really only necessary to replan "locally" back to the A* path.

That's a pretty dumbed down explanation. The original paper describing D* is here.

The actual variant being used by NASA is called "Field D*", and is able to interpolate costs and cross graph states in an arbitrary fasion (not just 8-connected).

Re:Based on A*?

[Xerotope]

P.S. The asterisk is because the algorithm is on steroids.

Re:Based on A*?

[SnowZero]

It amazes me how much people have picked up Field D*, given that it drops the optimality associated with A*/D*. Field D* tends to return shorter paths, but it is not guaranteed to do so. Since those were the exact reasons that groups like NASA would not touch randomized planners, I find that a little odd. I guess its the nice even upgrade path of A*->D*->Field D*. At any rate, having NASA pick up any recent work on autonomy is a success, given their conservative nature.

I remember an Air Force person once saying they would never fund any research using any randomized algorithms; The funny thing is I managed to make a version of the randomized RRT planner the primary route planner for a UAV research project. Grids simply break down as soon as you add any sort of additional dimensions to the problem, and randomized approaches are perfect for 3D worlds and/or kinematic constraints. Personally I am a bit biased though, as I am a big proponent or randomized RRT/PRM based methods, even in low dimensions.

Now if only game programmers would notice that there's been some advances since A*...

Re:Based on A*?

[Anonymous Coward]

I've implemented D*, and while more efficient than A* replanning from scratch in terms of heap percolates, the overhead of D* bookkeeping actually made it slower than just rerunning a tuned A* implementation, with the caveat that this was on maps that I generated; I'm sure one can generate a pathological terrain that would erase the difference. The massive reduction in heap percolates is interesting from a computer science perspective, but in my experience, in the real world D* doesn't really give you new capabilities that just rerunning A* couldn't do. Map representation e.g. quadtree has a much more drastic effect on performance.

metres

[lucabrasi999]

You know, NASA sometimes has a hard time figuring out the difference between Meters and Miles. Now, you are asking them to figure out the difference between Metres and Meters.

Re:My orcs could find their way around rocks...

[ajlitt]

The Warcraft engine knows the dimensions of the rock... It's responsible for rendering it. The rover, however, knows only what it can see.

Re:Come on guys! Its a joke.

[drinkypoo]

The slashdot moderation system is broken and penalizes humor in spite of the fact that the readership overwhelmingly supports it. Thus some people moderate using some other positive mod than funny, since funny does not give karma, but being modded funny and then being modded negatively does TAKE karma. HTH, HAND.

Re:This is pretty impressive....

[Iron Condor]

but I have to wonder why they didn't send it up there with the ability to plane long and short treks?

Because they were originally intended to last for 90 days. There were no "long treks" planned. People assumed that maybe they'd survive a teensy bit beyond the 90 day mark and there was pretty wild celebration (for a bunch of nerds) at the 100-day mark because people thought it was really cool. Now, a thousand+ days later, these little guys are still going strong.

This kind of engineering quality is the reason why JPL is the only organization on the planet that has ever sent enything past Mars orbit. They're considerably more expensive as just farming out your hardware to Lockheed (ahem), but instead of crashing into things they actually land and work properly.

Re:My orcs could find their way around rocks...

[Volante3192]

> Look L

To your left you see a sharp precipice going nearly straight down. Sticking out of the cliff wall are thorny bushes.

> Look R

To your right you see an overgrown thicket, filled with poison ivy, snakes and thorny bushes. The remains of a trail appear to pass through the thicket.

> Climb boulder

You grab hold of the boulder and attempt to pull yourself up, but lacking a firm grip, you slip and hit the ground with your butt.

God this is painful

[Cally]

...painful to read this mish-mash of half-truths and inaccuracies...

Yes, D* has been used "live" for the first time.

However, both rovers received a fresh load of mission s/w a couple of months back which enables a variety of fabulous new functions, including "go and touch" (as opposed to the original "touch and go") - go and touch enables the drive planners to instruct the rovers "move 12.4 metres forwards, turn 30* left, forward 70cm, approach the rock in front of you, deploy the IDD (robot arm holding a variety of instruments, spectrometer, close up camera, the RAT (grinder) and brush, etc; deploy the Mossbauer spectrometer, take reading in situ for 18 hours".

It also enables them to build their own route maps. One problem is that on featureless plains, it needs landmarks to assess how far it's travelled -- thus the newly developed "drunken sailor" manouever, designed to make clearly visible tracks that can be used to triangulate the on-board navcom. thing.

Re:Stupid AI.

[SnowZero]

Ugh, as a robotics person, I find that a bit insulting. NASA is overly conservative, but most game programmers don't even know there are other algorithms than A*. Their books have A*, so that's all you ever see. Most navigation graphs in 3D games aren't even automatically generated. No games use D*, field D*, or randomized roadmaps. Just 1970-80's era hierarchical A*. They'll use something from last year's Siggraph, but its like the last 15 years of robotics research never even happened.

Re:Been golfing for years...

[tbone1]

Try putting down your beer first. It did wonders for my driving.

And remember, kids, don't drink and drive. Use a seven iron.

Thank you: Why can't New Scientist do this?

[GuyMannDude]

Thank you for letting us know and even providing a link to the tech report.

Here's one that that really bugs me about online news articles: they rarely take advantage of the medium! Why the hell couldn't New Scientist provide a link to this paper? As the parent mentioned, the very least they could have done would be to mention that it was related to A*. Yes, I realize that the "average reader" (whatever that means) may not want to know such details, but why couldn't they include a simple "(details...)" link right next to the mention of D*? An interested reader could click on the "details" link and expanded text would create a brand-new paragraph describing more details of the algorithm and providing a link to the tech report. Click again, and the detail paragraph collapses and you go back to reading the basic-version of the story. Simple!

These publishers haven't grasped the power of the new media. For them, online articles simply mean that it's faster, easier, and cheaper to publish stories. Basically, they embrace web publishing for their own selfish reasons. With just a modicum of thought, they could make their products much more valuable to the consumer. But I suppose that would require them to give a damn about their work.

GMD

Re:Thank you: Why can't New Scientist do this?

[radtea]

Here's one that that really bugs me about online news articles: they rarely take advantage of the medium! Why the hell couldn't New Scientist provide a link to this paper?

Because science journalists and editors know nothing about the fields they report on, and frequently seem actively hostile to the facts in favour of some made-up, mythological story.

Some years ago a colleague at the university where I was a post-doc came into the lab and said, "Today the science section of the LA Times has five stories about stuff that I am either personally familiar with or have actually worked on. Four of them are all but unrecognizable. The fifth is full of things that are not true."

In my subsequent experience as a scientist I have found this to be pretty much par for the course for science journalism. I don't actually know if reporters are as ignorant as they appear, but by the time the edited work gets to the reading public it is almost always spun in such a way as to be misleading or simply wrong.

There seem to be some myths about science that are the bedrock of science reporting, and reporters or editors will distort or simply lie to ensure they reinforce those myths. Some of them are:

1) Science is mysterious and full of contradictions (see yesterdays "hot ice" story)

2) There is no point in anyone trying to understand science, it is beyond you (thus the lack of useful links in stories)

3) Scientists are either put on a pedestal or dragged through the mud. They are never treated as merely ordinary people doing a job or following a vocation.

4) The "story" is more important than the facts.

There are probably a lot more, but basically, science journalism will never be worth anything until it starts actually reporting on science rather than wasting time promulgating editorial myths.