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.
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?
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.
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).
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.
- 0.88 seconds is not well within the margin of error that the human drivers would introduce.
- If you would put all 20 current f1 drivers in exactly the same car, 15 of them would qualify within 0.5 of a second.
- 0.88 seconds advantage every 73 laps (Indianapolis) would accumulate to 64,24 seconds (almost a lap).
88/100th of a second per lap? Isn't that well within the margin of error that the human drivers would introduce?
Yes, but that doesn't negate its value (assuming the measurement is viable on the physical racetrack and not just in simulations). If you have a normal die A with sides labeled from 1 to 6 and another die B with sides labeled from 2 to 7, then there will certainly be rolls where A is higher than B, but on average, B will roll higher than A. In racing, this would translate to a slightly greater chance of winning--and while that may not be a breakthrough improvement, it's certainly better than none at all.
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.
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.
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.
Not only is there the performance gap in F1, but compared to Nascar, there's very little following of a safety (aka pace) car. This Sunday was the exception at Indy though. The tracks themselves have a lot of run off area (with the exception of Monaco), so usually when a car crashes, it's off track, or quickly removed from the track. In Nascar, if there's a crash, out comes the pace car, and the cars all bunch up again. Also, again, track design sometimes makes it very difficult to pass in F1, so a faster might get held up by a slower car for a few laps.
:) (Long time Ferrari fan, so I'm just loving the current domination of them rather than McLaren and Williams destroying the field. But such is F1, and another team will dominate eventually, and the cycle will continue.
And actually, on average, you're going to see a red blur every 45 seconds or so, and I love it
WWJD.... for a Klondike bar?
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.