29 August 2012

How GoogleLimo Punts

The Anti-Planner | Randal O'Toole | Toodling Around DC in the Google Car

As we threaded through downtown DC traffic, he noted that the car relies on GPS for only the most general purposes. Mainly it relies on the information it senses and its built-in knowledge of the area. For example, Google programs the location and height of every traffic signal the car might encounter so it knows where to look for the signals.
This is astounding to me. It goes against every bit of CS education I've received. It's audaciously clever in its very stupidity.
          JAN 2013
 Su   M  Tu   W  Th   F  Sa
--- --- --- --- --- --- ---
          1   2   3   4   5
  6   7   8   9  10  11  12
 13  14  15  16  17  18  19
 20  21  22  23  24  25  26
 27  28  29  30  31

          FEB 2013
 Su   M  Tu   W  Th   F  Sa
--- --- --- --- --- --- ---
                      1   2
  3   4   5   6   7   8   9
 10  11  12  13  14  15  16
 17  18  19  20  21  22  23
 24  25  26  27  28

Let me rewind. Back when I first started learning to program, about age 12 or so, one of our class assignments was to write a program that would print an annual calendar given the day of the week of January 1st, like the one to the right. (The follow-on assignment was to figure out that day of the week yourself, which I think is a good interesting problem.)

One student decided that since there were only 14 possibilities (because of leap years) he would just type all 14 calendars in himself, by hand, and have the program print the correct one.

He contended he deserved full credit, because it worked. But it went against the entire spirit of the exercise. Why have a computer program if you're going to do all the work yourself for it? Yes, it works. But it has no elegance. It's ugly. The point is to get a machine to calculate things for you, not to calculate things yourself and have the machine parrot them back to you.

The next fifteen years of programming & computer science has been no different for me: you don't just want a solution, you want an elegant solution. Maybe one time in a hundred the best decision is to step back and hack together an ugly, ad hoc solution. But even in those circumstances your're only putting yourself in the hole. Even in those 1% of cases, half the time that technical debt you incurred is going to have to be repaid in the future, with interest.

Let me illustrate with another story from my CS education. We once had an assignment to write a function which calculated the log of a number to five digits. One kid took a short cut and copied a table of logarithms into his program. It took him about 10 minutes to get this set up, while the rest of us worked considerably longer. That's all fine and well, until the prof saw his cheeky solution and assigned us the next problem: calculate the log to an arbitrary number of digits. Those of us who did things the right way the first time around needed about 20 seconds to modify our programs, while he had to start from scratch. You don't want elegant solutions for the sake of elegance: you want them because they pay off in the long run.

Google threw all that out the window here. Figuring out where the traffic light for your lane is on the fly using computer vision is hard. Very, very hard. (For one thing, computer vision is (almost universally) inherently probabilistic, and concluding that there's a 97% chance your lane's light is green does you absolutely no good at all.) But you know what Google is good at? You know what's an easy — indeed, already solved — problem for them? Driving all over hither and yon, recording data, and putting it in a giant look-up table. That's what Street View is, after all. So they took a look at this hard vision problem and said "screw it; let's just do it the ugly way."

I'm simultaneously scandalized that Google punted on the problem of determining where street lights are, and very impressed at the simplicity of their work-around. They're saying, "We'd rather have something that works the way it's not supposed to than something that doesn't work at all." That's a decision that goes against all my instincts, but it's also the right decision.

PS I have worries that this traffic light location database will be a devil to keep up-to-date, but I have a sneaking suspicion that the very vehicles that need it to be accurate can be leveraged to keep it accurate, so that may not be such a big problem in the long run.


  1. Heck - that could be a task for the non-driver: if the car can't find the traffic signal, it just flashes a big red light on the interior, which tells the non-driver point a swivel-mounted camera at his lane's traffic signal. After a few passes through that intersection, it's been remapped.

  2. I'll only be fully satisfied when my RoboCar will let me literally be asleep at the wheel, but this is still a good idea.

    Maybe you give a discount on the car to people who are willing to help with this sort of data collection.

  3. Meh. It'll be at least a decade before anyone is comfortable sleeping in their robo-car - this will give the paranoiacs something to do in the meantime.