Slashdot Mirror
Stanley and the Conquest of the DARPA Challenge
geekboy_x writes "Wired has a great in-depth piece on the Stanford team that won the $2 million DARPA prize. If you remember last year's disaster - with most vehicles falling off the road in the first kilometer or so - this victory becomes all the more amazing. The fact that the Stanford team used a 'tailgating' strategy is the best surprise in the article."
Also interesting to note is the fact that the major leaders of the Stanford team came from the Carnegie Mellon AI department 2-3 years ago.
http://www.asti-usa.com
In order to run, one must first learn to walk...
FTA: "He liked to point out that planes had been flying themselves since the 1970s. The public was clearly willing to accept being flown by autopilot, but nobody had tried the same on the ground."
Just give us our flying cars then already, damnit!
These are the first real steps towards completely autonomous vehicles that have any sense about them. You're not going to see these things out on roads like we have today for a long time, if ever, because of how unpredictable the real world is. However, imagine if you build roads that are only used by autonomous vehicles. It could be similar to an airplane - when you reach altitude, you program your heading and let it go at it, but when you're close to your destination, off it goes and you're back in full control. That, in my opinion, is where this technology is eventually going to go.
From TFA on 7 ways cars are already robots:
"4. Lane-Departure Prevention
Nissan has a prototype that uses cameras and software to detect white lines and reflective markers. If the system determines the vehicle is drifting, it will steer the car back into the proper lane."
I've driven enough roads under construction that I would be seriously afraid that my car would steer me into oncoming traffic because road workers haven't bothered to paint over lines that were previously there.
Personally, I'd be interested in how these vehicles do:
1. On regular highways.
2. At speeds other than the 5 to 25 MPH tested.
I realize they're not built for that. I would just like to see how they do applying what they "learned" in the desert to real traffic situations.
The teams did well this year, but what disappoints me is that this year, many of the teams had relied entirely on laser range finders and GPS to navigate the course.
There was one entry, a motorcycle, which still ran completely on a vision system (cameras instead of sensors). Unfortunately, it did not do too well.
While the military can still use technology developed by the teams that completed the DARPA Grand Challenge, I think they could benefit even more from a vision system capable of doing the same thing. What use is a robot that can navigate a desert if it can't actually see anything?
... is that the CMU team relied heavily on extensive pre-analysis of the environment, and failed (at least in the sense that it didn't come in first). Stanford instead relied on a probability analysis of the incoming data, along with multiple technologies for different goals (lasers for short range data, video for long range data).
It seems that the DARPA grand challenge not only showed off the first realistically autonomous vehicles, but also laid to rest the idea that expert systems were the way forward. The way forward instead is self-teaching computers. Hooray for self-teaching AI overlords!
Those who can, do. Those who can't, sue.
I still think it will be a long time before we trust a computer to drive us around. Intersting that it used a 'tailgating' strategy...what happens if all the cars around it are also doing the same!
I was never that impressed with the CMU approach. All that manual preplanning was an obvious dead end. And the giant mechanically stablized gimbal was just too clunky. It didn't help them in 2004, when they hit an obstacle placed by DARPA, and it didn't help them in 2005, when DARPA moved the racecourse from California to Nevada to prevent preplanning. The Air Force colonel in charge for 2005 said preplanning wouldn't work, and he meant it.
Computer vision of the natural world is finally about to take off, after three decades of frustration. It's probably possible to do much of the early vision processing in a current-generation GPU, which may make it affordable. Look for new apps that connect to cameras and pick out items of interest. Read that paper linked above.
Basically, after two years of work they have it going at 45MPH over rough uncharted terrain.
That is pretty darn good.
The best thing about it is, the system is capable of second guessing itself, that right there is the fundamental step that lead to success.
The flip side of all of this is, it is based on probability, and while in a desert the opportunities for accidents may be minimized, I wonder how well it will deal with unexpected random events, such as people who don't put on their turn signal when changing lanes.
CPU power and other hardware can always be scaled up to deal with increase speeds (indeed a major topic that the article deals with), the question is can the algorithms deal with truly unexpected input?
Of course one solution to this is to have all cars automated, then you do not have problems with fools not using their turn signal, as the cars would just wirelessly inform each other.
Bleck, then again, I have not yet seen a perfectly working wireless network stack, hopefully who ever they get to program the cars would be of a higher caliber than the idiots who program PCs and wireless routers/switches.
Need help treating your acne? Come here!
From Wired: The resulting liability issues are a major hurdle. If a robotically driven car gets in an accident, who is to blame? If a software bug causes a car to swerve off the road, should the programmer be sued, or the manufacturer? Or is the accident victim at fault for accepting the driving decisions of the onboard computer? Would Ford or GM be to blame for selling a "faulty" product, even if, in the larger view, that product reduced traffic deaths by tens of thousands?
It figures. A technological advance that would cut the number of traffic deaths by about 95% by taking drunks and maniacs out from behind the wheel, and preventing 93 year-old men with dementia from killing people, will be bogged down by liability issues should the robot kill someone. C'mon people! Even the best system will not prevent a fluke accident or yes, even a bit of bad code, from killing someone, but weight that against the number of road-rage infested idiots on the road now, driving at 100+ mph, swerving in and out of traffic, and I think libility needs to be the furthest thing from anyone's mind.
Just don't let Microsoft write the software.
GetOuttaMySpace - The Anti-Social Network
was when Thun explained how the vehicle was taught to drive by following a human driver and adapting its algorithms according to his behavior, gaining much better results than "force feeding" massive amounts of data artificially.
This has immediate implications not only for robotic cars - what if we took a human and strapped some positional sensors, voice recording, etc. and made a humanoid robot follow him throughout the day?
I mean how varied are our lives after all? Given the right processing power and sensors, the results could be interesting...
Again, a great achievement for a 'bottom up' approach to artificial intelligence
The fact that the Stanford team used a 'tailgating' strategy is the best surprise in the article.
Not anymore.
At the risk of being modded offtopic, I have to disagree -- a programming language is nothing more than a way of expressing an algorithm. While there is some degree of interest in the degree to which a language allows one to express alogrithms clearly, allows for easy separation of areas of concern, etc., it's ultimately the algorithms that really matter -- the programming language is simply a way of expressing them.
OTOH, it would be interesting to hear more about the algorithms and how they were expressed -- including the programming language(s) involved, to the extent that it/they had a real effect. And make no mistake about it, programming languages do affect the algorithms used to a degree, if for no other reason than some languages make particular kinds of algorithms easier to express than others.
If you care about the algorithms involved, you might want to look into the book on probabalistic robotics by Thrun (and others). Note that this isn't specifically abou the Stanley project, but about the field of work, not simply a description of Stanley or something like that.
The universe is a figment of its own imagination.
basically due to whatever circumstances (width of the road, start order etc) someone has to be in front and someone has to be behind - the fact that the Stanford vehicle was following another entry had nothing to do with how it was successful, in fact one could argue it put the vehicle in some danger if the lead vehicle messed up, rolled, crashed etc. It later passed the said vehicle to go on to the win - The article makes no mention of a "Tailgating Strategy" it does say that it was tailgating another vehicle for a bit before it passed it - not sure how this is any more strategic then when I drive to work in the morning - how about this winning strategy "Don't hit the car in front of you". Don't know why this bugged me so much, its actually a good read, I just don't know why this non-existent "Fact" was so prominent in the lead in. Sorry.. not enough coffee today....
Right now I think that it may have some issues regarding lane changing, and collision avoidance, but I think that, in the long run, those problems are a lot more solvable than, "Woops there's a giant ditch in the way, what do I do?".
Collision avoidance is pretty simple...Just stay X distance away from everybody around you, and computers have a huge advantage in that sort of test because, a) they don't get bored and stop paying attention, and b) they have very quick reaction time. It's probably easier to teach it to avoid someone merging into its lane than it is to teach it how to tell what a turn signal means.
Still a long way to go, but this is a big step.
ad logicam Claiming a proposition is false because it was presented as the conclusion of a fallacious argument.
Now all we need is a superstrong protective layer, a pursuit mode, and cool red lights on the front!
Accident opportunities in the desert are minimized? "The desert" isn't just rolling sand dunes, or a dirt road through scrubby brush. It's rocky, angled, steep, unpredictable terrain. Dealing with something as easily identifiable and predictable as road traffic (cars never leap into the air, or instantly hop sideways 6 feet) is a snap compared to off-road driving. What do you do that's so complicated when you see a car changing lanes suddenly, putting it too close to you? Apply brakes? Change lanes? A computer can do those things pretty easily-- probably safer and more attentively than a person.
If a job's not worth doing, it's not worth doing right.
That's actually not true. There was no "tailgating". During the Grand Challenge, no vehicle was allowed to approach another while both vehicles were active. DARPA had the ability to remotely pause any vehicle. When vehicles got anywhere near each other, the trailing vehicle was paused to maintain separation. If the trailing vehicle was clearly faster, a pass was scheduled. All passing took place with one vehicle stationary and at a wide place in the road. Wired has this wrong.
As a participant of another DARPA team (Cornell -- our site is down), I am skeptical as to whether the winners of the challenge would be able to drive in a real world environment. In many ways the Grand Challenge was a toy problem, but this is not usually emphasized because they want to make it seem more dramatic.
First of all, no other moving objects on the course. When a vehicle was about to pass another, the one in front was paused so that the passing vehicle could overtake it. At no time did the vehicles have to deal with changing conditions.
Secondly, to my knowledge, there were no obstacles (which were promised) on the course. If someone knows differently, I'd like to hear about it. So we don't know to what extent obstacle avoidance is effective on those vehicles.
Thirdly, daylight and clear weather is one thing, but nighttime, rain, snow, etc. would significantly degrade the data.
Essentially the problem that the current vehicles solved was this:
Given a set of waypoints and a "corridor" outside which you will never have to go (so far the problem can be solved only by 10cm-accuracy DGPS), use your other sensors to avoid obstacles by moving left or right within the corridor.
Not very much like real world driving at all. And I'm not saying Stanford, CMU and the others didn't accomplish something big -- I'm just saying it's not what the Wired piece makes it out to be.
The strategy is to work on freeways first: 2010-2020. Freeways are much more controlled than cities. Cities, much harder, will come later. 2020-2030. A city should be a humming hive of sensors and intelligences, by that point. (links)
One result from the second Grand Challenge that lots of people harped about was the fact that Stanley, the winning (and hence, fastest) entry, completed the course with an average speed of only about 19 mph. "19 mph?" quoted some of the the nay-sayers, "we're supposed to get excited about that?"
One thing that TFA points out, which wasn't mentioned many other places, was that the course rules stated a maximum vehicle velocity of 25 mph. Ideally, then, the fastest possible average speed for any entrant would likewise have been 25 mph. Stanley, at times, wanted and could have gone faster than that, and held back due to the rule-imposed speed limit. In that context, 19 mph is actually quite good, considering the terrain would have forced it to slow down over bumps and turns.
The article presents the history of Stanley is presented as a series of intellectual breakthroughs that I can understand, just like a lot of the pop science I read when I was a kid (and continue to read). I'm pretty sure each of these breakthroughs (such as learning from humans and assessing sensor data critically) are ideas that have been around in AI for a long time. The true story of Stanley is no doubt just as dramatic but much harder for a layperson to appreciate.
I think the first practical non-military application of autonomous cars will involve a ton of infrastructure. It won't be achieved solely by making the cars as advanced as possible, but by providing a lot of supplemental data from an array of stationary sensors (and processors) installed by a city or theme park that wants to be the first to have autonomous cars.
Eventually human drivers will be banned, and the cars will communicate and cooperate with each other (much better than human drivers!). Traffic engineers will maneuver cars manually in rare instances, and computer-controlled cars will give them a wide berth. Safety will be improved, but so will traffic efficiency. Cars will become less personal, hence smaller and more efficient; crashes will become rarer and safer, hence cars will be smaller; computers will be better drivers, so cars will run faster and closer together. We can look forward to a period of ten to thirty years in which freeways don't get any wider.
Continuing my utopian fantasy, if cars become autonomous and have less personal significance, many city dwellers will choose to use taxi services instead of owning their own cars. That means that most of the cars on the road at a given time can have a sensible capacity, rather than the maximum capacity the owner imagines that he or she might need. Per-capita energy use for personal transportation in the U.S. will drop to a fraction of the current level.
It will happen someday, but maybe not in the next hundred years, depending on how stubborn we are. It would certainly be easier and more rewarding to start with helpful, high-infrastructure environments, but the military has such a massive capacity for funding research that we will probably solve the harder problem of hostile environments first. I.e., we'll have autonomous robot sharks with frickin' laser beams on their heads long before we have Johnny Cab.
Its lasers are constantly teaching its video cameras how to identify drivable terrain, and it knows that it could accelerate more.
Maybe one day it can use its lasers to eliminate obstacles, creating drivable terrain and enabling to accelerate more.
He who knows best knows how little he knows. - Thomas Jefferson
Try the Scientific American article on the DARPA challenge: Innovations from a Robot Rally
It covers all the teams a bit and talks about some of the innovations that were used by the competing teams. It is a little light but worth a minute or your time.
Architectural plans are like computer source code with a couple of differences: You only compile once.
Unlikely, as they would be too easy to intercept and destroy. What they really want to use them for is logistics. So much of the military's manpower is concentrated on logistics, that's where the real potential for saving money and saving lives is. What they really want is a convoy of trucks that can be programmed to go from Supply Base A to Tactical Operations Center B, then proceed to Staging Area C, without having to put human drivers in the vehicles.
If you don't know where you are going, you will wind up somewhere else.
It was not programmed to tail-gate, it just happened to be so good at what it was doing that it caught up to the CMU vehicle and eventually passed it.
And it was using laser sensors and video cameras to visualize it's enviroment. It's a pretty remarkable system. Makes me wish I'd stayed in school for A.I. programming.
Coding reports in a factory cannot be as much fun as coding a toureg to drive through the desert.
Sean D.
"Hmm. I am to metaphor cheese as metaphor cheese is to transitive verb crackers!"
Yeah, because things sponsored by the Department of Defense never have any value outside of wars. Like that ARPANET thing.
Every deer, cow, buffalo, etc... has a GPS unit strapped to its back.
Would a robot controlled car try to straddle a squirrel running across the road like I do?
Yeah, but only to get a better shot with its mounted machine gun.
"I am the king of the Romans, and am superior to rules of grammar!"
-Sigismund, Holy Roman Emperor (1368-1437)
What do you do when someone jams their way over into your lane, pushing you out, and you are already up against the edge? Under what conditions do you accelerate, decelerate?
First you guess at the path of the other vehicle relative to yours for the next few seconds based on your recent measurements of its heading, speed, and size. Then you compare the outcomes of the fairly limited number of control options you have: slow straight, slow right, slow left, fast straight, fast right, fast left. Plug your current speed and approximate mass along with the predicated path of the other vehicle into each of the 6 scenarios and pick the best outcome in terms of energy remaining at time of impact (if any). Admittedly there are more than 6 options for course corrections, but you can make a first choice given the vehicle's width, mass, speed, heading, maximum steering angle and maximum acceleration/deceleration, and then calculate the exact control sequence to produce a course along the requried path while minimizing passenger discomfort. It's really not that complicated (and I actually have written obstacle avoidance algroithms for moving machines) and the computer has a *huge* advantage in quickly measuring and calculating the path of nearby objects.
On ice, there is suddenly a collision 50ft ahead, do you try to steer around it, slam on the breaks, coast to a stop? If you have to change lanes, to which lane?
If there's suddenly an obstacle 50 ft ahead of you you start braking immediately. If you slip, you reduce your breaking to stop the slipping and re-calculate your stopping distance given the new braking power and your approximate mass. If the remaining distance is insufficient, you compare the outcomes of moving left, continuing straight and moving right and choose the best outcome in terms of energy remaining at time of impact (if any). It's also worth noting that emergency steering is rarely if ever more effective than braking if you're really on ice, as it's still a huge change in momentum, and that a straight-on impact is more survivable than a sideways impact, all else being equal. And again, the computer has a *huge* advantage in determing your stopping distance and measuring or calculating your maximum non-slipping braking power and maximum non-slipping steering angle.
Following the road (or in the general case, picking a path) is much more complicated than simple physics exercises like you've described. What part of the situations you described do you see as challenging for a computer?
Wrong, you choose the best outcome based upon how it is going to effect others.
If the choice is either a near guaranteed death collision with the car in front, or running over onto a sidewalk and hitting a child, but with an almost guarantee that the passengers in the vehicle live, which do you choose?
What if the child on the sidewalk is a teenager, and there is a baby in the vehicle?
In a perfectly simulated world in which detailed information about all particles is known with absolute certainty, then yes, mathematics works out perfectly.
You throw stupid humans into the mix though, and things get a bit nuts.
Aside from all of this, humans have instincts; they can react really quickly to insanely complicated scenarios. Heck just think of the CPU power that was needed to keep a car on the road, how many tens of millions, if not tens of billions, of operations needed to be performed per second.
All to accomplish a task that the human mind does with ease.
I have seen computer physics simulations, walking robots are a great example, I believe Honda recently got their's to run. As slow as human babies are to develop, they are apparently easier to program! Admittedly, the major hurdle with walking robots was the development of the appropriate mathematics to solve the problem, and developing a truer understanding of the problem itself, once those were conquered, progress has been made quite steadily.
Also, I might add, physics simulations are really slow. And you would also need a computer that could react to events of such complexity, at incredible speeds. Obviously real time systems are capable of even faster reaction times than this, but the overall complexity of coordinating a real time system of this magnitude, this is not just some real time simulation running inside of Pefect Sphere physics land, the algorithms would have to handle the fact that their data is noisy.
You realize that imaging data collecting when the roads are icy would have problems with glare? Even more so, what about black ice? Where is the black ice at exactly? An experienced driver can feel it beneath their wheels, how about a computer?
When it is foggy out, data is even more sketchy. Heavy rain, humidity, wind, can disrupt the accuracy of sensor data. The fact that your data is being collected from an analog source (the real world), and then put into digital form, means that there is already some loss inherit in it, how much data loss can you tolerate?
Now run your physics simulation on that car skidding on the ice. How well does your simulator handle data of an iffy nature?
The human brain is designed to deal with incomplete, fragmented data, can your simulator handle it as well?
Can it handle it well enough to answer moral dilemas with enough certainty to satify the sue happy public?
If you say yes to all of this, now make such a complex system nearly bug proof. If it crashes, or has even a performance hiccup, even once, lives are going to be lost.
This is not a problem of the physics being done, we all know that the physics can be done, this is a problem of getting the physics done with corrupt tangled data.
Need help treating your acne? Come here!
Then let the robots download maps, etc. autonomously (automatically), and as needed, during the race.
And if route planning is so easy, why did CMU need "12 analysts in a tent beside the start line scrutinize the terrain" which "identified boulders, fence posts, and ditches so that the two vehicles would not have to wonder whether a fence was a fence".
That's not "autonomy", it's glorified R/C.