TL;DR
In this article, we'll train the car to do self-parking using a genetic algorithm.
We'll create the 1st generation of cars with random genomes that will behave something like this:
On the ≈40th generation the cars start learning what the self-parking is and start getting closer to the parking spot:
Another example with a bit more challenging starting point:
Yeah-yeah, the cars are hitting some other cars along the way, and also are not perfectly fitting the parking spot, but this is only the 40th generation since the creation of the world for them, so be merciful and give the cars some space to grow :D
You may launch the 🚕 Self-parking Car Evolution Simulator to see the evolution process directly in your browser. The simulator gives you the following opportunities:
The genetic algorithm for this project is implemented in TypeScript. The full genetic source code will be shown in this article, but you may also find the final code examples in the Evolution Simulator repository.
We're going to use a genetic algorithm for the particular task of evolving cars' genomes. However, this article only touches on the basics of the algorithm and is by no means a complete guide to the genetic algorithm topic.
Having that said, let's deep dive into more details...
The Plan
Step-by-step we're going to break down a high-level task of creating the self-parking car to the straightforward low-level optimization problem of finding the optimal combination of 180 bits (finding the optimal car genome).
Here is what we're going to do:
- 💪🏻 Give the muscles (engine, steering wheel) to the car so that it could move towards the parking spot.
- 👀 Give the eyes (sensors) to the car so that it could see the obstacles around.
- 🧠 Give the brain to the car that will control the muscles (movements) based on what the car sees (obstacles via sensors). The brain will be simply a pure function
movements = f(sensors). - 🧬 Evolve the brain to do the right moves based on the sensors input. This is where we will apply a genetic algorithm. Generation after generation our brain function
movements = f(sensors)will learn how to move the car towards the parking spot.
Giving the muscles to the car
To be able to move, the car would need "muscles". Let's give the car two types of muscles:
- Engine muscle - allows the car to move ↓ back, ↑ forth, or ◎ stand steel (neutral gear)
- Steering wheel muscle - allows the car to turn