Show HN: Self-Parking Car Evolution | Hacker News Reader

Show HN: Self-Parking Car Evolution

trekhleb.dev

119 pointsoleksiitwork43 comments

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

The page says:

> 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.

Yes, you may press the "Restore Evolution" button (at the bottom of the screen) and then upload the pre-saved training checkpoints from here https://github.com/trekhleb/self-parking-car-evolution/tree/...

You may also press the "Restore Evolution" button and then press "Use demo checkpoint" to use some pre-trained data.

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!

Currently all calculations are happening in user’s browsers - no sending to the backend.

Oh, amazing. Thanks!

Have you thought about a native version? I get the appeal of writing for the browser but it's so damned slow compared to what you could get natively.

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

And then still render it in 3D, right? That's a really cool idea.

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.

Maybe you could have an option to not render all the generations and maybe only show the animation for the Nth run

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.

That was my first approach actually.

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.

I would try mapping the distance to some fixed range and still represent "no response" as infinity, e.g. you can use the sigmoid function:

nn_input = 2/(1+exp(-distance))-1

This also captures the fact that differences in small distances are more meaningful.

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

This was my first thought as well.

Well it's outperforming Tesla FSD in generation 1.

Having perfect sensors and only one task to do makes live a lot easier.

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:

https://www.kaggle.com/c/abstraction-and-reasoning-challenge

Really enjoyed this bug haha: https://github.com/trekhleb/self-parking-car-evolution/issue...

Auto manufacturers should just implement that behavior!

Reinforcement learning bots exploiting physics engine bugs has a long and illustrious history: https://arxiv.org/pdf/1803.03453.pdf https://news.ycombinator.com/item?id=16600701

Yeah, this one is fun :D Really nice catch!

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.

Fair enough. Thank you for chiming in.

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! :-)

Manual Parking: Space to brake behaves... erratically.

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.

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"?

What your describing is reinforcement learning :)

Haha, sorry I meant specifically with 3D models like the OP.

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.

It seems like the generation could be stopped after both vehicles hit an obstacle in the first second. The other 16 seconds are helpful how?

That’s a good idea.

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.

I've got "Component has crashed" on mobile Firefox, not very optimistic :)

The "Component crashed" message is most likely because WebGL isn't supported/working in that browser/device.

very cool, thanks for sharing!

all the steps are well described and the code can be used as a template for other examples

Reply on news.ycombinator.com