Genetic Algorithms for Self-Driving Cars: Darwinism Optimization


By Dr. Lance B. Eliot, the AI Trends AI Insider –

I was watching the National Geographic cable channel the other day and marveled at a type of leopard that could leap several feet into the air to catch a bird mid-flight. The leopard at first had tried to get the bird while the bird was on the ground, but the bird was wise to the approaching leopard and opted to scurry into the air to get away. Seemed like the bird launching into the air would have been more than sufficient to escape the ground-based prowling leopard.  But, the leopard had anticipated that the bird would try to fly away, and cleverly the leopard ran at an angle that coincided with the upward trajectory of the bird, and managed to leap several feet into the air to intersect with the bird as it was taking off. A few more seconds and the bird would have reached a height that the leopard could not have achieved. Upon reflection of this leopard’s behavior, you need to really admire the physics aspects of the leopard being able to calculate the proper angle, speed, timing, and direction when it made its leap, since it was able to precisely snatch the bird in mid-stride and bring it down to the ground.  Score that as one win for the leopard family (another meal), one loss for the bird family.

How did the leopard know to make the leap? Did it go to college and learn it in school? Is there some kind of “leopard hunting” manual that the leopard had been reading? Those seem like unlikely explanations. A more plausible explanation would be that this type of leopard is the product of biological evolution. Over time, leopards that were able to ascertain how to best leap into the air to catch birds were presumably more likely to survive. Those leopards that were unable to add this tactic to their capabilities or that were not prone to it were less likely to get meals, and so they tended to starve off and not be around to reproduce. Leopards that inherited the ability to make these leaps were more likely to get meals, and more likely to survive, and thus more likely to reproduce. Eventually, leopards with this trait won out and become populous, while the leopards that did not have this trait lost out and became extinct.

There’s a well-known name for this explanation. Darwinism. As we all know today, Charles Darwin proposed a theory of evolution, which was published in 1859 in his now classic book “On the Origin of Species,” and for which his theory has gained widespread acceptance. His focus was on species of organisms and how natural selection leads to those that survive versus those that do not survive. In many ways, this theory was controversial when first proposed. Even today, there are some critics that don’t completely buy into his theory.  There are also ongoing debates about what his theory implies about the fundamental nature of mankind and creation.  I’m not going to open that Pandora’s box here.

I was reminded of Darwinism this morning while driving to work. A colleague was in my car and we were slogging through the dreadful bumper-to-bumper morning freeway traffic.  We were both visually scanning the traffic scene for any opportunity to somehow get ahead in the traffic. Suddenly, a car that was in the carpool lane made a mad dash out of the carpool lane. It illegally crossed the double-yellow lines that mark-off the carpool lane (see my article about self-driving cars and illegal driving), and then this same pushy car cut through all four other lanes of traffic. The driver was evidently trying to make a freeway exit but had not planned well to get to it. Besides cutting across all lanes and causing cars to abruptly slam on their brakes, he also just barely made the off-ramp.  He actually knocked over some cones at the off-ramp due to his wild maneuver and had been not able to get properly aligned to make the exit safely.

My colleague and I were stunned at the reckless and brazen act of the wanton driver. We both looked at each other and in the same moment said “Darwinism,” which was our way of conveying that we figured that his kind would ultimately get crushed or killed in a car accident, and he would eventually be weeding his kind out of the population pool. Of course, we didn’t actually believe this per se, it was more a figure of speech and bit of humor to lighten the stressful moment, but it highlights how much Darwin’s theories have permeated our everyday efforts and thoughts.

There is a line of inquiry and study that has tried to use Darwin’s theories for the development of mathematical algorithms development and for use in developing computer systems. This field of study is known as genetic algorithms. Basically, they are step-by-step procedures that try to use the same concepts that underlie the theory of evolution.  Be aware that there are various competing ways in which these genetic algorithms work, and there is no one specific standard per se. Different researchers and computer scientists have opted to implement genetic algorithms in varying ways. Generally, the overall approach is the same, but if you decide to use a specific software package or write your own software code, keep in mind that your use of genetic algorithms might differ from someone else’s use.

