Self-parking Car in 500 Lines of Code(trekhleb.dev)
trekhleb.dev
Self-parking Car in 500 Lines of Code
https://trekhleb.dev/blog/2021/self-parking-car-evolution/
57 comments
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.
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.
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.
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.
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.
My concentration was embedded systems but the majority of the class were just regular CS students.
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.
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.
Like I said, the analogy isn’t perfect. However, I’d argue that rebound damping is loosely analogous to integral control, because half of it’s purpose is to control how much “pack down” you get, which is the suspension terminology for failure to return to the right steady state quickly enough. Too little rebound damping and you get overshoot, too much rebound damping, and your steady state drifts (integrates) away from nominal and your suspension performance can suffer or even fail.
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-...
https://codesandbox.io/embed/rocket-sim-final-with-position-...
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.
There are supposed to be better controllers but dang PID just work.
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.
Usually better to design the process to be controlled by a PID than the other way around.
[deleted]
[deleted]
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”.
Some espresso machines use PID to give a consistent temperature - I think I now understand better what it does based on this explanation. Thanks!
And note that if it's more than 4m from the space it has absolutely no ability to find it other than luck.
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.
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?
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.
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.
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?
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?
GAs are great. Love 'em. Same with monte carlo -- too many people dismiss these approaches and get mired in gradient-based optimization (which is far harder, more expensive, and often doesn't work any better). There should just be a rule that you have to try linear regression before building a neural network, and GA/MCSA before doing gradient optimization.
> I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial.
Well, that's definitely what I was trying to say, so we're agreed.
I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess.
> I think calling it a "hack" misses the nuance: mapping the physical metrics and telemetry into a genome is nontrivial.
Well, that's definitely what I was trying to say, so we're agreed.
I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess.
Is Monte Carlo approach (versus a gradient based approach) basically trying a bunch of different things until something works, or is it more nuanced than that (perhaps with intelligent optimization of what to try next?)?
Monte Carlo is basically taking repeated random samples until you get a good approximation of the value you're interested in. Gradient descent is more like what you describe, except you don't try "a bunch of different things" but keep trying the same thing until you have a result you think is good.
To give a silly example, Monte Carlo is like trying to guess the surface area of a dartboard by throwing darts at it and counting how many hit it, while gradient descent is like throwing darts at the board until you hit the center (or something you think is the center).
To give a silly example, Monte Carlo is like trying to guess the surface area of a dartboard by throwing darts at it and counting how many hit it, while gradient descent is like throwing darts at the board until you hit the center (or something you think is the center).
> I actually don't think GA a great fit for this problem as parking a car is a time- and circumstance-dependent process, and a fixed gene is...not. But that's a guess.
Oh definitely not! :)
Oh definitely not! :)
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.
Headline is misleading. It's "Failing to make a Self-Parking Car in 500 lines of code"
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
> Maybe you need to wait 9183718 generations before it suceeds?
Assuming you can actually detect success, that's not really that big of a problem. You can do it in 11 lines by appending:
Assuming you can actually detect success, that's not really that big of a problem. You can do it in 11 lines by appending:
for(i in 1e7){g=do-generation(g);if(worksp(g)) return g}
maybe they used a genetic algorithm to generate the headline
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.
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.
LMGTFY: https://www.youtube.com/watch?v=YZUNRmwoijw (at a guess)
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?
Does this evolution park a car only if all the other cars are in those precise spots?
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/
https://maperz.github.io/genetic-ai/
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.
120-ish seems to to be where linters will yell these days.
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
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...
[1] https://www.npr.org/templates/story/story.php?storyId=122880...
If you think the purpose is to park a car, you're missing the point.
[deleted]
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.
Can someone who is downvoting this care to enlighten a lay person like myself who just wants to know what this is all about?
To be fair to the downvoters, on the surface I appear to be whining about a headline. But what I'm actually doing is complaining about a common thread I see in the industry, where people use ML as a crutch to avoid thinking, and are frequently proud of "solutions" that don't even work despite their absurd computational expense. And for some reason, people in ML command ridiculously inflated salaries.
I'm all about using the right tool for the job. In this case, I'd say algebra, if the job is "park the car." If the job is "teach genetic algorithms with a simple example," no complaints except for the headline.
I'm all about using the right tool for the job. In this case, I'd say algebra, if the job is "park the car." If the job is "teach genetic algorithms with a simple example," no complaints except for the headline.
But if the point is to each genetic algorithms with a simple example -- is there a better simple example problem where a genetic algorithm is a more appropriate approach?
And if there's not a simple example where a genetic algorithm approach is clearly a good tactic, or if it's not straight-forward to learn to distinguish when a GA approach makes sense, is teaching GAs useful?
The point is to develop general strategies for solving a wide range of problems, not to solve any one individual problem.
[deleted]
Sure. I'm downvoting because I think the original article is an interesting and useful exposition of genetic algorithms. I don't think it intends to be the software that would run inside a self-parking car.
I downvoted because I thought that the comment's dismissive tone is not helpful, and doesn't encourage the sort of content I like to see on Hacker News. I like it when enthusiastic people make cool stuff that explains an idea well. I don't like it when commenters are incredulous that others aren't doing something the same way they would, or generally are cruel and condescending about someone else's enthusiasm. "Not impressive" is just such an unhelpful thing to say, and not what I come here for, so I downvoted.
This comment in particular seems to be a great example of "middlebrow dismissal" in the original sense from pg.
I downvoted because I thought that the comment's dismissive tone is not helpful, and doesn't encourage the sort of content I like to see on Hacker News. I like it when enthusiastic people make cool stuff that explains an idea well. I don't like it when commenters are incredulous that others aren't doing something the same way they would, or generally are cruel and condescending about someone else's enthusiasm. "Not impressive" is just such an unhelpful thing to say, and not what I come here for, so I downvoted.
This comment in particular seems to be a great example of "middlebrow dismissal" in the original sense from pg.
To those reading this who are not spenczar5, up front I'd like to apologize as it is somewhat off topic, but also somewhat relevant as this commenter is the one who inspired my reply originally.
> I downvoted because I thought that the comment's dismissive tone is not helpful
I can't help but notice though that you initially had a rather dismissive comment, which I tried to reply to so I could ask for clarity, but you had deleted it by the time I hit submit. My comment that you are responding to was initially for you.
Can you shed more light on how this dichotomy exists? Generally, if you don't care for those types of comments, you'd also not make them, which even now in your second content is somewhat derisive with the "middlebrow dismissal" even if it is a quote from pg.
> I downvoted because I thought that the comment's dismissive tone is not helpful
I can't help but notice though that you initially had a rather dismissive comment, which I tried to reply to so I could ask for clarity, but you had deleted it by the time I hit submit. My comment that you are responding to was initially for you.
Can you shed more light on how this dichotomy exists? Generally, if you don't care for those types of comments, you'd also not make them, which even now in your second content is somewhat derisive with the "middlebrow dismissal" even if it is a quote from pg.
I've rapidly deleted comments, myself. Usually because they're snarky or otherwise counterproductive. I saw that comment too, but wouldn't have responded. Better to downvote and move on... among other things, that allows folks to delete comments that don't stand a second read.
Yeah, I was irritated enough that I first made a petty comment which I immediately regretted. I don't remember the phrasing but it was something like "Sheesh, where's your article then?"
Anyway, I deleted it because I can't really defend that tone myself, and think that a downvote says enough.
I don't really understand the rest of your comment. What dichotomy are you talking about?
Anyway, I deleted it because I can't really defend that tone myself, and think that a downvote says enough.
I don't really understand the rest of your comment. What dichotomy are you talking about?
[deleted]
You are correct, of course. However, it is a unique away of introducing some GA concepts, rather than the usual "learn to walk" examples.
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!
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.
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!
I'm glad my Model S does a better job!
Love the style and use of TypeScript, especially considering the target crowd (Data-scientists)
Uhh, prob not a place to focus on elegance/hackery/vanity LOCs
https://news.ycombinator.com/item?id=28683887