Self-Parking Car in 500 Lines of Code

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: You may train the cars from scratch and adjust genetic parameters by yourself You may see the trained self-parking cars in action You may also try to park the car manually 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 ← left, → right, or ◎ go straight while moving With these two muscles the car can perform the following movements: In our case, the muscles are receivers of the signals that come from the brain once every 100ms (milliseconds). Based on the value of the brain's signal the muscles act differently. We'll cover the "brain" part below, but for now, let's say that our brain may send only 3 possible signals to each muscle: -1, 0, or +1. type MuscleSignal = -1 | 0 | 1;For example, the brain may send the signal with the value of +1 to the engine muscle and it will start moving the car forward. The signal -1 to the engine moves the car backward. At the same time, if the brain will send the signal of -1 to the steering wheel muscle, it will turn the car to the left, etc. Here is how the brain signal values map to the muscle actions in our case: MuscleSignal = -1Signal = 0Signal = +1Engine↓ Backward◎ Neutral↑ ForwardSteering wheel← Left◎ Straight→ Right You may use the Evolution Simulator and try to park the car manually to see how the car muscles work. Every time you press one of the WASD keyboard keys (or use a touch-screen joystick) you send these -1, 0, or +1 signals to the engine and steering wheel muscles. Giving the eyes to the car Before our car will learn how to do self-parking using its muscles, it needs to be able to "see" the surroundings. Let's give it the 8 eyes in a form of distance sensors: Each sensor can detect the obstacle in a distance range of 0-4m (meters). Each sensor reports the latest information about the obstacles it "sees" to the car's "brain" every 100ms. Whenever the sensor doesn't see any obstacles it reports the value of 0. On the contrary, if the value of the sensor is small but not zero (i.e. 0.01m) it would mean that the obstacle is close. You may use the Evolution Simulator and see how the color of each sensor changes based on how close the obstacle is. type Sensors = number[];Giving the brain to the car At this moment, our car can "see" and "move", but there is no "coordinator", that would transform the signals from the "eyes" to the proper movements of the "muscles". We need to give the car a "brain". Brain input As an input from the sensors, every 100ms the brain will be getting 8 float numbers, each one in range of [0...4]. For example, the input might look like this: const sensors: Sensors = [s0, s1, s2, s3, s4, s5, s6, s7]; // i.e. 🧠 ← [0, 0.5, 4, 0.002, 0, 3.76, 0, 1.245]Brain output Every 100ms the brain should produce two integers as an output: One number as a signal for the engine: engineSignal One number as a signal for the steering wheel: wheelSignal Each number should be of the type MuscleSignal and might take one of three values: -1, 0, or +1. Brain formulas/functions Keeping in mind the brain's input and output mentioned above we may say that the brain is just a function: const { engineSignal, wheelSignal } = brainToMuscleSignal( brainFunction(sensors) ); // i.e. { engineSignal: 0, wheelSignal: -1 } ← 🧠 ← [0, 0.5, 4, 0.002, 0, 3.76, 0, 1.245]Where brainToMuscleSignal() is a function that converts raw brain signals (any float number) to muscle signals (to -1, 0, or +1 number) so that muscles could understand it. We'll implement this converter function below. The main question now is what kind of a function the brainFunction() is. To make the car smarter and its movements to be more sophisticated we could go with a Multilayer Perceptron. The name is a bit scary but this is a simple Neural Network with a basic architecture (think of it as a big formula with many parameters/coefficients). I've covered Multilayer Perceptrons with a bit more details in my homemade-machine-learning, machine-learning-experiments, and nano-neuron projects. You may even challenge that simple network to recognize your written digits. However, to avoid the introduction of a whole new concept of Neural Networks, we'll go with a much simpler approach and we'll use two Linear Polynomials with multiple variables (to be more precise, each polynomial will have exactly 8 variables, since we have 8 sensors) which will look something like this: engineSignal = brainToMuscleSignal( (e0 * s0) + (e1 * s1) + ... + (e7 * s7) + e8 // <- brainFunction ) wheelSignal = brainToMuscleSignal( (w0 * s0) + (w1 * s1) + ... + (w7 * s7) + w8 // <- brainFunction )Where: [s0, s1, ..., s7] - the 8 variables, which are the 8 sensor values. These are dynamic. [e0, e1, ..., e8] - the 9 coefficients for the engine polynomial. These the car will need to learn, and they will be static. [w0, w1, ..., w8] - the 9 coefficients for the steering wheel polynomial. These the car will need to learn, and they will be static The cost of using the simpler function for the brain will be that the car won't be able to learn some sophisticated moves and also won't be able to generalize well and adapt well to unknown surroundings. But for our particular parking lot and for the sake of demonstrating the work of a genetic algorithm it should still be enough. We may implement the generic polynomial function in the following way: type Coefficients = number[]; // Calculates the value of a linear polynomial based on the coefficients and variables. const linearPolynomial = (coefficients: Coefficients, variables: number[]): number => { if (coefficients.length !== (variables.length + 1)) { throw new Error('Incompatible number of polynomial coefficients and variables'); } let result = 0; coefficients.forEach((coefficient: number, coefficientIndex: number) => { if (coefficientIndex < variables.length) { result += coefficient * variables[coefficientIndex]; } else { // The last coefficient needs to be added up without multiplication. result += coefficient } }); return result; };The car's brain in this case will consist of two polynomials and will look like this: const engineSignal: MuscleSignal = brainToMuscleSignal( linearPolynomial(engineCoefficients, sensors) ); const wheelSignal: MuscleSignal = brainToMuscleSignal( linearPolynomial(wheelCoefficients, sensors) );The output of a linearPolynomial() function is a float number. The brainToMuscleSignal() function need to convert the wide range of floats to three particular integers, and it will do it in two steps: Convert the float of a wide range (i.e. 0.456 or 3673.45 or -280) to the float in a range of (0...1) (i.e. 0.05 or 0.86) Convert the float in a range of (0...1) to one of three integer values of -1, 0, or +1. For example, the floats that are close to 0 will be converted to -1, the floats that are close to 0.5 will be converted to 0, and the floats that are close to 1 will be converted to 1. To do the first part of the conversion we need to introduce a Sigmoid Function which implements the following formula: It converts the wide range of floats (the x axis) to float numbers with a limited range of (0...1) (the y axis). This is exactly what we need. Here is how the conversion steps would look on the Sigmoid graph. The implementation of two conversion steps mentioned above would look like this: // Calculates the sigmoid value for a given number. const sigmoid = (x: number): number => { return 1 / (1 + Math.E ** -x); }; // Converts sigmoid value (0...1) to the muscle signals (-1, 0, +1) // The margin parameter is a value between 0 and 0.5: // [0 ... (0.5 - margin) ... 0.5 ... (0.5 + margin) ... 1] const sigmoidToMuscleSignal = (sigmoidValue: number, margin: number = 0.4):