At the Cybernetic Self-Driving Car lab, we have been using genetic algorithms in ways that help self-driving cars.

Genetic algorithms can be used for standalone purposes, they can be used by embedding them into the self-driving car AI capabilities, and they can be used in conjunction with neural networks and other machine learning mechanisms (see my article about machine learning and self-driving cars). In this article, I’ll describe some ways in which we are using genetic algorithms for advancing self-driving cars.

Let’s start my example of genetic algorithms by bringing up an ongoing friendly debate between me and my daughter. As driver, she likes to really put the peddle to the metal. Every time she drivers her car, it is like an Indy race that involves her going as fast as possible, cutting all corners, and clawing for any means to reduce her travel time and get to her destination the soonest possible. In contrast, I am the perhaps stereotypical fatherly driving driver, namely I stop fully at all stop signs, I don’t gun the engine, I seek to get to my destination as soon as practical but with safety as a key factor in my approach. My daughter believes that my style of driving is archaic and over-the-hill, and furthermore that her style of driving is modern, realistic, and the only way to expeditiously get to any destination.  All I can say is that the number of dings, scratches, and other bumps on her car are suggestive that her approach, though maybe indeed more expeditious, also has the potential for some really adverse consequences.

My team at the Cybernetics Self-Driving Lab has overheard (ad nauseam) the lighthearted debates that me and my daughter have about driving styles. Over and over, I claim that I can pretty much get to the same destination as she, with marginal difference in time expended, and yet in a much safer manner. She claims that my style would add a huge amount of time to any driving excursion. Who is right? Intuitively, I realize that it seems logical that she must be right in that certainly if you go as fast as possible you would reach your destination sooner than someone else.  But, I claim that this intuitive notion is actually false when you include certain kinds of traffic conditions.

If there is heavy traffic on the roads, you are going to be bound by their progress. During my morning commute on the freeway, I see cars that try to go as fast as they can, but they get locked into the rest of traffic and so their attempts at going fast are blunted.  Yes, they might accelerate very quickly in little pockets or gaps of traffic, but nonetheless the rest of traffic is still keeping them going at a measured pace. Speed-up, slow down, speed-up slow down, this is the outcome of a frantic speeder driving style in those traffic conditions.  I assert that a more paced driver would be able to make the same amount of progress, and yet not be doing the useful speed-up’s and slowdowns that the frantic driver is doing.

A means to characterize this debate is to consider it as an optimization problem. We want to optimize the time it takes to get to a destination X, doing so in heavy traffic conditions T, and use some set of driving techniques S, in order to ascertain which is the “best” solution.  To make this a fair fight, we would want to keep the T approximately equivalent for any comparison of the set S. So, the set S of driving techniques might be a really good solution for light traffic conditions (a lite T), but then not be very good in heavy traffic conditions (a busy T). This is important in that my daughter’s style might be a tremendous solution when driving on the open road for miles and miles, since there are no obstructions and therefore going fast is in fact going to be the soonest arrival. On the other hand, when freeway traffic is solid and you can’t get going fast anyway, her solution might be equal to or maybe even worse than mine.

The team at the Cybernetics Self-Driving Car Lab decided to go ahead and use a genetic algorithm to test out the competing approaches to driving style. A genetic algorithm uses Darwinian aspects to try and solve an optimization problem.  Besides trying to settle the debate that my daughter and I are having, it is useful for self-driving cars too, since the question rightfully arises as to what kind of style of driving a self-driving car should have.

