This is cute, but am I missing some way to make it run faster? It seems to only happen in real time.
Group sizes of any more than about 10 make my machine slow to a crawl. Using the suggested population size of 500, then means it takes running 50 groups to pass 1 generation. With the suggested time of 17s, that's about 15 minutes per generation. The recommended 50 generations would therefore take over 12 hours.
And that's at the low-end of their recommendations. Population size of 1000 and 100 generations would take 50 hours.
I feel like usually with these things you want to run most of the generations headless, as fast as possible, and only show a few exemplars from each generation so the user can see how the evolution is progressing.
Yes, currently the simulation performance is one of the biggest issues (https://github.com/trekhleb/self-parking-car-evolution/issue...). You may try to check the “Performance boost” checkbox that simplifies the geometry. It should give you approx x1.5 performance increase. But even with x1.5 boost the performance is still an issue, yes
Does each visitor submit their dna back to the server? Using the power of the web this allows you to have as many "cores" as you have visitors, and train massively parallel!
I haven’t thought about the native version, it was fun trying to implement it for browser. To resolve the performance issue I would try next to switch to the 2D simulation engine, since we don’t use the height during the parking. Getting rid of the 3rd dimension, lights and complex geometry would increase the performance drastically I believe
Yes, training may happen pretty fast in 2D, but then applied to the 3D to final visualizations. But this is just an assumption. I haven’t tried this approach yet.
https://rednuht.org/genetic_cars_2/ does something like this. You can turn off visualizations and let it run for a while then turn visualizations back on or replay the best result.
Indeed, the simulation should not be done in real time.
The 3D world could be a cute way for users to change the parking scenario and then let the algorithm run in background and show the winners every 1000 cycles.
> 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.
I would guess that mapping ”nothing here” to a value that is higher than the others would give better results. The software wouldn’t have to learn that weird inversion where the safest value is very close to the least safe ones.
Alternatively, it would be interesting to try having the sensors output 1/(distance + k), where k is maybe 0.1m. Then the output would naturally go to zero as things got further away.
Many depth estimation AI approaches do that and call it disparity. The idea there is that as things get further away, you'll see distances less precisely, so perceptually 20cm to 30cm might be the same as 20m to 30m
The mental model is like this: if sensor says 4 - it means the obstacle is 4 meters away. If obstacle is far away, then sensor may say… hm… 5 meters? 10 meters? Infinity meters? So I went with something a bit higher than max sensor distance limit of 4 meters. And, for linear equation this didn’t work for me. Cars were straggling to learn.
So I’ve switched to another mental model: if sensors says 0 - it means we just turn the sensor of, the sensor is not important. Let’s say you want to learn how to drive forward if the obstacle is behind you. Then you don’t care about the side sensors, you may just cancel them with zero variables. And with this setup, the cars started to learn much faster.
I think the correct approach depends on the brain “model”. For linear equation, canceling the sensor with the zero value of the sensor.
But if you would manage to train the cars well with the different approach - it would be really interesting to try
I would go for “4 meters and a tiny bit”. When driving in a thick fog that limits vision to 4 meters, a sane driver interprets “don’t see anything” as “there’s at least 4 meters of room”, not as “5 meters” or “10 meters”.
That also makes sense if you interpret “sensor says 3” not as “obstacle is 3 meters away”, but as “there’s 3 meters of room”.
But then, I didn’t try to see what works better. I find the result surprising, though.
However, there is an issue right now (https://github.com/trekhleb/self-parking-car-evolution/issue...), that the cars are not “punished” for hitting another cars (they are allowed to create the road accidents). That’s why if both cars have hit another cars they may continue driving and approaching the parking lot (only approaching matters so far). That’s not good, agree. But the app is in proof-of-concept stage, so it has the issues like this.
If you hold down space and right your car drifts to the right a tiny bit with only a very small amount of rotation. This lets you move into the spot directly sideways.
This is pretty cool, kudos to the author. However, I'm curious about why would you want to use a genetic algorithm (GA) for what is clearly a relatively straightforward computer vision (CV) problem. I would argue that the GA-based evolutionary solution is no simpler and, more importantly, will not only never outperform the CV-based one in terms of accuracy and speed, but will be orders of magnitude slower.
You are right in this particular case. CV may effectively solve this particular problem, but will be useless if yellow cars are replaced with blue trucks, or if starting angle will be slightly different, or if other cars will start moving as well, etc, etc.
Genetic algorithm may be useful if one needs to animate cars in a game and making the algorithm less deterministic will make the game look better.
Yeah, the GA is not the best option for self-driving tasks, agree.
The reason why I chose GA is because I wanted to play around with this algorithm at the first place. And only after that I’ve tried to come up with some artificial problem I could try to solve with it :)
I'm glad that we're on the same page on this. Your motivation is totally understandable and the end result (including relevant blog post) is both very nicely done and educational. Thank you for this and your other resources that you share online! :-)
How challenging would it be to design something similar generically, such that you can just define the "pain" and "reward" and just have some random 3D model in a 3D world take random actions until there's no more "pain"?
Incredibly well explained, kudos to author! This reinvigorated my interest in genetic algorithms. Last time I considered getting my hands dirty with GA was for this Kaggle challenge which still remains largely unsolved:
I can definitely outperform a computer at the task of parking a car. But not in a slow simulation in a browser with a keyboard for steering and no feedback.
44 comments
[ 3.0 ms ] story [ 86.3 ms ] threadall the steps are well described and the code can be used as a template for other examples
Group sizes of any more than about 10 make my machine slow to a crawl. Using the suggested population size of 500, then means it takes running 50 groups to pass 1 generation. With the suggested time of 17s, that's about 15 minutes per generation. The recommended 50 generations would therefore take over 12 hours.
And that's at the low-end of their recommendations. Population size of 1000 and 100 generations would take 50 hours.
I feel like usually with these things you want to run most of the generations headless, as fast as possible, and only show a few exemplars from each generation so the user can see how the evolution is progressing.
> For better results, increase the population size to 500-1000 and wait for 50-100 generations
Do you have example output from that? I'd expect my computer to take months of running 24/7 to get there.
You may also press the "Restore Evolution" button and then press "Use demo checkpoint" to use some pre-trained data.
The 3D world could be a cute way for users to change the parking scenario and then let the algorithm run in background and show the winners every 1000 cycles.
I would guess that mapping ”nothing here” to a value that is higher than the others would give better results. The software wouldn’t have to learn that weird inversion where the safest value is very close to the least safe ones.
The mental model is like this: if sensor says 4 - it means the obstacle is 4 meters away. If obstacle is far away, then sensor may say… hm… 5 meters? 10 meters? Infinity meters? So I went with something a bit higher than max sensor distance limit of 4 meters. And, for linear equation this didn’t work for me. Cars were straggling to learn.
So I’ve switched to another mental model: if sensors says 0 - it means we just turn the sensor of, the sensor is not important. Let’s say you want to learn how to drive forward if the obstacle is behind you. Then you don’t care about the side sensors, you may just cancel them with zero variables. And with this setup, the cars started to learn much faster.
I think the correct approach depends on the brain “model”. For linear equation, canceling the sensor with the zero value of the sensor.
But if you would manage to train the cars well with the different approach - it would be really interesting to try
That also makes sense if you interpret “sensor says 3” not as “obstacle is 3 meters away”, but as “there’s 3 meters of room”.
But then, I didn’t try to see what works better. I find the result surprising, though.
nn_input = 2/(1+exp(-distance))-1
This also captures the fact that differences in small distances are more meaningful.
However, there is an issue right now (https://github.com/trekhleb/self-parking-car-evolution/issue...), that the cars are not “punished” for hitting another cars (they are allowed to create the road accidents). That’s why if both cars have hit another cars they may continue driving and approaching the parking lot (only approaching matters so far). That’s not good, agree. But the app is in proof-of-concept stage, so it has the issues like this.
The reason why I chose GA is because I wanted to play around with this algorithm at the first place. And only after that I’ve tried to come up with some artificial problem I could try to solve with it :)
Auto manufacturers should just implement that behavior!
https://www.kaggle.com/c/abstraction-and-reasoning-challenge