Fri 13 Nov 2009
As most people who read the iSchool's mailing lists know, I got pretty excited about the DARPA Network Challenge. If you haven't heard, it's a competition in the spirit of the DARPA Grand Challenge. The idea is that on a particular day in December, for a few hours only, DARPA will fly 10 large red weather balloons in 10 different locations, somewhere near a road, somewhere in the US. The challenge is to find them all. Sounds easy, right?
I like what DARPA is thinking here. We know that internet-based tools have helped people coordinate massive jobs on the fly. The best recent examples of collective efforts enabled by the internet were the searches for Jim Gray's lost sailboat and Steve Fosset's downed plane. Unfortunately, neither search turned up anything. Both of those examples were a carpet bombing approach. We all had one job: search satellite photos for clues. This challenge is a little different, but much more like the kind of thing we might want to mobilize for nationally in response to crisis. Those balloons could be anywhere. They'd be hard to spot. And depending on how hard DARPA wants to make this thing, a good portion of them are likely to be stationed in rural America. Since they announced the challenge a few weeks back, DARPA has updated the rules to say that if no one finds all 10 they'll give out the prize to the first team to find at least 5. This tells me it's going to be hard. Awesome!
The web is full of commentary on this, and I'm repeating a lot of it. Here's a quick review of very dumb ideas, ranked in order to dumbness.
- Send people out looking. Some people think the answer to this is to get a big group of people to drive out looking for these balloons. It seems rational on the face of it, like DARPA planned a big game of hide and seek. But this is very dumb. No group will be large enough to cover the necessary ground in time. Ryan's back of the envelope calculation:
To aid with calculations, according to the CIA World Factbook there are 2,615,870 miles of paved roads in the U.S. If we assume that DARPA only considers 80% of those roads eligible for this challenge, and an average speed of 45MPH, it would take 46,500 hours to travel those roads, which is just under 2000 (person-)days. So how many people do you need in order to scout out all this terrain?
- Offer a cash bounty and watch the tips roll in. Many teams think this will be won by offering to split the winnings amongst people who submit the locations of balloons. Nuh uh. First of all, we have a repeat of problem one above: how are people going to find these things, by driving around looking? Second, who is going to go driving around on the basis of a cut of the $40,000 prize? The problem with that is most people would view it like a lottery: you'll give me $3,000 for submitting the balloon location if I find it, but the chances that our team will win are so small anyway. Offer cash prizes and a very small group of committed people might be motivated to go driving around, but you won't get very far with that.
- Look at satellite photos. Again, this sounds smart on the face of it, but it's not. This blog post on the subject puts it nicely:
The very best resolution you’ll realistically get is 1.6 ft, meaning an 8ft red balloon will take up about 19 pixels. That’s not bad, but that’s only under ideal conditions, so if you’re trying to automate the process of finding those 19 pixels with computer vision, you’re going to get a lot of false positives (see below).
To that add the issues of weather (clouds make balloons hard to see from above) and cost (it would be way more than $40k). You might imagine a collective effort like the Jim Gray search, but good luck getting enough people to care about this.
- Data Mining. Armies of computer scientists read about this problem and started to design their Twitter crawlers to look for the inevitable flood of 'OMG WTF Red Balloon?' messages. This is the least dumb of the dumb ideas because they will actually find some balloons this way. It's a tiny fraction of people who know about this DARPA challenge, but there are plenty of people who might be curious about a giant red balloon in their neighborhood. But let's not get too carried away. This is still dumb. Reason: there are only like 12 people in the US who use Twitter. Ok, I'm exaggerating (a lot) for effect. But the point is, it's a small fraction of Americans who use Twitter and, more importantly, they mostly live in about 3 cities. Check out this beautiful NY Times visualization of Twitter usage during the Superbowl in Feb. Now try to estimate the fraction of the country in which there were no Tweets at all… Roops.
How to Win
So, as much as I like to critique other people's ideas, I'd like to offer my own opinion on how to win this challenge.
- Forget cash. Splitting up the prize money will do no good. If you're going to motivate people to help with the challenge, it's going to be based on non-monetary, social psychological incentives. In other words, they're going to help because they're interested, because they think it's fun. So…
- Focus on the hard to find balloons. I'm guessing somewhere between 3-6 of the balloons will be stationed in social media dense areas, so a lot of people will find them in the first few hours, and they'll be a lot of easy to spot chatter about it on Twitter and Facebook. So figure on someone else finding those, and worry about the balloons in that vast swath called middle America.
- Harness the people who are out anyway. We can develop as many sophisticated motivational schemes as we want. We can donate the money to charity or get a major celebrity to mobilize people. We can design games with prizes and achievements and badges. Yay! The problem is that it's still a lot to ask of people to go driving around. So, why not get the people who are out driving anyway? Partner with trucker organizations. Get road trippers and cops. These are people who are driving anyway, so all the incentives have to do is get them to report in. Reporting and verification will still be an issue. So is communication. Truckers use CB radio, so design a an automated CB messaging interface. Road trippers are bored out of their minds, so make the balloons part of a big game of I SPY. Design an iPhone app. and give away instant music downloads – road trippers need new music! I'm not saying that's easy. Just easier.
My prediction is simple: no one will find all 10 balloons. The winning team will find 5-6 at most. Most people will drastically underestimate the magnitude of this challenge. If DARPA wants to make this hard (and I think they do), they can make it VERY hard. The problem is that the only people who could reasonably plan this in time are the teams of technologists who think they can solve this through data mining alone. But they can't. Strategies with a real chance of winning would take too long to develop. DARPA will re-issue the challenge and up the ante.
Update: A few new ideas and predictions here. I'm so excited! Tomorrow's the day!