Driving a car with genetic algorithm
I watched the following video on Youtube a while ago:
and wanted to write about it for long. Here a person is trying to create a car that will successfully drive around a track, he starts with 100’s of cars I think. Each car consists of an algorithm like this, that is velocity could be guided by this equation:\[v = \sum \alpha_i d_i\]
where \(d_i\) is the distance the cars sensors record from an obstacle in a particular direction. If you look at the diagram below, each car might be fitted with an algorithm to check for distance between obstructions in various directions.
Similar the steering angle could represented by the following formula:\[\theta = \sum \beta_i d_i\]
Looks very simple isn’t it. So how does this very simple equations make the car drive around the track? The reason is evolution. How does evolution work? First there is lot of randomness, if you watch the video the person creates lots of cars, with lots of values of \(\alpha_i\) and \(\beta_i\). So some cars are little better than others. Most of them crash soon, but the guy in the video picks the best cars and seeds it for the next generation.
So let’s say that for steering better if we consider angle measurement to be counter clockwise, now lets say the car is going towards an obstruction as show below:
now if we have \(\beta_1\) and \(\beta_2\) as negative and \(\beta_4\) and \(\beta_5\) as positive, as you see in the above image, as \(d_1\) and \(d_2\) decrease and \(d_4\) and \(d_5\) increase, the wheel angle will be more positive, that is the car will turn to the left thus avoiding collision.
So the ones that have the closest to the ideal values of \(\alpha_i\) and \(\beta_i\) are picked up the user and rest are destroyed, this forms the seed for the next generation. Some in the next generation may be better than seed and some may not be better than seed if we spawn younglings from seeds with minute variations to \(\alpha_i\) and \(\beta_i\). The video creator spawns lot of cars so definitely some are better and some are not. In the second generation he picks the best and spawns the third and so on. So as time goes by ones that are the best of the best of the best are picked and others are killed. So the cars get improving and improving until the video creator has finally picked few cars that drive down the track.
I have created a code that uses the same evolutionary principle to guess a number here https://gitlab.com/data-science-with-julia/code/-/blob/master/genetic_algorithm_to_guess_number.ipynb, if you understand it it’s great, else its still okay, I will be writing about it when I find time. May be in the future I will use the same principles to guess linear and non linear equations that fits a bunch of data points. But in the next few blogs I will write about functions and how they interacts with arrays in Julia.