Learning to Program Google’s Driver-Less Car

A few months ago I took a course on how to program a robotic automobile, Artificial Intelligence for Robotics. This course is taught by Sebastian Thurn, who heads the Google X Lab and the Google Driverless Car Project. Thurn also founded the educational organization, Udacity, that is offering this and many other free computer science and math courses.

Recently, I decided to port the code I wrote to Java and use the excellent Processing visualization library to illustrate some of the core concepts. My code is hosted on GitHub: https://github.com/stevepepple/car-robot. It a separate post, I’ll consider how this code would work in a real car. In short, a real robotic car (like Stanford’s award-winning cars Junior and Stanley) uses a map of its environment and Global Positioning System; optical/LIDAR, laser, radar, and inertia sensors; and– of course– an central, on-board computer that gathers data from the car’s sensor and controls steering, acceleration and braking.

Localization

The first step in programming a robotic car is how to locate the car within its environment. This is called localization. You can never know for sure where the car is at. Even the best global positioning system will have a margin of error within a few meters, which is not acceptable on the road. Yet, there are several localization techniques that provide us with a strong belief, statistically speaking, of where the robot is located.

The following histogram (Histogram.java in my code) shows a simple example of localization in a one-dimensional world. Each step in the graph represents the robot’s belief about it’s location. Before the robot has moved or tried to determine its location, there is an even probability distribution. The robot will then sense its location based upon a map of landmarks or other real-time observations. The belief for each part of the graph is normalized so that the total probability across steps is equal to one.

localization

Filters and Bayes Theorem

Having a robot deterministically navigate a maze is rather simple, the real challenge presented in this course is how a robot can deal with uncertainty. There are several approaches that apply Bayes rule and other probabilistic methods that help the robot determine the location of landmarks, obstacles, other vehicles, and itself. A Kalman filter is one such method that allows a robot to continuously track the position of objects in it’s environment. The Kalman filter stores measurements as two-dimensional gaussian distributions and uses these values to estimate the current state of the environment and predict how surrounding objects will move.

Another useful technique, which is a central part of my final implementation, is a particle filter. The robot uses a particle filter to determine its location and proximity to obstacles. A particle filter creates thousands of copies of the robot and randomly distributes these copies over the grid. In essence, these particles travel along with the actual robot and makes the same measurements and calculations for each particle. The robot takes an mathematically-involved average of all of the particles and the particles are given an importance weight based on their proximity to the robot’s location, landmarks, and obstacles. Each time the robot moves these particles are re-sampled and reduced. The average of the reduced particle set gives the robot a much improved estimate of its location.

particles and motion

Planning

Algorithms that are often used for the routing of network data are also well-suited for creating a robot’s driving plan.

A shortest path algorithm will spider over all of the available paths and calculate the least number of steps required to arrive at the goal. Other algorithms, such as the Dijkstra or A* search pattern, use heuristics and/or policies at each point to decide upon which direction to search. A* thereby eliminates paths that are further away from the goal. Once A* finds the shortest route, this path can be reduced to a single continuous path. (During A*, I kept a updated policy and history of action of the actions taken.)

However, this path may be too tight for a car to navigate, so the robot needs to calculate a smoother path. The model used for my car simulation is quite simplistic. The car can set its speed, steering, and heading direction. It goes as speeds between 20 and 40 mph. It can steer left or right at a 45 degree angle. If the path is not smooth enough, the robot cannot stay on track and tends to oscillate back and forth away from the desired course. For the simulation, I added noise to the car movements and sensors. It’s quite fun to play with these values and see how the robot will behave under different conditions.

Example of the shortest path and A* algorithms with path smoothing.
Example of the shortest path and A* algorithms with path smoothing.

Robot Controller

The remaining part of the robot that I must discuss is the PID (proportional-integral-differential) controller.

The controller will use the smooth path found by the planning algorithms to move. As the car moves, its controller calculates the error between the path and its estimated location. The proportional component steers in proportion to the path, adjusting according to the current error; The differential component prevents the proportional controller from over-steering and overshooting the smooth path by easing these proportional steering adjustments; The integral component tries to account for system”bias” over time. For instance, a real car hardware degrades and may not steer as well as it used to or it’s sensors may become more prone to error. The integral controller will help to account and correct for this sustained error over time.

All this said, here’s a video of my robot in action!

Demo of My Driverless Robotic Car from steve on Vimeo.

Advertisements

