mssv + Have You Played

Update 2 Nov: Just set up a wiki to document resources about the Network Challenge at http://redballoon.wikispaces.com – feel free to join in!

You may have heard of DARPA before – they’re the US Defense Advanced Research Projects Agency. In 1969, they created ARPANET, the predecessor to the Internet, and more recently, they run the DARPA Grand Challenge, which is a competition for groups to create driverless cars.

A couple of days ago, they announced the DARPA Network Challenge to mark the 40th anniversary of the Internet. Like the Grand Challenge, it’s a simple competition: On December 5th, ten large red weather balloons will be inflated and moored at at locations across the US. The first individual to submit the latitude and longitude of all ten balloons will win $40,000.

The purpose of the competition is to ‘explore the role the Internet and social networking plays in the timely communication, wide area team-building and urgent mobilization required to solve broad scope, time-critical problems.’ Without the internet, it’d be impossible for all but the very largest organisations – the government, the military, Google, etc. – to win this competition; but with the internet, it’s possible for millions of people across the world to collaborate on a single goal.

The Network Challenge is not the first to test the mass problem-solving abilities of online communities; open source projects see thousands of people work on extremely complex problems over long time scales. Some of the tasks in Alternate Reality Games (ARGs) have brought these problems into the physical world; in I Love Bees, thousands of people answered payphones across the US.

But the Network Challenge is the first to pose such a geographically-massive task in such a small timescale. Those red balloons aren’t going to stay up forever – they’re only going to be moored for six hours. And while they’ll be moored at ‘readily accessible locations and visible from nearby roadways’, the continental United States has an area of 8 million square km and 6.5 million km of roadways (4.2 million if you’re just counting the paved ones).

It’s a deceptively simple challenge that ought to be reasonably straightforward to solve, but gets extremely difficult and time-consuming when you think things through. Online discussions about the Network Challenge seem to think that you could win this just by following Twitter hashtags and Facebook. Far from it. That might do for a few balloons in cities, but not those by a desert road that no-one ever drives down; and believe it or not, but not everyone uses Twitter – and even if someone does, that’s no guarantee they might not keep the information to themselves for bargaining.

Given this, $40,000 seems like a pittance compared to the effort involved, but the small prize money is really a key point of the competition. It’s not supposed to cover any expenses – in fact, it’s probably as small a sum as they could reach without getting insultingly low.

The reason for the small prize money is because DARPA are exploring the different kinds of motivation that can be brought to bear on this type of problem. If a team treated the Network Challenge like paid work, $40,000 would buy very little time. However, if it’s treated differently – like a game, or like a citizen-science project such as GalaxyZoo – money is basically irrelevant. And it’s those non-monetary types of motivation that DARPA will be keen to evaluate – which works, and which don’t?

So, let’s get onto the fun stuff – how do you win the DARPA Network Challenge?

(Caveat: This is all assuming that DARPA is going to make this hard. If all the balloons end up in cities or by highways, it’ll be much easier).

Positive Strategies

Satellite Photography

This seems like the easiest way – just get a satellite to photograph the continental US over a six hour period. Unfortunately, there are numerous problems:

1. The satellites with sufficient resolution to resolve an 8ft weather balloon do not have a wide enough image swathe to cover such the US in six hours.
2. 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).
3. Clouds, and weather in general.
4. It’s expensive.
5. Not sure how quickly you can get the images from the satellites – it’d need to be near real-time.
6. Highly susceptible to fake balloons (see below).

Satellites are clearly the coolest and tech-heavy solution, but basically impractical for all but the most remote and inaccessible areas…

Aerial Photography

OK, so satellite photography is not the solution. What about planes though? You can get better resolution and near real-time data. But…

1. Planes don’t move fast enough, and the image swathe isn’t big enough.
2. Clouds, and weather in general.
3. It’s expensive.
4. Highly suspectible to fake balloons (see below).

Having said this, I wouldn’t be surprised if aerial photography, like satellite photography, played a role in winning the challenge.

Crowdsourced Data

Let’s forget about looking from above at the moment, and consider a ground-level solution. Why not just get lots of pepole to keep an eye out for the balloons and tell you if they find one? This strategy isn’t susceptible to fake balloons, so that’s a plus, at least.

1. 4.2 million km – that’s a hell of a lot of road. OK, so you don’t have to walk or drive down all of them, particularly in cities, but to have a reasonable level of confidence of finding more than a few balloons, you’re talking about tens of thousands of hours of driving. So you might be able to drum up a few thousand people to drive down specific roads on a Saturday, but they can only cover a fraction of the area required.
2. So there’s a big publicity and marketing challenge here – say you make some iPhone app or SMS number for people to report sightings; how do you get sufficient numbers of people (e.g. tens of thousands) to use yours? Because it certainly won’t be the only one out there.
3. Very noisy data – expect thousands of false sightings

Let’s face it – you’re going to have to use crowdsourced data whether you like it or not. And you’re going to be in for a world of pain…

Negative Strategies (aka 4CHAN)

Winning the Network Challenge isn’t just about finding those ten balloons – you need to find them first. To do that, you can either do the job really quickly, or slow everyone else down. A nice way of doing this is through generating false positives:

