Slashdot Mirror
Breeding Race Cars With Genetic Algorithms
smack-pot writes "Wired News has an article about how the Digital Biology Interest Group at University College, London is using genetic algorithms to breed superfast Formula-One race cars. 68 design parameters were configurable in the cars, and the generated designs were tested using the racing simulation software developed by the game developer Electronic Arts. According to the research it is possible to shave off 88/100th of a second per lap by using genetic algorithms to tune the cars. In an industry where a tiny fraction of a second matters, that's significant."
This will EVOLUTIONALIZE racing ;)
It's easier to fight for one's principles than to live up to them.
How will this benefit me, Joe Sixpack?
Here's a good link for people who don't know what genetic algorithms are:
It should be noted that the "research" was done with a video game and no actual tests have been conducted on real cars and situations. This does not mean the techniques cannot be applied in real situations, but just that it has not been done yet.
A blog like any other.
when a driver slams into the wall, will this be a GMO accident?
Does this mean that they will have pedigrees now?
How long then before racecars come with a "pedigree" like a champion racehorse or a Crufts prizewinning pooch?
"And Schumacher rides to victory again in his car 'Victorious Monarch' which of course comes from the Ferrari stable and is the offspring of 'Burning Rubber' and 'Teutonic Speed Demon'"
A little planning goes a long way...
..For example, by:
1. computer-modeling an actual car;
2. Spawn a neat million cars, differing only in their electronics (fuel injection parameters, ABS, traction control,etc.)
3. select for desired caracteristic;
4."mix genetics"
5. respawn.
I guess that if you can access your car's electronics, you can do that yourself, but I think it will void any warranty. BTW, i know that here in Italy some outfits offer on the sly to change the electronic parameters of a car, especially turbo diesel, to increase max power and torque.
"If a boss demands loyalty, give him integrity. But if he demands integrity, give him loyalty." (John Boyd, 1927-1997)
88/100 = 0.88
So it's about one second.
500 lap race = 440s. Not insignificant.
This lot must have come from one of those places where it's still legal to marry your sister...
When I am king, you will be first against the wall.
I did some research and programming in this field over a decade ago. The really frustrating thing about this field is how slow moving it is and how little it is taken seriously.
When you have constructed an environment and electronic "organisms" that can breed within that environment, and then watched the generations gradually improve and adapt to the environment, you get the feeling of a new kind of power that we haven't really tapped yet - evolution.
I think one of the problems is that people don't get what is happening in these types of projects. When I showed people the projects I was working on - even biologists and computer scientists - the first reaction was that what they were seeing was just a simulation - i.e. that I had programmed in the fact that the organisms adapted to the environment. It took a lot of explaining to convince some people that what they were seeing was actual evolution, albeit in digital form.
The fact that this research is just looking at breeding cars which are used in a computer game just demonstrates how slow moving developments in this area are. Evolution could be used to improve many aspects of cars -- their engineering, efficiency, production and even visual design. It will happen one day, but it's taking us a hell of a time to realise that we can exploit the force that produced all the wonderful things we see in nature.
After careful research, I found a visual aid that helps clear up the mystery.
**WARNING** Do not view at work (if you are a mechanic). It's a truckse.cx link.
Show me on the doll where his noodly appendage touched you.
As a member of a raceteam which is about to enter the formula SAE competition. (A global university based competition aimed at building the fastest racecar) I find that 68 parameters are not nearly enough. Modern racecars have that many in the suspension alone. And all those phony calculation with determination of how many seconds are spared cannot be used for anything concrete.
You've never watched a certain M Schumacher, obviously. The guy is a robot.
When I am king, you will be first against the wall.
This means you have to be skeptical with experiments performed just in simulation without testing the same model in reality.
root post is made irrelevant by the math error corrected in the reply.
-Ryan
AUWYHSTOT (Acronyms are Useless When You Have to Spell Them Out Too)
But if you allready have a realistic computer model of the car, using a genetic algorithm would be very cheap. I dont see why you couldnt both get a better driver, and using a GA for the parameter model. After all, the design team probably play around with the parameters manually.
Anyway, tracking the effect of 68 parameters can be very kinda. So I guess thats the reason they went with GA instead of using simulated annealing ( a population of candidate solutions),- a technique better fitted for problems with a low number of parameters (only one candidate solution).
Alternatively, you can get a nitrous oxide kit fitted. BIG power increase for those rare occasions when you need it( zooming away from lights to impress girls )and stock engine for the rest of the time.
They whose government reduces their essential liberties for temporary security, receive neither liberty nor security.
The advantage is not slim in Formula One. They are routinely fighting for single hundredths of a second. Official timing is down to the hundredth and there was actually one race where 3 cars qualified with the same time down to the hundredth.
Revolutions are never about freedom or justice. They're about who's going to be top dog. -- Kilgore Trout
All that aside, do you watch NASCAR much? I'm not what you'd call a NASCAR junkie, but I do watch at least every other race. Tenths of a second in lap times are frequently the determining factor between pole and, say, 10th qualifier. Races are often decided on margins approaching less than one second.
All that said, yes, one bad pit stop can and does ruin a race. So does one unseen oil slick. Kasey Kahne should have won Dover, period. The officials were loathe to call a caution so late in the race, after so many cautions had already been called, and cost Kasey his first win.
Sucks.
And tenths of a second did it.
"BSD: Free as in speech. Linux: Free as in beer. Windows 10: Free as in herpes." --Man On Pink Corner in #52607549.
The to five finished i i the same second.
2 .html
1: Pether Gethin 1:18:12.60
2: Ronnie Petterson +0.01s
3: Francois Cevert +0.09s
4: Mike Hailwood +0.18s
5: Howden Ganley, +0.61s
See http://www.formula1.com/archive/grandprix/1971/52
for complete results.
For a nice date: Call strftime(3C)!
F1 is only an absolute maximum of 200 miles or 2 hours, whichever is first. Most races are about 190 miles or 60 - 80 laps.
One of the classical algorithms to do genetic evolution using floating point values (not bits) as parameters, is Differential evolution.
What's in a sig?
Reminds me, I made this,
which is some very simple code for the uninitated to genetic algorithms.
Interestingly enough, Peter Bentley's group results on car racing would not be considered human competitive, unless the results obtained in the simulation will be tried in the real world, or if the simulator is something experts actually use to shave of seconds. In any case, it seems the Evolutionary Computation world is starting to obtain very strong results, for a part due to Moore's law. It's possible that this is caused by the fact that the field simply tries to solve things, instead of first proving that it works (AI/ML), or proving that it doesn't work (Operations Research).
Kasey Kane should have won Dover and if he didn't, Jeremy Mayfield should have won. But Jeremy got caught up in a 18 car wreck. Evernham had a bittersweet day, it should have been a win for Dodge. Just another bad Nascar decision, what else is new. Nascar officials have been screwing everything up lately as long as it favors Junior.
Ok, having done a lot of work in Genetic Algorithms here is the elevator pitch.
A genetic algorithm is an algorithm that manipulates encoded problem solutions using a population of potential solutions. Each solution, or population member, in this case, is a set of racing car parameters. The genetic algorithm selects a couple of solutions and recombines parts of each to produce two new solutions using a recombination operator. Mutuation is normally added as well. The two new solutions are then "measured" for fitness; in the racing scenario a full scale simulation of the actual car is carried out. This produces a single value of fitness that is associated with the newly generated member.
The algorithm proceeds by selecting a couple of candidate parents; normally with random bias weighted toward fitter parents. The parents mate, new chidren produced, the children are measured, then integrated back into the population and they cycle continues.
The end result of all of this is that small "above average" solution components "accumulate" in the population at an exponential rate as time goes on. Of course, this only happens early in the first few generations before high "saturation" / convergence levels are reached. This is kind of cool because something good is happening at an exponential rate as time goes on; this is very useful when trying to solve problems with vast state spaces; eg the problem of finding a good racing car model where you need strong brew to find a resonable solution. Later on, most of the population members can often encode very fit solutions. This mathematical property (exponential accumulation) explains why the genetic algorithm is the algorithm of choice in nature, and also why an alarming proportion of PhD students are now studying genetic algorithms. This technique isn't new either, as Ratbag games have been using these techniques and other cool machine learning techniques for years to evolve the AI on their car titles such as "Dirt Track Racing" and "Powerslide".
Of course, we already know that this stuff works; as a quick trip to the zoo will show you what evolution has done to optimize the cheetah.
This is a very simplified view; there are a bunch of design issues such as encoding, premature convergence, crossover (recomination), reproduction methods, method of generation, population sizing, operator adaptation that make this whole field very interesting and addictive. Having written a dozen genetic algorithms and solved many many problem types using GAs they never cease to suprise me how powerful these methods are.
consider coffee a lubricant that helps one penetrate the coding zone
Is that genetic algorithms are nice for parametric optimisation, but not for breakthrough innovation.
"Using this sort of programmed procreation, the Digital Biology Interest Group has made self-healing battlefield surveillance robots -- gadgets that look like robotic snakes that can figure out how to wiggle home even when severely damaged, unlike less-evolved robots that typically just give up when one of their critical components goes out of commission."
It is tempting to conclude from that paragraph that, somehow, the "life force" of real snakes was transferred to machines via the power of evolution, as if GA could make a machine live. Indeed, the paragraph makes it sound like no other design method could have arrived at that solution, that there is something almost magical about GA.
Taking stuff apart since 1969 (TM)
Posts that ask you to mod a parent up are just so informative that I feel the parent post should be modded up.
88/100th of a second per lap?
Isn't that well within the margin of error that the human drivers would introduce? If the driver takes a turn slightly off of the most optimized route, wouldn't that negate the fraction of a second these algorithms are providing?
(I'd patent this idea, but you can have it /.)
"This is your life, and it's ending one second at a time."
Trust me, girls can indeed be impressed with BIG increases, but they don't care about cars. I've never heard of anyone needing a nitrous oxide kit fitted though, there are pills available if you can't produce enough on your own.
Rather than getting into the metaphor of genetic algorithms and biology...get practical.
Show how a gradient method is limited when you have distinct options (fastener sizes, commodity components etc).
Show how your product has a complex design space (assuming it does and genetic algorithms are necessary versus gradient methods). If your simulations are not too expensive, map out the design space on two of the variables (payoff function as versus 2 variables).
Eliminate the political or "religious" arguement and prove how the optimum found with GA is X% better then the solution found with other methods. And X% is worth $$$'s.
When the people fear their government, there is tyranny; when the government fears the people, there is liberty.
Genetic Racing sounds great in theory, but wait until the first inbred cars come out. You know, they start all scientific with that Formula 1, but when it works its way deep inside the country with NASCAR... oh, my hominy grits... those Republicans are gonna want to force us to race whatever comes out of the oven.
Zen is certainly the mystical function of the equation. Unfortunately, it is one we engineers find difficult to address.
In my many years of study (I go almost all the way back to Prolifferro Nuvolari), the theme of the driver as a closed loop has been my frame of reference. At speed the human body supplies an enormous amount of sensory data from vibration, centrifugal force acting upon the entire body, visual, auditory, data from the parts of the body in direct contact with the car, etc. etc.
That data combines within the nervous system and results in a tremendously complex firing of nerves that initiate hundreds of thousands of muscle twitches and jerks that, when applied to the controls of the car, make it go around. I know this sounds complex but when you realize we are dealing with thousandths of a second per lap, you'll see what I mean.
"There must be a better way", I always said to my self. Then one hot summer day, while eating a Creamcicle, it came to me. "The parts of the body in direct contact with the car" !! Carumba!!! Why didn't I think of it before ?? And, which part of the body has the greatest surface area that contacts the car ?? It was as plain as the nose on your face.
You will appreciate the need for working in secrecy these last few years. But, since you brought it up, now it can be told. If I could come to you as a race car driver and say, "How would you like to have 750 ONE THOUSANDTHS of a second per lap, guaranteed, money back, for only $89.95." What do you think you'd say ? Think of it. That's 562,000 one thousandths in the Sunbank 24 hours or almost 10 minutes !!
It took several years to develop and test my theory. My methods shall go with me to the grave. I was able to ascertain that there is a direct correlation between the sensitivity of a race car drivers Glutinous Maximus and his standings in his respective series. Then the question became, "How to neutralize this God given "Unfair Advantage" ?? How to give those less well endowed by their makers a boost up, so to speak, in this department ?? It was an ergonometrict engineering tour de force.
Sometimes the old ideas are best. Do you remember the old "Union Suit" ? With the trap door ? My Company has developed (with clever use of Velcro and tiny Japanese electric motors) the "Tenth of a Second" driver's suit. We advertise 750/1000 but
actually deliver a full tenth.
The device is simplicity itself. When the driver squirms down into the car, our unit pulls away all 3 layers of cloth rolling them neatly into an out of the way pouch. This puts the actual skin of the driver's Ass in direct contact with the Kevlar of the car seat. When the driver pulls himself up out of the car, the device modestly reverses, the result being seamless and unobtrusive. A special crash sensor activates the device in that eventuality, preventing possible burns. There is a separate manual control which has been redesigned after the embarrassing incident in Victory Circle at one of our test locations.
When we first approached drivers to test our prototypes, the reaction was cautiously positive and even a bit skeptical. After using the product all but one drive was enthusiastic. The usual response was, "Where can I get me one of these ?"
In this our first season, a certain few select drivers will be using our device in select races. For those of you interested from a scientific viewpoint I will be able to Email, at your request, car #s and races 5 days before each event. For those drivers who are constantly mobbed by hordes of beautiful women, the location of the manual button is being kept secret.
In race mode, there is of course another factor: where the aerodynamics of NASCAR give the advantage to a closely following car, the aerodynamics in F1 give the advantage to the car in front. Yes, this makes for awfully boring racing, but that's never bothered F1 fans who find it exciting to get a short glimpse of a red blur going past every couple of minutes... :)
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Formula 1 timing is down to the thousandth of a second and there have been occasions when the difference between pole position and second on the grid has been 0.000 seconds, (in which case the first person to set the time gets the pole).
Make sure you never test your optimized system using the model you used to optimize it. If you do, your optimized system always wins. If it doesn't win under these circumstances, you've used a bad optimization technique.
Genetic algorithms are terribly clever, and are useful for many purposes, but to make them work you need a "fitness function" - the ability to check how good a solution is. And, seeing you're going to need to apply it to every member of the population in each generation, it better be pretty bloody low-overhead, and be a pretty close approximation of the real-world fitness of a solution. In fact, in my admittedly limited experience with them I found that 99.9% of the difficulty in applying genetic algorithms to a problem is finding an appropriate fitness function.
The fitness function these guys have used is to use a racing simulation game and run the race electronically. That's good if you're trying to set up a car to win that game, but if you're actually trying to win a real car race with a real car, if the only fitness function you have is sending your driver out for a few million trial laps it's just not going to cut it.
If, on the other hand, they had built software that allowed them to specify the car settings and tell them what lap time the car would achieve, that would be really impressive, and then you could bolt on the GA optmizer to find the killer setup. But using GA's like they have done is just a party trick - cute, but not that impressive.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Foremost from my amateur racer point of view is the cost: Being able to tune any one of 60 some-odd parameters probably means being able to swap out any one of 60 some-odd parts with some other part, so you've got to have one of every possible part on hand or be able to fabricate it.
For an F1 team, cost's not so much a consideration, though, the trouble is time. To be able to change that many parameters means having someone get under the car, swap a pile of parts, and send the test driver back out on track to collect the info for the next evolution. Computer simulations are neat, but they're not perfect, and when you're talking about shaving fractions of a second, that small imperfection can throw it completely away.
I also wonder if this would actually be useful in the real world with real conditions. The sun going behind a cloud for a while has a measurable effect on lap times. The amount of gas in the tank, the temperature of the track, all those things change the way a car handles on the edge. Often, race setup is to dial in a car to be a little tighter or looser than what you really wanted because you expect the track to come to you.
And then there's a possibly even bigger problem: If you go out and look at two cars that are running identical lap times, chances are they're nothing even close to identically set up, because drivers aren't machines. One driver will like a certain setup, and another won't be able to do anything with it.
Three drivers had identical qualifying times down to 1/1000th of a second in 97.e l/f1/ races/portugal/?SPORTS
http://www.theautochannel.com/sports/openwhe
It will not get much faster, but will start running over pedestrians while a HUD shows how many points the pilot scored...
For those of us living in this universe, 88/100 is 0.88 seconds. That's an enormous difference, almost a second per lap. If you have ever watched high-performance racing, be it F-1 or stock car, you know that pulling away from the competition at a second a lap is gigantic. With regard to the drivers, it's not about whether or not they are perfect - it's about giving them the best "gear" to play the game. This is equivalent to developing new bats for baseball players or new cleats for football players.
Take this weekend's United States Grand Prix.
73 laps: if you can save 0.88 s each lap that means 64.24 s for the whole race.
There was a difference of 2.9 s between the first two racers (M. Schumacher and Barrichello) and 37.5 s between the first and the fifth (Panis), so that 0.88 s is a pretty significant amount. (Of course, in a race situation it would be less, since the presence of the other racers)
Real life is overrated.
Also, increasingly in Formula 1, it's more about getting pole position than the actual race itself as it is so difficult to overtake, and qualifying times, done on one 'hot' lap, are often much closer than .88 of a second.
"Feel the force, mother fucker." (Shaft Windu)
You've never watched a certain M Schumacher, obviously. The guy is a robot.
You didn't watch the race last Sunday, then, did you? He made a mistake... not that it would have diminished his chances of winning in the slightest, but nonetheless he did...
while true;do echo -e -n "\033[s\n\033[u\134_\033[B";done
Even robots make mistakes. What mistake are you refering to? Do you mean last Sunday as in at Indy or at Montreal?
WWJD.... for a Klondike bar?
This is already done in practice to optimize individual *parts* of a car. Certain desired/required parameters are given (dimensions as far as prescribed by regulations, necessary stiffness to survive race distance etc.). Others are variable (detailed geometry of individual parts). However, 70 parameters are just enough to model a single part, such as the shape of the nose.
The insight of the design at large still has to come from an engineer. Genetic algorithms are then used to fine-tune that design. Applying the algorithm is still hard because it requires a lot of knowledge of the physics involved. Once you have this, you can be quite successful because everyone is craving to optimize a few percent.
I'm thinking that since the purpose of Nos is to rapidly cool the air pre ignition (making it denser) you might have some shrinkage problems with your equipment if you tried to demonstrate BIG gains with the ladies.
Degaussing scares the bad magnetism out of the monitor and fills it with good karma.
Nice troll. Hope you're modded as such.
Will the car's DNA be admissable? Will they test the gas for steroids or the oil for amphetamines? Will the car have to comply with the laws of Robotics?
Yes, 2004 is beginning to look far more like 2002, than 2003. However, Paragon is built and once Williams(Sir Frank) sorts out his drivers, Then it should become more competitive again. Or wait for the spec tire coming 2006. And only a tifosi would mod parent a troll.
Then there's the circuits. I'm based in Melbourne, so we get the joy of a street circuit; you can't see *anything* unless you shell out hundreds of dollars for a grandstand pass (instead of $70 for general admission) and even then you can see maybe two corners.
I've seen F1, MotoGP, touring cars, supercross, speedway, even oddities like mud racing, both live and on TV. F1 has always been the most boring of the lot.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
I was thinking about another kind of Minimal Simulation...
No, seriously... using a smaller "universe" so they can test "real-world" while still using only 68 parameters (sic)...
And have all the car computer controlled, for testing, you know... + some serious fun 8)
It takes 40+ muscles to frown, but only four to extend your arm and bitchslap the motherfucker
I expect I could do a lot better with traditional optimization methods. Genetic algorithms are notoriously slow at converging and are only any good when all other methods fail. I expect that for a racing simulation the output is, almost everywhere, a differentiable function of the input parameters, and hence you can use some kind of calculus based minimization algorithm. People use adjoint methods all the time to differentiate fluid dynamics simulations or orbital manoeuvers so I don't see that these methods would fail for a racing sim. In fact this paper is probably a good place to start.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
( zooming away from lights to impress girls )
/.
I certainly hope you mean girls inside your car. Because if they're in the other car, you'd end up being far away from said girls. Then again, this is
Genetic Algorithms are really neat. I've seen a bunch go, and it is fun to see what they come up with in the end and how they get there. But what they simulate seems very strange to me. First off, my favorite computer games are driving simulations, and Electronic Arts is always harshly critisized by the sim community on how "arcade" their games are. It would seem doubtful that they designed a new piece of software just for this, but you never know. Second, is variables that change every hour at the track. 30F difference in temperature is HUGE in the way it affects how the car handles. Even 10F would most likely warrant some changes to the chassis. Plus, parts of the race track might be in the shade, also cloud cover affects a bunch of things. It could be done to write something that includes all the things head engineers face on race day, but it would take a lot of real life experimentation.
My lap times (autocross and road racing) improved a good deal when I put a harness into my car. It was so much eaiser to feel what the car was doing when you're firmly attached to the seat.
Pro hockey players tend to skate barefoot (no socks) for much the same reasons - less flexing in the skate due to better contact = better feel on the ice.
You could just as well use a grid search algorithm for this. After all, you basicly have a function of so many variables that returns a real number (lap time), and you want to minimize this function.
After doing a grid search, and saving your data, you could try some multi-variable calculus curve fitting and get a pretty good idea of where the local/global minima are likely to be. This way, you don't just have a unique solution, a single example of a fast car, but rather a theory in the form of an equation which can be empirically tested at many points to determine if your model is correct. Then you can tweak the model/equation based on empirical results, and do some simple multi-variable calculus to fit the real-world optimized solution.
One thing genetic algorithms are useful for is ever-chaning environments, where there is no unique solution and there are trade-offs between robustness in general and optimization for the momentary environment. In this case the GA allows you to continuously evolve as you go through various environments so that you (hopefully) end up with both good performance and excellent robustness, and possibly also find and record various different specialized species for different environments. Games of chance, such as poker or multiplayer xpuyopuyo against imperfect opponents is one example of this.
GA's are also useful when the design can not be reduced to a fixed number of real number variables, but rather is open-ended in terms of complexity.
Notice that living organisms satisfy both of these categories.Mathematics is not a crime.
This is not flamebait.
The shift schedule for automatic transmissions can be optimised for the urban cycle fuel economy measurement.
I have a genetic simulator for precisely that function.
Oh, you won't be getting 55 mpg from your PoS car any time soon, mass is the problem.
Full vehicle simulations (say using MSC ADAMS www.adams.com ) typically run at rather less than real time (say 10%) on a decent PC. GA lends itself to parallel evaluation of each solution, so each generation of say 1000 models could be run in say 20 minutes on 1000 cpus.
Alternatively, we have the option of running them on a Cray.
Alternatively #2 it would not be hard to reduce the run time for each model by cleaning it up manually, and running it in RAM. I'd guess it would be easy to achieve real time then.