70 thoughts on “Learning to Program Google’s Driver-Less Car

  1. When I initially commented I appear to have clicked on the -Notify me when new comments are added- checkbox and from now on every time a
    comment is added I receive 4 emails with the exact same comment.
    There has to be a means you can remove me from that service?
    Kudos!

  2. I want to to thank you for this very good read!!
    I certainly enjoyed every little bit of it. I have you book-marked to check out new things you post…

  3. Someone essentially help to make critically posts
    I’d state. That is the first time I frequented your website page and to this point? I amazed with the research you made to make this actual publish incredible. Great process!

  4. I was curious if you ever thought of changing the page layout
    of your site? Its very well written; I love what youve got to say.
    But maybe you could a little more in the way of content so people could
    connect with it better. Youve got an awful lot of
    text for only having one or two images. Maybe
    you could space it out better?

  5. Hello! I know this is kind of off topic but I was wondering which
    blog platform are you using for this site?
    I’m getting fed up of WordPress because I’ve had problems with hackers and I’m looking at options for another platform. I would be great if you could point me in the direction of a good platform.

  6. Unquestionably believe that that you said. Your favorite
    reason seemed to be on the internet the simplest factor to take note of.
    I say to you, I certainly get irked even as other people consider
    concerns that they plainly don’t know about. You managed to hit the nail upon the top and outlined out the entire thing without having side-effects , people can take a signal. Will likely be again to get more. Thank you

  7. Hi, Neat post. There’s an issue along with your site in internet explorer, might check this? IE nonetheless is the marketplace leader and a huge section of folks will omit your wonderful writing due to this problem.

  8. With havin so much content and articles do you ever run into any issues
    of plagorism or copyright violation? My website has
    a lot of exclusive content I’ve either authored myself or outsourced but it looks like a lot of it is popping it up all over the internet without my permission. Do you know any methods to help stop content from being stolen? I’d certainly appreciate
    it.

  9. I loved as much as you will receive carried out right here.
    The sketch is attractive, your authored subject matter stylish.

    nonetheless, you command get got an edginess over that you wish be delivering the following.
    unwell unquestionably come more formerly again as exactly
    the same nearly very often inside case you shield this increase.

  10. I think this is among the most vital info for me. And i’m glad reading your article.
    But wanna remark on few general things, The website style is wonderful, the articles is really excellent :
    D. Good job, cheers

  11. Excellent pieces. Keep writing such kind of information oon your
    site. Im really impressed byy it.
    Hello there, You’ve performed an incredible job.
    I will certainly digg it and in my opinion recommend to my friends.
    I’m confident they’ll be benefited from this web site.

  12. I have been exploring for a little bit for any high-quality articles or blog posts on this sort of space .
    Exploring in Yahoo I ultimately stumbled upon this website.
    Studying this information So i am satisfied to
    exhibit that I’ve a very excellent uncanny feeling I came upon just what
    I needed. I most without a doubt will make certain to do not overlook this website and give it a look on a continuing basis.

  13. Hello there! I know this is somewhat off topic but I was wondering if you knew where I could get a captcha plugin for my comment
    form? I’m using the same blog platform as yours and I’m having difficulty finding one?
    Thanks a lot!

  14. Good day! I know this is kinda off topic however ,
    I’d figured I’d ask. Would you be interested in exchanging links or maybe guest
    authoring a blog post or vice-versa? My website covers a lot of the same
    subjects as yours and I feel we could greatly benefit from each
    other. If you are interested feel free to send me an e-mail.
    I look forward to hearing from you! Great blog
    by the way!

  15. These are just some situations that can endanger the
    lives of people and these can be avoided if professional contractors
    are tasked to do the job as they are equipped with protective
    gear. So here are a few tips that could be helpful
    to start with. Communities can make great strides in
    going green by reducing their carbon footprint.

  16. Now you are sure that the answer to this question, make sure you look
    at the real estate rules in your state for the final percentage.
    An evidence of your respective secure income source along with your capability to pay to
    the monthly installments in the course in the loan is exactly what
    the bank is searching for. Fixed residential investment negatively contributed to GDP [PDF] inside
    fourth quarter for that very first time since third quarter of 2010.

  17. How to Get the Best Lawnmower Repair In Huntersville

    Purchasing home furnishings for home is not an expensive task today if folks have full understanding of every
    aspect of it. Furniture units are brought after long wait and
    so it becomes vital to produce the best possible deal.

    Three most popular and durable timber types with which furniture are crafted are pine furniture,
    oak furniture and ash furniture. These are most commonly used materials as a result of immensely amazing features delivered by them.

    One of the favorite honest home based companies right this moment is performing special
    attractions videos. If you like as a persons vision behind it camera and have anyone to use, you might wind up trading tomorrow.
    Seriously, bring to mind each of the special attractions
    in people’s lives that they’d like to own on video.
    Weddings, marathons, club events, Little League games, retirement dinners, family reunions are several gatherings that searchers want on video.
    You can probably consider tons more. Which is good if you select
    this since the honest home-based business for you.

    Knowing how to employ a mower safely can be a function of wise practice and
    the machine-specific information in the user manual.
    The first step to safety (and also this is not over-emphasised)
    is to read and continue with the manufacturer’s instructions.
    Reading the manual may also present you with important
    information about caring for your lawnmower, protecting ignore the and taking advantage of
    its features to the full. The following principles sign up for all mowers:

    Rather than the usual moped, or scooter, or possibly a conventional motorcycle, the Honda 50 had an unconventional female-friendly step through frame,
    plus a clean and quiet engine. Other features of the 50 included molded-polyethylene body parts, seven-inch wheels and tires, plus an automatic clutch that enabled it
    being ridden one handed. The 50’s single-cylinder overhead valve engine made 4.5
    hp, which motivated the 143 lb. bike to go up into to 43 mph.
    The $249 two-wheel ride delivered over 200 mpg.

    In the riding mower segment of mowers Toro is among the leaders.
    A strong reason meant for Toro mowers is because they need only the light source renovating every now and again.

    One important maintenance service required for Toro lawnmowers is lubricating the mower’s idler bearing,
    spindle bearings as well as steering controls. Continue to lubricate each
    component with all the correct lithium complex once every use.
    If you need to grease your Toro mower, then abide by these steps:

  18. Thanks for ones marvelous posting! I really enjoyed reading it, you are a great author.I will always bookmark your blog and may come back at some point.

    I want to encourage one to continue your great work, have a nice evening!

  19. I’m excited to discover this web site. I need to to
    thank you for ones time just for this fantastic read!! I
    definitely liked every little bit of it and I have you bookmarked to look at new information on your website.

  20. Which ensures that actually, prior for a start you’ll see the noticeable
    process of getting older on our own skin. Using products containing collagen will not benefit your skin.
    We all get a little older daily where there isn’t a single thing you’ll be able to do to prevent it.
    Seeds will also be included the actual nut category for the identical reasons as nuts.

  21. Edmonton Scrap Metal, General Scrap Metal Edmonton, Scrap Metal
    Edmonton, Scrap Metal Recycling Edmonton Scrap Metal Recycling Edmonton Sanford & Sons Scrap
    Car Hauling Alberta 780-604-4470 – We pay top $$$ for all all types of autos dead or alive, car & truck batteries

  22. Superb blog! Do you have any tips and hints for
    aspiring writers? I’m hoping to start my own website soon but I’m
    a little lost on everything. Would you recommend starting with a free platform like WordPress or
    ggo for a paid option? There are so many options out there that I’m totally overwhelmked ..
    Any tips? Many thanks!

  23. This doesn’t only include security systems or life line type call systems.
    Some people just worry and worry, without ever finding a approach to overcome the difficulty
    and move forward. Many mistakenly believe they’ve got to sustain a war injury so that you can qualify.
    You’ll both determine what to expect from the other person, and you also’ll know how
    advisable to contact each other.

  24. hey there and thank you for your information – I’ve certainly picked up
    something new from right here. I did however expertise a few technical issues using this site, as I
    experienced to reload the web site a lot of times previous to I could
    get it to load correctly. I had been wondering if your
    hosting is OK? Not that I am complaining, but slow
    loading instances times will very frequently affect your placement in google and could damage your quality score if ads and marketing
    with Adwords. Well I’m adding this RSS to my email and can look out for
    much more of your respective intriguing content.
    Ensure that you update this again very soon.

  25. I enjoy you because of your own labor just for this site. My daughter really loves setting aside time for internet research and it’s easy to understand explanation why. We know all the relating to the powerful mode an individual produce efficient strategies via your website and as well as inspire response right from other individuals about this matter and our own girl is undoubtedly studying so much. Have fun with the rest of the new year. Your carrying out a remarkable occupational.

  26. I have been surfing online more than 3 hours today, yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my view, if all site owners and bloggers made good content as you
    did, the web will be a lot more useful than ever before.

  27. It is the best time to make some plans for the future and it is time to be happy.

    I’ve read this post and if I could I want to suggest you few interesting things or suggestions.
    Maybe you can write next articles referring to this article.
    I desire to read even more things about it!

  28. I would really recommend to check this minecraft seed out since it contains what you would expect in a survival island type seed.
    This past weekend, 4J Studios featured a sale discounting most skin and texture pack offering that have released thus
    far for the Xbox 360 version of Minecraft. I generally start digging from within my
    house simply to prevent mobs from dropping down on me.

  29. It’s a shame you don’t have a donate button! I’d definitely donate to this excellent blog!
    I suppose for now i’ll settle for book-marking and adding your RSS feed to my Google account.
    I look forward to brand new updates and will share this website with my Facebook
    group. Talk soon!

  30. I’m amazed, I must say. Rarely do I come across a blog that’s equally educative and interesting, and let me tell
    you, you’ve hit the nail on the head. The issue is something too few men and
    women are speaking intelligently about. I’m very happy I stumbled
    across this during my search for something regarding this.

  31. What i do not understood is in fact how you are not actually a lot more neatly-preferred than you
    may be right now. You are very intelligent. You know therefore considerably
    on the subject of this subject, made me in my
    opinion imagine it from numerous various angles. Its like women and men don’t
    seem to be involved except it is something to do with Lady gaga!

    Your own stuffs nice. Always deal with it up!

  32. What’s up it’s me, I am also visiting this web site regularly, this site is truly
    pleasant and the viewers are truly sharing good thoughts.

  33. Good day! Do you use Twitter? I’d like to follow you if that would be okay.
    I’m definitely enjoying your blog and look forward to new updates.

  34. I am extremely inspired along with your writing talents and also with the layout in your weblog.

    Is this a paid theme or did you customize it
    yourself? Anyway keep up the nice high quality writing, it is
    uncommon to peer a nice blog like this one today..

  35. I think this is one of the most vital info for me.
    And i’m glad reading your article. But should remark
    on few general things, The web site style is
    perfect, the articles is really nice : D. Good job, cheers

  36. Wonderful goods from you, man. I’ve understand your stuff previous to and you are just extremely fantastic.
    I actually like what you have acquired here, really like what you’re stating and the way
    in which you say it. You make it entertaining and you still care for
    to keep it sensible. I cant wait to read far more from you.

    This is really a great website.

  37. Pretty section of content. I just stumbled upon your web site and in accession capital to assert that I get actually enjoyed account your blog posts.
    Any way I will be subscribing to your feeds and even I achievement
    you access consistently rapidly.

  38. Good day! This is my first visit to your blog! We are a team of volunteers and starting a new initiative in a community in the same niche.
    Your blog provided us beneficial information to work on. You have done a
    marvellous job!

  39. This is the right web site for anyone who wants to understand this topic.
    You know a whole lot its almost hard to argue with you (not that I
    actually would want to…HaHa). You definitely put a new spin on a
    subject that has been written about for decades. Excellent stuff, just excellent!

  40. I don’t even know how I ended up right here, however I believed this publish was once good.
    I don’t recognize who you are but definitely you’re going to a well-known blogger if you
    aren’t already. Cheers!

  41. Build the site with Site – Builder and choose the Hosting
    package:. There are lots of video converter software products available
    on the market for you the consumer to select from.
    Many functions provided by plugins can be replicated manually through individual actions in Photoshop or other programs.

  42. This package is accessible in your nearest general store or instrument shop, and getting acclimated to this software is step one in the direction of mastering Handicraft
    talent, so it is imperative that you do not really feel worry
    or hesitation on utilizing this device. The second thing requrred fot the Handicraft talent
    is the set of materials that differ depending on the merchandise that’ll be made.

  43. An impressive share! I have just forwarded this onto a co-worker who was conducting a little homework on this.
    And he in fact bought me breakfast simply because I found it for him…
    lol. So allow me to reword this…. Thanks for the meal!!
    But yeah, thanks for spending some time to discuss this issue here on your site.

  44. Understanding both advantages and disadvantages are important in order to
    choose the best internet marketing strategy. A VPN creates an encrypted
    connection to a third-party server, and all your Internet traffic
    is routed through that server. A internet
    marketing business, in a nutshell, a business that’s designed to run on the internet
    via a website.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s