Having had to code this problem for the 2005 DARPA Grand Challenge, it's fun to see this.
First, we tried Craig Reynolds' flocking system. That's a repulsive field approach. It just won't work in a narrow space. We tried a system where there's a target projected in front of the vehicle, and repulsion fields from the object act on that. The vehicle then chases the target. This was a little better, but not much.
We ended up using a system where we computed a clear path ahead of the vehicle composed of two arcs, which could have opposite curvature. We always kept enough clear path ahead for the stopping distance of the vehicle, or we'd slow down. Arcs were tested against the map by brute force, then tweaked a bit for maximum obstacle clearance. The minimum turning radius increased with speed and decreased with vehicle tilt (this was for off-road operation), so the system wouldn't generate a path that would roll the vehicle.
(Our biggest headache at the event wasn't obstacle avoidance, it was that we took DARPA's prescribed GPS boundary limits as hard boundaries. The GPS positions were not accurate enough for that. After a very frustrating first run, where we could barely make it through narrow gates because the GPS boundaries and the real world obstacles were misaligned, we allowed 1 meter outside the boundary limits, and performance improved.)
I don't know anything about neural networks or what type of work went into this, but it seems pretty easy to break.
The reversing is undeveloped and collision-detection is too basic (it looks like you're using a really small number of sensors). A car can get wedged between an angular object easily (and most times does).
As well, it seems like cars travel a set path and if gets obstructed, they get stuck trying to ram through it.
Yeah... I broke it on my first try by drawing 1 shape that they cars just proceeded to run into over and over. Upon refreshing the page, the two cars drove straight towards each other and ended up being stuck driving towards the upper-right corner constantly backing up for a bit and then running back into the corner.
My instinctive reaction when looking at the title, was, "oh, another js car learning thing, can I be bothered....?" but it's actually pretty fun. Because it's 2D it's approachable for someone like be who knows a (tiny) bit about it.
This is a great demo. But I would caution you to provide something in the initial writeup introduction that the concepts presented aren't for beginners in machine learning, and that you don't intend the following writeup to be a tutorial or anything like that.
I only say this because as I was reading it, I was looking at it from that standpoint, because on initial review, with the 2D nature and the "cartoonish" graphics (nothing wrong with that - in fact, it makes it very approachable), there is a subtle expectation that this demo might be for beginners in the field.
I continued reading, and as I read the technical background, it became quickly apparent that this was not using a simple multi-layer backprop ANN, but something seemingly more advanced, with little to go on to understand how it worked. There is enough there that an interested learner could research the topic, but I think a beginner to the topic would quickly become overwhelmed, because none of the various jargon and other terms ("hyper-parameters? what the hell are those?", I can hear such a newbie exclaiming) have been defined.
I don't believe you ever intended this to be understood or used as an introduction or a beginner's tutorial to machine learning, but because it appears like it could be, mentioning that it isn't at the beginning might be appropriate.
Furthermore, this could be an opportunity for you or someone else to create an approachable series of interactive "run-in-the-browser" javascript machine learning tutorials, starting with the basics, and culminating in something like this. Such a series would need to be planned well, and first defined what should be shown and in what order (ie - Do you discuss basics of linear algebra or probability? Do you incorporate classic ML techniques in the series along with neural networks?). Hmm - now that I think about it, I can actually envision a whole sequence of series of lessons, building from the bottom ("What is a vector?") on up...
Ultimately - I found this demo fascinating and interesting. Thank you for sharing it!
Thanks for the feedback, I really appreciate the time you took to write this! Btw. being fairly new to sites like Hacker News and Reddit, I'm actually amazed by how nice this community is.
You are right, the write-up isn't meant for newbies to the topic. I'll definitely think about updating the intro to reflect that.
Regarding the ML series: aren't there already quite a few introductory series into the topic, which can be referred to? Because the text I wrote on the project page wasn't intended to be a guide of how to build a project like this, but rather to give a glimpse of how such an algorithm might work. But anyway I must say that I really like your concept of an interactive tutorial series. Maybe I'll write a guide to a project like this in the future; would also contribute if someone else does (to anyone out there).
Welcome! I find that the HN community is generally very nice to people showcasing stuff they're worked on. Occasionally the community can be harsh, but in my experience this is usually because 1) there are some serious issues with a project (so harsh, but true), or 2) the creator of said project gets defensive or combative when presented with feedback.
I definitely hope you stick around and keep posting interesting stuff you're working on. It's one of the main reasons I'm a regular visitor, and it inspires me to keep tinkering with my own projects!
> Regarding the ML series: aren't there already quite a few introductory series into the topic, which can be referred to?
I agree with the earlier poster that upon seeing what you did I kind of expected a tutorial explaining how to get there. I don't think you'd have to provide such a tutorial, of course, but I think setting expectations and ideally even linking to good 'introductory series into the topic' would be very much appreciated.
Personally I like to be presented with some end result that might take quite a bit of work to recreate. Being frustrated upon realizing that there's quite a bit of work ahead works well for me. But I especially love it when I'm given some gentle pointers towards next steps, so for me at least adding such pointers would make your article/demo even better.
For example: I had been interested in this 'lisp' thing for a while. I'd read a few short articles explaining the basics and why lisp is cool and so on, but I never dove in.
Then, one day, I read an article that presented some (relatively) idiomatic code in js/python/ruby/I don't remember, and a much shorter equivalent in, iirc, Clojure. The latter made no sense to me, but I was so curious about what was going on, that I continued reading the rather long article.
After finally vaguely understanding what the Clojure code was doing, I was so excited that I immediately went on and spent a few weeks tinkering with Clojure. Somehow, for me, it took a `look at what you'll eventually be able to do` type article to tickle me in the right way to actually sit down and bother learning clojure.
Love the demo, good work! However my cars got stuck in a fairly "stupid" way, both in the same place, when I tried to break their usual path. Maybe too low exploration / exploitation ratio?
About the series: there are quite a few of those around, but most of them are difficult to follow for the mathematically challenged. So, can you explain it without needing to include mathjax.js? If so, you would definitely stand out. :)
I played around with it and created an oval track, but the car isn't learning it very well. Every loop around it gets caught on this one part, but it has plenty of room. The other car got stuck completely and can't move (I guess there is no reverse). I let it run for about 20 minutes but will let it go longer and see what happens.
This is super awesome! I had a lot of fun with this, and the visualization was simple and enjoyable to follow along.
I think I found a small bug: cars don't seem to have much ability to estimate the size of a gap between obstacles, so they'll attempt to squeeze through gaps that are too small for them.
I just have to ask if someone knows:
Is there any benefit to doing this in WebGL? Does that enable you to use the GPU for other calculations than the graphical ones?
(I really don't know anything about GPUs, so sorry if that's a naive question).
Yep, you can implement your calculations as shaders, which I bet is really useful for matrix multiplication and doing stuff in parallel. That and better graphics performance.
For example, you can't match the performance of this Game of Life implementation with Canvas2d.
http://glslsandbox.com/e#207.3
The map doesn't change on page reload, and I'm guessing you didn't change it while training. Doesn't that mean these cars are trained only for this map?
Surprisingly, they seem to successfully avoid user-added obstacles.
That's a good question. While training I have changed the obstacles, which means the cars can adapt to any map. The map you see on the published page is just there on page reload to make it easier for everyone to actually see the cars in action.
This is great, and timely, as I'm making basically this in meatspace (an RC car with distance sensors in front). It'll be very useful to see how the ML part can work.
First, we tried Craig Reynolds' flocking system. That's a repulsive field approach. It just won't work in a narrow space. We tried a system where there's a target projected in front of the vehicle, and repulsion fields from the object act on that. The vehicle then chases the target. This was a little better, but not much.
We ended up using a system where we computed a clear path ahead of the vehicle composed of two arcs, which could have opposite curvature. We always kept enough clear path ahead for the stopping distance of the vehicle, or we'd slow down. Arcs were tested against the map by brute force, then tweaked a bit for maximum obstacle clearance. The minimum turning radius increased with speed and decreased with vehicle tilt (this was for off-road operation), so the system wouldn't generate a path that would roll the vehicle.
(Our biggest headache at the event wasn't obstacle avoidance, it was that we took DARPA's prescribed GPS boundary limits as hard boundaries. The GPS positions were not accurate enough for that. After a very frustrating first run, where we could barely make it through narrow gates because the GPS boundaries and the real world obstacles were misaligned, we allowed 1 meter outside the boundary limits, and performance improved.)