Self-parking Car in 500 Lines of Code

https://trekhleb.dev/blog/2021/self-parking-car-evolution/

by maydemir • 5 years ago

239 51 5 years ago

mrb• 5 years ago

None of the animations show a successful parking manoeuvre, because the code is unable, after 40 generations, to produce a car that actually successfully parks itself. How long does it take to go through 40, 80, 120 generations?

diskzero2• 5 years ago

Probably longer than most would find acceptable! I did some work with genetic algorithms about twenty years ago and the author mentions some of the optimizations that could be done to improve performance.

timr2• 5 years ago

There's no fixed answer, because "a genetic algorithm" is not one thing -- it's an optimization process, and the details of how you model your problem matter at least as much as (if not more than) the optimization process you use.

In this case, the mapping of a complicated multi-step process involving external constraints to a "gene" is going to be a hack, no matter what you do.

SavantIdiot2• 5 years ago

Genetic algorithms work well in some circumstances, I recall that multi-band antenna design technology experienced a step-function boost in the 90's due to application of GA principles, which helped the cellphone market boom. (I could be mixing up two IEEE articles in memory.)

I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial.

Plus 40 generations is no where NEAR enough. A GA needs millions (or billions) of generations to avoid local minima/maxima. Especially given the size of the input vector. His vector is what, 2^100 states?

gowld2• 5 years ago

Headline is misleading. It's "Failing to make a Self-Parking Car in 500 lines of code"

nqzero• 5 years ago

maybe they used a genetic algorithm to generate the headline

cjohansson2• 5 years ago

Maybe you need to wait 9183718 generations before it suceeds? Like I do a random code generator in 10 lines and say it can solve any problem in the world if you wait long enough

codyogden• 5 years ago

Discussion from when this was posted on Show HN a couple weeks ago.

https://news.ycombinator.com/item?id=28683887

klyrs4• 5 years ago

You need 500 lines of code for that??? Oh, because you're using a genetic algorithm that doesn't start with a good plan. It would be much simpler to find a very small number of parameters for a templated piecewise linear function. No training cost, should only be a few lines of code: this is solvable through straightforward algebra, no guesswork required [1]. Love the visualization, though.

[1] https://www.npr.org/templates/story/story.php?storyId=122880...

SamBam• 5 years ago

If you think the purpose is to park a car, you're missing the point.

klyrs4• 5 years ago

I think there's a time and place for genetic algorithms: heuristics to solve genuinely hard problems. This problem has a known, polynomial-time algorithm. If the headline was "An easy primer to genetic algorithms" then I'd agree with you. But it's "self-parking car in 500 lines" -- not impressive.

diskzero2• 5 years ago

You are correct, of course. However, it is a unique away of introducing some GA concepts, rather than the usual "learn to walk" examples.

blowski• 5 years ago

That link seems to cover only whether it's possible for you to park in a given spot, whereas the OP's link covers when and how far to turn, bumping against cars parked opposite, etc. You'd need a lot more variables for that!

aborowie• 5 years ago

Wow - this is a great read, reminds me of the guy on YouTube that used a genetic algorithm to evolve wind turbine blades which outperformed traditional ones.

AlexanderTheGr8• 5 years ago

the wind turbines thing is fascinating. Any chance you have a link for that? I would love to see the source code, if that guy shared that.

willbw• 5 years ago

LMGTFY: https://www.youtube.com/watch?v=YZUNRmwoijw (at a guess)

jakear2• 5 years ago

A good demonstration of the perils of Proportional-only control -- if the only input to the system is only the instantaneous distances to obstacles, the car can't make any decisions that take into account its momentum. This means it's destined to overshoot the target, as we see in the demos.

Consider: if you were given a freeze-frame view of the car in the exact right spot, what controls would you send it to keep it there? It'd be impossible to say without knowing the car's velocity - if the car was in the process of reversing, it should apply forwards acceleration to come to a stop, but if it was in the process of going forwards it should apply reverse acceleration.

The solution is to add Derivative control. This would look like a second set of inputs to the system comprised of the difference between the current measurements and the prior ones.

dahart2• 5 years ago

Yup. And an integral term too. Writing racing AI for a video game is exactly why I ran into PID controllers (Proportional-Integral-Derivative). If you steer only in proportion to error, not only will you overshoot, but it’s super easy to get into a divergent state where the overshoot gets bigger with each turn. The very surprising thing from an intuition perspective is that if you dampen the proportional term, the instability only gets worse!