Most of self-driving car makers are assuming that the AI of a self-driving car should always be the most legal and most slow-poke kind of driver. This is sufficient right now during the research and development stages of self-driving cars. Once self-driving cars are truly in the real-world, we are likely to see that human occupants will want their self-driving car to be more aggressive. Some human buyers of self-driving cars might even use as a criterion of which self-driving car to buy whether it is one that is the “old granny” style driving or whether it can accommodate the “race car” driver style. I have been saying that self-driving car makers need to provide multiple driving styles and allow the human to select which kind of ride they want.  Right now, self-driving car makers are making it as “one style fits all” and we’ll likely gradually see the marketplace want choices.  That’s why we are developing the multiple styles at our Cybernetics Self-Driving Car Lab, in anticipation of a gradual realization that it is what humans will want to have their self-driving car be able to do.

Let’s get back to the genetic algorithm aspects. Typically, you start by creating a random initial population shaped around whatever structure you’ve decided upon.  In this case, we defined that a driving style consists of these factors:

  •        Speed Style
  •        Lane Changing Style
  •        Braking Style
  •        Distances Style
  •        Risk Style

This small set of factors is sufficient for a rudimentary setup, and there are added factors in our more robust version.

For the Speed Style, we established that you can be a very “fast going” driver, or instead be a more measured driver. For the Lane Changing Style, we established that you can be a continually lane changing driver, or instead an infrequent lane changer. For Braking Style, we used whether you are a hard-braking driver that comes to abrupt stops and rides your brakes, or instead you are a driver that uses the brakes only when necessary. For the factor on Distances Style, we established that you are a driver that drives right up to the butt of another car, or instead one that allows for appropriate stopping distances between cars.  For the Risk Style, we established that you are a high-risk driver that cuts things closely and takes significant chances of getting into a car accident, or instead you are lower risk driver that seeks to ensure safety as you drive.

Each of these factors is not a black-and-white scale per se, but instead more akin to a slider scale of being toward one end of the spectrum versus the other end. You don’t have to be only a completely go-fast driver and nor only just a go-slow driver, you can be somewhere in-between.

The nature of the trip itself is a crucial aspect. Just as in Darwinism, the environment is what determines fitness. If the leopard was in an environment where there weren’t any birds, it would be unlikely that the leopards that had a leaping capability would be a better fit over other leopards, and so that jumping trait would not be rewarded by being able to get more meals. For this self-driving car example, we opted to do my normal daily commute, which takes me anywhere from ninety minutes to two hours in very heavy morning freeway traffic conditions.  We also have collected actual traffic data that indicates the patterns of cars that are in the morning traffic, such as how many cars there are, their driving behaviors, and so on.

Let’s then suppose that we are trying to figure out that in this defined T, we will use a driving approach S that consists of the driving style of my daughter, and the goal is to minimize the time it takes to get the destination X where I work, and do so with the least number of accidents.  It is important to include in the optimization that the least number of accidents is a factor, since without it you could potentially bump into other cars and opt to just proceed ahead, but this is not realistic and getting into accidents should be a penalty.

On any given single trip of making the commute, one driving style might turn out more optimal than the other, due to variances, and so we need to simulate the trip numerous times to gauge whether the driving style is overall optimal or not (see my article about simulations and self-driving cars). We ran this simulation for thousands of trips. This is equivalent to realizing that Darwinism tends to take many years of evolution to see changes appear, and it is not something that tends to happen in the near-term. We also opted to divide the driving into segments, and adjust the driving style at each segment.

Using my daughter’s driving style, we created a population of drivers with her aggressiveness. We scored each member of the population based on their fitness score. This is considered the “current” population and is used to create the next generation.  Essentially, these are the parents which will contribute their genes toward their children.

For the next generation of the population, there are three kinds of children as based on the current population:

  •        Elite children are those with the best fitness value from the current population and so are considered to survive to the next generation.
  •        Crossover children are created by crossing genes from two parents and producing a child with a mix of their characteristics.
  •        Mutation children are created by mutations or random changes made to a selected parent.

