Slashdot Mirror
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."
You would be correct. D* stands for "Dynamic A*"
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).
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.
We're all born with nothing.
If you die in debt, you're ahead.
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.
"None are more hopelessly enslaved than those who falsely believe they are free." -- Goethe
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.
The rovers can be manually commanded to perform specific driving maneuvers (and the beginning of each drive usually is done by manual planning). It's not a problem.
Stop it, stop it, it's fine. I will *destroy* you.
Originally, they had teams working Martian days round-the-clock. But they they stopped doing that years ago now as they don't have the cash or the staff to do it any more. Months of working out-of-synch with Earth days kinda screwed with people's heads too. Even when they were doing it, they weren't in constant contact. Did you think Nasa's Deep Space Network has one of its precious, in-demand dishes pointing at Mars 24/7 in case one of the rovers wants to call home? Did you think the survey satellites round mars position themselves and their antennas to be ever-ready to relay messages when the rovers are on the far side of Mars as seen from Earth? Well, they don't. All that stuff has plenty of other work to be doing. Resources (people, money, comms, power, appropriate alignments...) are all much more scarce than you seem to think. They plan a day, upload the plan, then wait a day to see what happened. As Earth and Mars days aren't in synch, sometimes the plans are for a couple of Martian days.
Chernobyl 'not a wildlife haven' - BBC News
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*...