Optimizing the Driving Behavior of Self-Driving Cars Using Genetic Algorithms
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Number of Parts | 95 | |
| Author | ||
| License | CC Attribution 4.0 International: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/32335 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
| |
| Keywords |
FrOSCon 201712 / 95
4
8
9
15
20
22
23
24
25
27
29
32
36
37
38
39
40
45
46
47
48
49
50
51
53
54
59
63
64
65
74
75
76
79
83
84
86
87
88
89
91
92
93
94
95
00:00
Domain nameParameter (computer programming)Natural languageEvoluteBranch (computer science)AlgorithmPerformance appraisalHypermediaVirtual machineSoftwareMathematical optimizationCartesian coordinate systemMereologyField (computer science)Flow separationTerm (mathematics)Set (mathematics)Strategy gameMultiplication signDifferent (Kate Ryan album)BitStudent's t-testMetre9K33 OsaMathematical modelOpen sourceSoftware testingOpen setInheritance (object-oriented programming)Machine learningDynamical systemEndliche ModelltheorieDistanceSoftware developerTrailArtificial neural networkGame controllerWeightSelectivity (electronic)NumberTotal S.A.Electric generatorComputer clusterParametrische ErregungDevice driverCASE <Informatik>Office suitePresentation of a groupPattern languageTheory of relativityPower (physics)Fitness functionNatural numberUniverse (mathematics)Solvable groupRight angleCountingIterationSystem callXMLComputer animation
06:03
Right angleCurveWater vaporTrailGraph coloringGroup actionPosition operatorAsynchronous Transfer ModeProcess (computing)Limit (category theory)Inheritance (object-oriented programming)Order (biology)Shape (magazine)NumberRandomizationError messageSoftware crackingDistanceMathematicsPressureGoodness of fitParametrische ErregungCombinational logicTheory of relativityPhysical systemSpeech synthesisIterationPoint (geometry)WordFitness functionMedical imagingWave packetGreatest elementParameter (computer programming)Universe (mathematics)MereologyConstraint (mathematics)Context awarenessCurvatureIndependence (probability theory)Software frameworkReading (process)2 (number)Chromosomal crossoverElectric generatorAlgorithmProduct (business)Range (statistics)Roundness (object)InformationBitMaxima and minimaDrag (physics)Computer animation
11:59
Computer animation
12:20
Cellular automatonCurveMultiplication signProcess (computing)Endliche ModelltheorieAsynchronous Transfer ModeVirtual machineObject (grammar)Parameter (computer programming)1 (number)Block (periodic table)Food energyWave packetBitFlow separationInclusion mapLine (geometry)CoprocessorMessage passingGraphical user interfaceComputer animation
14:49
Artificial neural networkWave packetParameter (computer programming)Point (geometry)AlgorithmArithmetic progressionMereologyTrailDevice driverChromosomal crossoverFlow separationMathematical optimizationProfil (magazine)Pairwise comparisonNumberElectric generatorSoftwareMultiplication signBit rateInsertion lossLink (knot theory)Virtual machineGoodness of fitLinear regressionKinematicsGenderFrame problemElectronic visual displayNavigationCrash (computing)Electronic mailing list2 (number)Set (mathematics)Forcing (mathematics)outputLecture/Conference
21:00
Computer animation
Transcript: English(auto-generated)
00:07
My name is Maximilian Manzing, I'm currently a student at Bonranzig University and also working at DJI in Cologne, and I'm going to talk a little bit about optimising the
00:20
driving behaviour of self driving cars using genetic algorithms today. Thanks for showing up at this very late time, I didn't actually expect that many people to come on the last day of Froskon, this late hour. First of all, what am I talking about? Usually when people hear about machine learning they
00:42
think about neural networks and deep learning, because this is what's in the media all the time, but there's also another branch of machine learning which is less known, it's genetic algorithms, which also has a very nice field of applications to optimise parameters in domains which are less known and where people don't have that much domain knowledge
01:03
and control. For example, if we want to use self driving cars, as we would for example in talks, the open racing car simulator. No, it's speaking. Sorry? Better? No, the
01:34
group? Hello, hello? I think this is better now, I hope.
01:44
Okay. Torx is a free and open source software used for 3D car racing simulation, and it has a very nice sophisticated physical model for the racing simulation. It takes into account the material the tyres are made of, also the dynamics of the car which you're
02:04
driving, and also how the car behaves on different kinds of roads, and it's widely used by conferences, like for example the Gecko conference used four years ago to do the big algorithms challenge where people had to train their agents for best behaviour
02:22
on a certain set of tracks, and also Google DeepMind is currently working on agents which can control the Torx cars which will probably come up in one of the next conferences they are participating. Usually when you're writing software for self driving cars, the software is very complex in development and testing, because the developer has to
02:45
think of so many corner cases, and there are so many parameters, like for example the distance to the car you can, when you're driving at a certain speed, you have to know how far you have to stay away from other cars in the traffic, or how far can you go in curves, and these parameters are very, very hard to test by hand and to develop
03:04
by hand, so it would be very nice to have an algorithm helping with this, and here one possible solution might be a genetic algorithm. Here we only need to develop a very, very basic controller, not taking into account many things you would if you would do everything manually, and then this algorithm is used to train and evolve the behaviour
03:26
of the car to find the best possible driving strategy with a given software. So I've been saying this term genetic algorithms a few times now, what are these algorithms
03:40
actually? Genetic algorithm is an algorithm inspired by nature, by the natural evolution also we emerged from, and it's basically a method for optimising parameters in a domain where we have maybe limited or no domain knowledge at all, which might be fields from physics, or like for car driving I'm also not that proud of the car, so I don't
04:03
really know that much, maybe I know when to brake, and I'm a very careful driver, but well, here we can use an algorithm to learn better strategy, and the only thing we need is the problem to be solvable and testable in a situation, a simulation sorry,
04:21
and also the problem has to be disposable into a set of parameters describing what we are doing, so we can have actually something the algorithm evolves, these parameters will be called genome or individual from now on, and usually the algorithm starts by initialising a set of parameters, several genomes called population, where all the parameters are in
04:47
one individual, and we have several individuals, and each of those has to go to the simulation and then we see how good it completed the track, or maybe it didn't complete and only got a certain amount of metres on the track, and then the algorithm will start
05:02
evolving and improving those parameter sets, those solutions, and maybe find the best driver yet. So this evaluation part on the top left would be what I was already talking about, when you're putting the parameter set into Torx, it will start, the cars will complete
05:21
the track and we will get a fitness value back, which tells us how good the car performed in total. Then the first step of the algorithm itself is the selection part on the top right, this is basically like humans going to the disco where we are selecting the parents for the next generation of children, a certain number of parents gets selected, like, usually
05:54
we assign a certain weight to each individual, if it has a better fitness, it might have
06:01
a better chance of being selected, and if it has, well, maybe it didn't complete the track at all, or maybe it was very slow, it has a lower fitness and has a lower chance of getting selected as a parent, but still all individuals might be selected for the next generation, because a very good performing individual with a high target speed can learn
06:23
from the steering behaviour of a weaker individual, and in combination of those, it might improve actually. So the combination is done with a crossover on the bottom right, for the crossover we are taking two of the parents we just selected, and create an offspring from those. This is usually done by just taking maybe random genes from one of the
06:45
parents and combining them with random genes from the other parent, but keeping the order the same, or taking the first half of the genome from one of the parents, and the second half from the other parent, and thereby creating a child like it would be with human production of children, and then as we know sometimes dark haired people
07:06
get a red haired child, and this is obviously maybe, okay, those parents, maybe someone had a different girlfriend, a different boyfriend at some point, or there was a little mutation, and this is also introduced with this mutation process, we are changing a very low number
07:22
of the genome, of the genes, sorry, and introduce some new information to it, by maybe increasing the target speed or the distance to another car on the track, and yeah, so, how do we put this together with Torx? First of all, our cars have a few little track sensors,
07:43
which will tell us how far the car is on the left or on the right of the track, and how it is tilted to the track, it will tell us the current speed, the gear we are currently driving at, the rounds per minute the motor has currently, and we have 19 range finders distributed over the front half of the car, and depending on the range finders, they show us
08:06
how far the car is with each of the sensors on the track border, and for example, the third sensor to the right here, and the front here, we know, okay, there's a very steep curve to the right, so we have to start driving right, and this helps us determine the curvature.
08:24
So, what parameters are we actually learning here? We have a very, very simple agent, it will just try to accelerate to a maximum speed, and because we know if we're driving too fast, we might not be able to brake before a curve or before a wall, and just drive into it,
08:41
or the motor or RPM for gear shifting, especially driving beginners like me know this a lot, if you don't have enough rounds per minute, the car will just turn off if you're trying to gear shift, and your car will die in front of the traffic light, and also if you always shift at the optimal position, it's a lot better for efficient and fast acceleration,
09:04
and then for curves, of course, we know that we need to decelerate a bit before a curve, and then, yeah, so we need to have a maximum speed we can still sustain in a curve, and also need to know how strong we are braking before, and we need to determine
09:23
the steering strength and dependence to the curvature, and also if the car gets damaged, we might still want to allow it to complete the track, so we might just limit the maximum speed of a car by learning this parameter also. So, let's see how well this works in training.
09:45
This was done with 30 randomly generated individuals trained for 50 generations, and as we can see, in the very first generation, it took about 195 seconds for the cars to complete the track, and by running through this algorithm over and over again, and evolving the parameters,
10:02
after about 7 to 10 generations, we went down to 155 seconds for the track, and after this, the slope of the learning curve slowed down a bit, and after about 50 generations, we were down to 142 seconds of training, which is quite improvement, but we can see that most of the learning is done in the very first generations.
10:27
I'll do a live demo, but I think I'll just complete this first. Others have also used algorithms already in industry, for example, this was done by NASA. When NASA had to develop an antenna for the ST-5 mission,
10:41
they had engineers working on this for years and years, and they didn't come up with a viable solution fulfilling all the parameters for the mission, so at some point, they just decided to put all the constraints into stimulation and use the genetic algorithm to involve this quite counterintuitive antenna design, which was then deployed on the spacecraft, it's still in orbit,
11:02
and it turned out to work better than anything the engineers did there. Sorry? Yeah, maybe this prototype, which they did with the paperclip actually. They can create a random solution in the beginning.
11:24
And also, at our team here at university, we're using genetic algorithms to optimize the shapes of velomobiles, which are basically bicycles you can lay down in and have a chassis, so you have less resistance, less drag from the air hitting on you when you're driving,
11:43
and yeah, this is just a number of shapes generated with evolutionary methods towards certain parameters, like for example, good pressure through the road and as little drag as possible, depending on the size you have inside. So, let's see how well, let's just go to my VM,
12:11
here's a little talk, and let's just see how one of those agents would behave driving.
12:21
This runs on my machine. Yeah, I love the full-screen motors in this simulation. Yeah, we can see it's somewhere around 5,000 RPM, it knows, okay, I can shift here, very good. Goes down to about 70 kilometers per hour in a curve, and we can see that these super steep curves, it's quite aggressive, but still working.
12:42
Also, there's already a little bit of damage here, so it's quite aggressive, but seems to be performing quite well, with only, like, the entire agent is like 30 lines of Python. All the parameters were trained.
13:03
The parameters for this were trained, and this was trained without the GUI and only using the simulation. What's the actual, okay, I thought it was driving backwards for a second there.
13:22
Yeah? Yes, you can completely decouple this, run it in headless mode, and then choose as many processors as you want, and run hundreds of simulations at the same time, which is very nice, when you have a population of 100 individuals you're training, you can train all of them at once, and don't have to wait for the others to complete.
13:42
Sorry? Yeah? You can also include several cars into training,
14:01
and, yeah, it has opponent sensors too, if you want to, well, extend it a little more, and it will find quite sophisticated driving behavior, we've seen this, that if there's a car chasing it, it might just try completely to keep one of the opponent sensors blocked, so it knows, okay, there's one behind me,
14:21
and it cannot pass me, and the one behind might be trained in a way, it knows, okay, if there's a strong curve, maybe, I can try to push it against the wall, and it will get damaged. Okay? Yeah. Any more questions? I think we just jumped over to the questionnaire.
14:48
This was the Alborck track, I think the fastest driver on the 2006 World Championship was 1 minute and 5 seconds, or something like that, and this car does about 1 minute 20 seconds,
15:01
after like 50 generations of training. We achieved about the same speed and lap time with neural networks, we also trained neural network agents for this,
15:21
which didn't have any software agent at all, it was only neural network having the sensors I just described as input, and then had some gearing, the gear setting, steering and braking and acceleration as outputs, and this got, after a lot longer training, to about the same speeds.
15:44
Yes, yes. Yes. The question was, if you have comparison to other machine learning methods,
16:08
can you deal with obstacles in between? Dynamic? Yeah, well, it has these opponent sensors, I think an opponent car driving on the track would be an opponent trying to dodge.
16:20
Yeah.
16:43
It's used for racing. The question is if genetic algorithms can be compliant,
17:08
applied to other parameter optimisations. Yeah, sure. As long as you have some simulation or some efficient way to test it, you can always use genetic algorithm to try to approximate the almost optimal set of parameters in the end.
17:31
Yes, yeah. The question is if the genetic algorithm has parameters itself. Yes, it does. I skipped over this because I think if there are people in the audience
17:41
not really knowing about this, it's a little too much to go into detail about the parameters. But, for example, one thing I actually forgot to say, you can always keep the best, you're elite and copy to the next generation so you don't lose progress and don't have a population at some point where no one is performing
18:00
as well as in the population before. And you can have a crossover rate so only a certain number of the individuals do actually perform crossover. You have mutation rate, how strong the individuals get mutated and how many of them get mutated
18:20
and how large parts of the genome get mutated. There's a huge amount of parameters which you can set again. This totally depends on the problem. This totally depends on the problem. It's very problem dependent and when you're using genetic algorithms
18:40
you need to develop a feeling for this what's good and what's bad for your current problem. Yes. It's way too disruptive.
19:04
Yes, this was also tried the question was if this was also tried in different tracks. Yeah, this was this agent was mainly trained for asphalt roads but we can also perform training on several roads at once and then we can yeah.
19:25
Did you put it on another track? Yeah, I can do this if you want right now. Yeah, well this driver works on almost every asphalt track.
19:41
Yes, I will put this onto my FrostCon profile in my GitHub link. It's on GitHub. You can just put it on this.
20:11
The question is I think if this also works with opponents or if the training has to be done differently with opponents if you put opponent into this this car doesn't use the opponent sensors
20:22
so it will completely ignore opponents and it will just crash into them, lose its behavior and have to try to get back on track again. You have to enable the opponent sensors and perform training completely differently if you had these enabled. It was tested but not for
20:41
this agent. I think that's it.