DARPA challenge unshreds destroyed documents

Wednesday - 11/23/2011, 5:23am EST

Jared Serbu, DoD reporter, Federal News Radio

Download mp3

The Defense Advanced Research Projects Agency (DARPA) is using a challenge program to find out whether it's possible to put shredded documents back together again.

It turns out the answer is yes, but with one important caveat: Participants in the challenge are dealing with pieces of one document at a time, not the mishmash of paper shards that would likely be found in a typical organization's recycling bin.

Nonetheless, with a little less than two weeks to go from the start of the Oct. 27 competition, participants have managed to meet four out of five challenges of incrementally increasing difficulty. Thousands of individuals or teams have signed up to take a crack, and the winner will take away $50,000.

As in some of its previous public challenges, DARPA wanted to see how people go about solving complex problems. And in this case, the answers could have some important military applications, said Dan Kaufman, director of DARPA's Information Innovation Office.

"We shredded the documents in different ways, and we wanted to know if people could put them back together in a way that's relevant to the military," he said. "That means, can you do it fast enough and cheap enough to fit within a mission timeframe?"

It amounts to perhaps one of the most difficult sets of jigsaw puzzles in history. There are tens of millions of possible combinations, and unlike the usual jigsaw puzzle, the people putting it together don't know what the final product is supposed to look like. The final and most difficult document, "number five", contains 6,000 separate pieces of shredded paper.

But on Monday, DARPA was pleasantly surprised to find that the first four had already been solved. Dr. Norm Whittaker, deputy director of DARPA's Information Innovation Office, said the teams took a variety of approaches.

"We saw almost immediate returns on the first puzzle within the first few days," he said. "Some real clever jigsaw puzzle fans, I think, were the ones who stepped up. But as we get into the most difficult puzzles, the jigsaw puzzle folks are having a lot more difficulty with the thousands and thousands of pieces."

Teams lining up to play

About 8,200 teams or individuals signed up to compete and the puzzles received more than 70,000 downloads from the DARPA website. Whittaker said the teams moving up the leader board seem to be ones that have figured out ways to go beyond the traditional, manual jigsaw-puzzle approach.

"We're seeing automated approaches, and we're seeing at least two crowdsourced efforts," he said. "That looks like an approach that has a real potential to move fast."

One of the teams taking the crowdsourcing approach is led by Dr. Manuel Cebrian, a research scientist at the University of California San Diego. He was on the Massachusetts Institute of Technology team that solved a DARPA challenge in 2009 in which participants had to track down ten red balloons hidden all over the country.

For the shredder challenge, his team managed to recruit 3,500 participants from across the globe in a single week, through a recursive scheme of monetary incentives.

If UCSD wins, the $50,000 will get divvied up among the people who helped solve the puzzles and their recruiters. Participants get a dollar every time they find a paper shard's proper place, but 50 cents also goes to the recruiter, and a quarter goes to that recruiter's recruiter. The idea, Cebrian said in an interview with Federal News Radio, is to expand the recruiting reach to people who don't necessarily have puzzle-solving skills. If they know someone who does, they can get a piece of the action.

More help is needed

Hundreds of members of the UCSD team are working on the puzzle at any given time. To do it, they arrange the pieces collaboratively on a virtual tabletop and exchange ideas in an online chat environment. But even that approach isn't enough to solve the more difficult puzzles, numbers four and five. So they're getting some puzzle-solving help from computers.

"We're working on computer vision techniques that can actually separate the pieces by similarity," he said. "If there are some pieces that are blank, we'll put them in one pile on the virtual board. If there are other pieces that are, for instance, stained from coffee, we'll put them together. Even if we don't know their exact location, we know they're very likely to go together. So with these clustering techniques, we're helping the actual participants assemble the puzzle."