• Identical red weather balloons: These will fool everyone and cause a lot of grief; unfortunately, they’re comparatively expensive, and you’ll have to impersonate a DARPA representative.
• Red circles: Make a 2D red circle with an 8ft diameter and put it on the ground; it’ll look pretty similar to a red balloon from above. You could even paint it with a shadow to annoy sat and aerial photography users even more.
• False reports: Want to mess up a crowdsourced strategy? Send in false data! For bonus points, get your friends to corroborate your false reports with photoshopped photos and so on.
• Destroying balloons: If you find a balloon, make a note of its location, and destroy it. Don’t let those DARPA nerds stop you – just use an airgun!

I predict a veritable firehose of false positives being entered into the Network Challenge; it’s just too easy and too fun to put up fake balloons and send in false reports.

How to Win

Realistically, if you’re serious, you’re going to use a combination of these strategies. If I lived in the US and had more spare time, here’s what I’d do:

1. Use satellite and aerial photography for remote and inaccessible regions, then use people + machines to spot the balloons.
2. For most areas, use crowdsourced sightings by creating an application that integrates sightings via every and any communications medium available; voice, SMS, MMS, email, Twitter, IM, etc. When you get a sighting, get other people to corroborate it from different angles. Have an algorithm that assigns a reliability value to each location based on the incoming information.
3. Recognise useful contributors and make stars out of hard-working reliable ones. Use points, and turn it into a game.
4. Give people a reason to be involved. Finding ten weather balloons is not cool enough, and $40,000 doesn’t go very far. Give the prize to charity, or make the challenge part of a story. Make people care.
5. Don’t mess about too much with putting up fake balloons – it’s a waste of time. You’d be better off refining your algorithms and getting more contributors.
6. Don’t try and restrict your contributor base; to win, you need scale. This means a lot of false data, but you’d get it anyway.

This all sounds very hard, but there’s one good piece of news – the required accuracy is only one arc minute, which is about 1.86 km; a pretty big area, all things considered. You don’t need people with GPS devices to report, you could do fairly well with just a street name.

Unanswered Questions and Wildcards

• It’s not clear how many times you’re allowed to submit entries on the site. If you had a list of, say, 30 sightings you were reasonably confident in, could you just send a few hundred thousand entries to cover all possible combinations of the ten real balloons?
• Will there a spam cut-off limit, so you can only submit one entry a second?
• What if someone performs a DDOS attack on the Network Challenge website to prevent other people from entering? (OK, it’s DARPA so you’d think they’d be ready for this, but still…)
• Will people unaware of the challenge report balloons anyway? If so, the challenge becomes rather easier.
• Will a rich person or organisation (e.g. Google) throw money or time at the problem, for the kudos? If this happens, it won’t be as boring as it seems, since I’d be impressed with any organisation nimble enough to shift resources to a problem like this within a mere few weeks.
• Will anyone try a social engineering attack against DARPA to steal the location data? When we ran our Perplex City treasure hunt, with a $200,000 prize, we were paranoid about being followed. While the Network Challenge is less money, it’s arguably more kudos.
• Is DARPA going to make this easy, or hard? (see below)

My Prediction

The Network Challenge will either be solved reasonably quickly, or not at all, and I think it’ll come down to the amount of false positives being entered into the system. Any balloons in or near metropolitan areas will get sighted very rapidly, but others will be very tricky to find. Teams will require scale in order to win – tens or hundreds of thousands of ‘players’, all feeding in data; unfortunately, the most visible team will be the most tempting target for griefers, and they’ll have to deal with a lot of crap, so with the balloons only being up for six hours, it’s not clear whether they’ll be able to corroborate sightings in time.

If individual teams can’t, teams will eventually end up pooling their data in an attempt to weed out false positives. That could take time, but if you’re allowed to send in unlimited entries, maybe this won’t be so bad.

Personally, I welcome the false sightings and griefing; it might be annoying, but that’s life, and if you can beat them, the victory will be much sweeter!

It’s really up to DARPA as to how difficult they make this challenge. If they put most of the balloons near cities and highways, the challenge will be solved within hours. If they’re placed randomly, it’ll be very hard. Very possibly they’ll make it easy to start with this year, and then ratchet up the difficulty, which is sensible (but personally quite disappointing).

Final Thoughts

The Network Challenge is brilliant – it’s the sort of hard-to-solve but easy-to-describe challenge requiring strategy and mass co-ordination that is catnip to someone like me. It also represents the future of work, and demonstrates type of skills that will be most valuable in the future – in that sense, it reminds me of Vernor Vinge’s Rainbows End.

Also, the great thing about the Network Challenge is that it costs DARPA very little to run; you’ve got a website and ten weather balloons. If someone does win, $40k is a small price to pay for witnessing such an original type of problem-solving; and if no-one wins, then they don’t have to pay up.

What about a UK version?

While people of any nationality can enter the Network Challenge, and much of the work will be done online, it’s very much a US-centric task.

Happily, if you are interested in this sort of thing, I’ve been planning a similar sort of challenge with Philip Trippenbach. It’ll be much easier, but no less challenging and fun, and it’ll happen in London before Christmas; you’ll also be able to follow and participate online. Email me if you’re interested!