When this happened on my job, I was very surprised that I hadn’t heard of PID controllers in CS school. They’re standard in other kinds of engineering.

There are often better variants and alternatives to a basic PID controller, but I’m quite partial to the core idea - the three terms in the PID controller are analogous to car/bike suspensions. It’s a unitless suspension system for sensors & data. Spring rate is like your proportional term, and compression damping and rebound damping are like the derivative and integral terms. This analogy ain’t perfect, but I dig the concept.

learc83• 5 years ago

I took a class in my CS program where we had to write PID controller software running on a microcontroller to keep water at a specific temperature using a hot plate.

My concentration was embedded systems but the majority of the class were just regular CS students.

jakear2• 5 years ago

I’m not aware of an analog for Integral control in standard bike/car suspension. Integral control is steady state loss minimization, and the precise steady state position isn’t a big deal for most suspension systems. An exception could be “air ride” suspensions, where once the driver has “keyed in” a 1’ clearance target, the car could adjust the air levels to maintain that despite changes in load (person gets in, car drops due to gravity, air pressure increases until 1’ clearance is regained). I am not sure if this is how such systems work in practice.

But yes, I couldn’t imagine a CS education without controls. My intro CS class in college explored controls in some depth and I took a follow up class. Some of the most incredible things I’ve created were control systems, and it’s one of the primary classes I think of when people ask about the merits of a college education.

polishdude20• 5 years ago

I've actually used a PID controller on my thrust vectoring rocket (actually there are two controllers, one for each axis). I made a sim to try and find the correct PID terms needed before flight :

https://codesandbox.io/embed/rocket-sim-final-with-position-...

mr337• 5 years ago

Same, also amazing how simple it is to implement a PID controller and how well the results are. I use them all the time for computer mechanical control interfaces.

There are supposed to be better controllers but dang PID just work.

Gibbon1• 5 years ago

What one of my book on process control said was anything 'better' than a PID controller needs to be carefully matched to the process being controlled. That involves some sort of model which then needs to be accurately match what's happening with the process. That itself is hard.

Usually better to design the process to be controlled by a PID than the other way around.

LorenPechtel• 5 years ago

And note that if it's more than 4m from the space it has absolutely no ability to find it other than luck.

quickthrower22• 5 years ago

In real life if you are more than 4m from the space, someone else has taken it. The real AI challenge is to automate the yelling at the person who took your space.

xixixao• 5 years ago

We used PID in our robotics class (for driving). But I was dismayed how little literature there was on the topic. From my research back then “the details are closely guarded company secrets”.

quickthrower22• 5 years ago

Some espresso machines use PID to give a consistent temperature - I think I now understand better what it does based on this explanation. Thanks!

leroman• 5 years ago

Love the style and use of TypeScript, especially considering the target crowd (Data-scientists)

tomxor• 5 years ago

I'd like to see this working in the UK, where you are regularly expected to squeeze into spaces with <1ft either side, sometimes much less!

douglee650• 5 years ago

Uhh, prob not a place to focus on elegance/hackery/vanity LOCs

kwhitefoot• 5 years ago

I'm glad my Model S does a better job!

ghastmaster• 5 years ago

I often see the term "line" used as a metric. When screens were limited to a certain number of characters in the early days this meant something. Is there some current limit to the length of a line that would make this useful? Bytes/Characters seems more appropriate.

bubblesorting• 5 years ago

120-ish seems to to be where linters will yell these days.

cjohansson2• 5 years ago

I think what is usually meant is one expression or statement per line. Any editor get problems when you have lines that are a few MBs each

ItsMonkk• 5 years ago

Wonder if it makes sense to have two goals, one being the traditional 'drive slightly past then reverse into' spot, and the other being the result.

maperz• 5 years ago

Reminds me of a similar project i did trying to teach robot AI to jump over boxes. Always impressive to see how easy it is to get quick results with a bare implementation of genetic algorithms:

https://maperz.github.io/genetic-ai/

joezydeco• 5 years ago

I don't see how the other cars are randomized at all.

Does this evolution park a car only if all the other cars are in those precise spots?

Self-parking Car in 500 Lines of Code

Related Stories