At each driving segment, we took what was the current population, in this case aggressive drivers like my daughter, and produced offspring of having a tendency toward aggressive driving (which becomes the next generation). Some of the offspring would be just like the current population (elites), some of the offspring were a mix of two parents from the current population (crossovers), and some of the offspring were different from the current population (having been mutated).

Using the leopard analogy, go back in time before there were leaping leopards. At first, let’s assume leopards didn’t particularly leap. For that “current” population, they reproduced to generate their next generation of leopards.  We could just assume that all leopards produced as offspring are identical to the current population, and so the current population becomes the next generation, but that’s not what happens according to Darwin.

Instead, though there are some offspring that are identical to a single parent (elites). But, there are also some offspring that are based on a combination from their parents (crossovers), which if you have had children you probably noticed in your own children that they seem to be a mixture of both the father and the mother in ways that makes them unique in comparison to their parents (in other words, the child exhibits some traits that the mother has but the father does not, and traits that the father has that the mother does not).

There is also the mutation aspect. Sometimes a child seems to have a trait that neither the mother and nor the father seem to have.  Nature seems to introduce random variation that can presumably lead to offspring that will have a better chance at fitness, beyond what their parents had. In this case of the self-driving car, we allowed that the aggressive driver traits could be mutated, for example that the hard braking of an aggressive driver, which normally carries into the next generation or offspring, could have a random mutation that made it no longer a hard braking but maybe a softer braking.

After having setup the genetic algorithm for this, we ran it. You can run it based on how many times you want it to run, or there are other limits you can set, such as so-called “stalls” which is a measure of how far the next generation is from the current generation (if subsequent generations are not changing much, it probably suggests you can stop running the genetic algorithm). The runs can be allowed to go indefinitely and instead the focus be on the fitness test, in essence saying run this until the algorithm has reached a certain fitness point.

The results were fascinating.

In the end, in terms of greatest fitness and optimization, the aggressive style morphed towards a more moderate style. This appeared to support my contention that when faced with heavy traffic conditions over a somewhat lengthy path, the purist aggressiveness style does not in the long-run gain you much advantage and that instead a more moderate driving style is “better” for such conditions.  My daughter isn’t going to change her driving behavior because of this, and she genuinely enjoys her aggressive driving style, plus her style might well be better in shorter trips (we need to test this!), so the genetic algorithm effort that we did won’t be impacting her.

We believe though that this kind of use of genetic algorithms is important for self-driving cars and how the AI proceeds.

Using genetic algorithms for self-driving cars is likely done outside the actual driving of the car.  It is more akin to a design technique to assess differing ways to have the AI drive the car. Trying to use a genetic algorithm while in the midst of the AI driving a car is not only computationally intensive and expensive, it is questionable whether you would want to immediately put into play the outcome of the genetic algorithm without some other inspection of what it had produced.

Genetic algorithms can though potentially be used by sensor fusion for a self-driving car, which can be done beforehand (prior to embedding sensor fusion into the self-driving car), or could possibly done in real-time. This would allow you for example to determine LIDAR data in real-time (see my article about LIDAR) or camera images and video streams.

One increasingly useful aspect for genetic algorithms has been to tune neural networks. When you setup a neural network, there are various parameters that you need to establish. How do we know what will be a good setting for those parameters? A means to figure that out involves using a genetic algorithm that runs many generations of those parameters and tries to identify via a fitness function which settings will be the “best” or optimal for the neural network.

Genetic algorithms are at the far edge of the self-driving car industry and not yet being especially utilized by the self-driving car makers. We will gradually see this algorithmic technique shift from being mainly research oriented and become more real-world used by the self-driving car makers. It is another tool in the toolkit for self-driving car makers.  And, the more you want to push a self-driving car toward the level 5 (see my article about the Richter scale for self-driving cars), you’ll need to bring to the forefront any advanced tool that can help make that leap to a true self-driving car.  Drive safely out there!

This content is original to AI Trends.