DARPA Network Challenge

The 2009 DARPA Network Challenge was a prize competition for exploring the roles the Internet and social networking play in the real-time communications, wide-area collaborations, and practical actions required to solve broad-scope, time-critical problems. The competition was sponsored by the Defense Advanced Research Projects Agency (DARPA), a research organization of the United States Department of Defense. The challenge was designed to help the military generate ideas for operating under a range of circumstances, such as natural disasters.[1] Congress authorized DARPA to award cash prizes to further DARPA's mission to sponsor revolutionary, high-payoff research that bridges the gap between fundamental discoveries and their use for national security.

In the competition, teams had to locate ten red balloons placed around the United States and then report their findings to DARPA. Due to the distributed nature of the contest, many teams used online resources, such as social media sites, to gather information or to recruit people that would look for balloons. Teams often had to deal with false submissions, and so they needed to come up with ways to validate and confirm reported sightings. The contest was concluded in under nine hours, much less than expected by DARPA, and had many implications with regards to the power of online social networking and crowdsourcing in general.[2]

Specifics of the competition

Under the rules of the competition, the $40,000 challenge award would be granted to the first team to submit the locations of 10 moored, 8-foot, red weather balloons at 10 previously undisclosed fixed locations in the continental United States. The balloons were to be placed in readily accessible locations visible from nearby roads. The balloons were deployed at 10:00 AM Eastern Time on December 5, 2009, and scheduled to be taken down at 5:00 PM. DARPA was prepared to deploy them for a second day and wait for up to a week for a team to find all of the balloons.

Part of the purpose of the challenge was to force participants to discern actual pertinent information from potential noise. Many teams came across false reports of sightings, both accidental and purposeful. One valid strategy was spamming social networks with false reports to throw competitors off the trail of real sightings. The verification of balloon sightings was paramount to success.

The contest was announced only about a month before the start date. This limited the amount of time teams had to prepare. The ability of many to do so showed the effectiveness of mass and social media to distribute information and organize people quickly.[3] The time in which information about the challenge spread was actually more compressed than a month. However, in the week preceding the launch day the official competition site increased in traffic from an average of 1,000 hits per day to 20,000 hits per day. Similarly, the efforts of many competing teams went viral in the last few days before the start date.[4]

DARPA selected the date of the competition to commemorate the 40th anniversary of the Internet.

Results

Even though DARPA was prepared to deploy the balloons for a second day and accept submissions for up to a week until a team found all 10 balloons, the MIT Red Balloon Challenge Team won the competition in under 9 hours.[2] A team from the Georgia Tech Research Institute (GTRI), which located nine balloons, won second place. Two other teams found eight balloons, five found seven, and the iSchools team (which represented Pennsylvania State University, University of Illinois at Urbana–Champaign, University of Pittsburgh, Syracuse University, and University of North Carolina at Chapel Hill), whose strategy is described below, finished tenth with six balloons.[3] In table form, the top ten teams were:[5]

Place Name Hometown # Balloons Date/time
1 MIT Red Balloon Challenge Team Cambridge, MA 10 6:52:41 PM
2 GTRI "I Spy a Red Balloon" Team Atlanta, GA 9 6:59:11 PM
3 Christian Rodriguez and Tara Chang (Red Balloon Race) Cambridge, MA 8 6:52:54 PM
4 Dude It's a Balloon Glen Rock, NJ 8 7:42:41 PM
5 Groundspeak Geocachers Seattle, WA 7 4:02:23 PM
6 Army of Eyes Mutual Mobile Austin, TX 7 4:33:20 PM
7 Team Decinena Evergreen, CO 7 6:46:37 PM
8 Anonymous Anonymous 7 7:16:51 PM
9 Nerdfighters Missoula, MT 7 8:19:24 PM
10 iSchools DARPA Challenge Team State College, PA 6 6:13:08 PM

Winning strategy

The winning MIT team used a technique similar to multi-level marketing to recruit participants, with the prize money to be distributed up the chain of participants leading to successful balloon spottings, and all prize income remaining after distribution to participants to be given to charity.[6] The team's strategy for public collaboration in finding the balloons was explained on their website:

We're giving $2000 per balloon to the first person to send us the correct coordinates, but that's not all -- we're also giving $1000 to the person who invited them. Then we're giving $500 whoever invited the inviter, and $250 to whoever invited them, and so on ... (see how it works). It might play out like this. Alice joins the team, and we give her an invite link like http://balloon.media.mit.edu/alice. Alice then e-mails her link to Bob, who uses it to join the team as well. We make a http://balloon.media.mit.edu/bob link for Bob, who posts it to Facebook. His friend Carol sees it, signs up, then twitters about http://balloon.media.mit.edu/carol. Dave uses Carol's link to join ... then spots one of the DARPA balloons! Dave is the first person to report the balloon's location to us, and the MIT Red Balloon Challenge Team is the first to find all 10. Once that happens, we send Dave $2000 for finding the balloon. Carol gets $1000 for inviting Dave, Bob gets $500 for inviting Carol, and Alice gets $250 for inviting Bob. The remaining $250 is donated to charity.

The strategy was a variant of the Query Incentive Network model of Kleinberg and Raghavan,[7] with the main difference being that the incentive rewards in the team's technique scale down for later participants.[8] The recursive nature of the reward had two beneficial effects. First, participants had an incentive to involve others, as these new people would not become competitors for the reward but rather cooperating partners. Second, people not located in the United States were motivated to participate by passing along information even though they had no way of locating a balloon in person. This helped the team garner a large number (over 5,000) of participants.[3] The team only began with four initial participants.[4]

To determine whether submissions were legitimate or fake, the team employed at least three strategies. The first strategy was examining whether there were multiple submissions for a location. If this was the case, then the likelihood of a balloon actually being there was thought to be higher. A second strategy was to check whether the IP address of the submitter matched the supposed location of the balloon. A third strategy was to examine photos accompanying the submission. Real photos included a DARPA employee and a DARPA banner, details which were not announced, while faked ones did not.[3]

A detailed analysis of the winning strategy highlighted the important role that social media played. Analysis of Twitter data showed that while some teams relied on large initial bursts of activity over Twitter, mentions of those teams quickly faded. It was argued that due to the recursive incentive structure, the MIT team was able to create a more sustained social media impact than most teams.[8]

Second-place strategy

The second-place GTRI team used a strategy that relied heavily on Internet publicity and social media. They created a Web site three weeks before the launch day and used a variety of media-related efforts, including a Facebook group, in order to increase the visibility of the team and increase the chance that people who spotted the balloons would report the sightings to them.

The team promised to donate all winnings to charity to appeal to the altruism of participants. However, due to the lack of a structure that created much incentive as the winning MIT team's scheme, their network of participants grew to only about 1,400 people.

With regards to validating submissions, the team assumed that because of the charitable nature of their effort, the number of false submissions would be low. In any case, they primarily relied on personal validation, having phone conversations with submitters.[3]

Tenth-place strategy

5개 대학을 대표하는 10위 아이스쿨스팀은 두 가지 뚜렷한 접근법을 시도했다. 첫 번째는 발사 당일에 풍선을 찾을 팀원을 직접 모집하는 것이었다. 이 회원은 팀 내 조직(예: 펜실베이니아 주립대)을 위한 공식 메일링 목록과 소셜 미디어 웹사이트 그룹에 학생, 교수진 및 동문들을 포함했다. 그러나 실제로 참여한 관측자는 극소수에 불과했고, 이 전략을 이용해 풍선 하나만 발견됐다.

두 번째 전략은 오픈 소스 인텔리전스 방법을 사용하여 사이버 공간에서 도전과 관련된 결과를 검색하는 것이었습니다. 이것이 그들이 풍선을 찾는 데 성공한 주요 원천이었다. 이 전략은 결국 두 개의 뚜렷한 하위 전략으로 구성되었다. 첫 번째는 트위터와 경쟁팀의 웹사이트를 포함한 다양한 정보원을 수작업으로 검색하고, 보고된 목격담을 취합한 다음, 출처의 명성에 근거하여 목격의 타당성을 평가하는 인간 분석가 그룹을 이용하는 것이었다.

팀이 사용한 사이버 공간 검색과 관련된 또 다른 전략은 자동화된 웹 크롤러로, 트위터와 반대 팀의 웹사이트에서 데이터를 캡처한 후 분석하는 것이었다. 이 기술은 천천히 작동했고 더 긴 대회 기간 동안 혜택을 받았을 것이지만, 트위터 크롤러는 때때로 지리적 정보를 포함하고 있기 때문에 특히 유용하다는 것이 증명되었다.

가능한 목격의 유효성을 확인하기 위해, 가능하면 모집된 팀원을 사용했다. 만약 이용할 수 있는 사람이 없다면, 목격자 근처에 위치한 단체에서 새로운 관찰자를 모집했다. 팀 내 서로 다른 조직의 분산된 위치는 이것이 실현 가능한 전략이 될 수 있도록 했다. 사진 분석은 청구권의 타당성을 확인하거나 이의를 제기하는 데 사용되었다.

또 다른 팀이 우연히 목격 정보를 유출한 뒤 이를 은폐하려 한 사례도 마주쳤다. iSchools 팀은 소셜 네트워크를 포함한 다양한 정보원을 사용하여 실제 위치가 무엇인지 파악했다. 이것은 어떤 것의 타당성을 결정하기 위해 다양한 공공 웹사이트의 정보를 사용할 가능성을 보여주었다.[3]

기타전략

대회 전에 많은 사람들이 위성 사진, 항공 사진, 풍선 탐지를 위한 크라우드소싱 [9]등 가능한 전략과 다른 팀들의 승리를 막기 위한 잘못된 정보 캠페인의 가능성에 대해 논의했었다. 실제 대회에서는 팀별로 채용한 전략이 다양했다.

캘리포니아 주 샌 라파엘의 제이슨 브린델이라는 한 팀장은 140여 명으로 구성된 팀을 구성했다.[10] 그의 계획은 그의 팀원들이 그들의 연구 결과를 전달할 수 있도록 도전에 전념하는 웹사이트와 트위터 계정을 만드는 것이었다. 도전에 참여하는 모든 사람은 자신의 제출에 대해 확인하는 세부사항을 포함한다면 정보를 제출할 수 있다. 브린델은 팀이 뉴스 사이트, 블로그, 소셜 미디어 사이트에 풍선에 대한 언급을 위해 인터넷을 뒤지도록 할 계획이었다.

현재 플레이스테이션3 해킹과 소니의 소송 해결로 유명한 트위터 유명인 조지 핫즈는 대회 시작 1시간 전에야 대회 준비를 한 뒤 트윗을 올렸다. Hotz는 8개의 풍선을 성공적으로 찾을 수 있었다. 4명은 거의 5만명에 달하는 그의 트위터 네트워크 안에서 발견되었고, 4명은 다른 팀과의 정보 교환을 통해 획득되었다.[4]

5위 마무리 투수인 그라운드스피크 지오커러는 활동적인 지오커러스와 그라운드스피크 직원들을 배치해 풍선을 수색했다. 그들은 8개의 풍선을 찾는데 성공했지만, 데이터 입력 오류로 인해 7개의 풍선만 발견되었다.[11]

'네르드파이터'라는 팀은 형제단 2.0 vlog의 기존 팔로워 네트워크를 활용해 대회 전 바이럴 영상을 출시했다. 그들은 2,000명의 활동적인 풍선을 찾는 사람들을 간신히 끌어 모았다. 또 대회와 관련된 인터넷 트래픽을 검색해 다른 팀들을 혼란스럽게 하거나 잘못 지시할 것을 기대하며 오보 캠페인을 전개하는 데 특화된 3천 명의 네드파이터를 활용했다. 그들은 또한 휴대폰 사용자들의 네트워크를 만들어 발견에 대한 직접적인 문자 메시지 확인을 제공했다.[4]

아이폰 애플리케이션 개발팀은 TX 오스틴을 기반으로 Army of Eyes를 결성했다. 이들의 출원은 당초 챌린지 발표 직후 개발돼 챌린지 출시일까지 이용할 수 있게 됐다.[4]

기존 동네 감시 커뮤니티용 소셜미디어 사이트 회원들로 구성된 아이네이버스 팀은 모집이나 거래 활동을 전혀 하지 않았다. 그들의 목표는 그들의 네트워크가 주변 지역 내의 비정상적인 활동에 대해 효과적으로 보고할 수 있는 능력을 평가하는 것이었다. 그들은 열 개의 풍선 중 다섯 개의 풍선을 성공적으로 찾을 수 있었다.[4]

반사

그 도전은 많은 통찰력을 낳았다. 첫째, 대중 매체와 소셜 미디어가 얼마나 보완적으로 행동할 수 있는지를 보여주었다. 매스미디어가 주로 도전에 대한 일반적인 정보를 전파하는 데 유용했지만, 소셜미디어가 잠재적인 팀원 모집에 대한 도전에 대한 정보의 바이러스 전파에 효과적이었다. 둘째, 소셜 미디어가 데이터 마이닝 소스로서 어떻게 유용할 수 있는지를 보여주었다. 예를 들어, iSchools 팀은 공공 웹사이트를 단순히 모니터링함으로써 다른 많은 팀들보다 더 잘했다. 셋째, 과제는 소셜 네트워킹이 활용될 수 있는 다양한 방법을 보여주었다. MIT와 GTRI 팀은 참가자들 간의 빠른 의사소통을 용이하게 하기 위해 주로 그것들을 사용했고, iSchools 팀은 그것을 정보의 원천으로 사용했다.

넷째, 이 도전은 지리적으로 분산되고 시간에 민감한 문제를 해결하기 위해 크라우드소싱 기법을 사용하는 일반적인 효과를 보여주었다. DARPA 프로그램 관리자들은 이 도전이 얼마나 빨리 완성되었는지에 놀랐다. 그러나 공공 사이트에서 유용한 데이터를 걸러내는 것은 어려울 수 있으며, 공개상장 정보에 대한 독립적인 검증은 효율성과 정확성에 있어 과제로 남아 있다.[3]

DARPA는 소셜 네트워크가 강력한 인텔리전스의 원천이 될 수 있지만, 소셜 네트워크를 사용하는 것은 데이터 마이닝 사용자 컨텐츠와 관련된 프라이버시 우려 때문에 정치적으로 민감할 수 있다고 지적했다. 마찬가지로, MIT 우승 팀은 그들의 재귀적 접근방식은 그 노력의 목표가 참여자들에 의해 도덕적이고 좋은 것으로 보여질 경우에만 효과적일 것이라고 추측했다.[4]

Verified balloon locations

Balloon locations
Map all coordinates using: OpenStreetMap
Download coordinates as: KML

The officially verified coordinates of the balloons,[12] listed by their tag numbers, were:

Related challenges

Inspired by the success of the DARPA Network Challenge, DARPA launched the Shredder Challenge in 2011. This competition aimed to explore methods to reconstruct documents shredded by a variety of paper shredding techniques. As with the DARPA Network Challenge, some teams used crowdsourcing to solicit human help in reconstructing the documents.[14] The winning team used a computer-vision algorithm to suggest fragment pairings to human assemblers for verification.[15]

On July 2, 2011, also inspired by the DARPA Network Challenge, the Langley Knights Challenge was launched. It differed in that there were knights to find in various locations in England and that had been placed on Google Maps so people in locations outside the UK could participate.[16]

In January 2012, the University of Pennsylvania School of Medicine launched the MyHeartMap Challenge to map Automatic External Defibrillators (AEDs) in the city of Philadelphia.[17] According to the organizer Dr. Raina Merchant, "DARPA succeeded with locating red balloons. AEDs are a natural extension of a brilliant idea."[18]

Also inspired by the DARPA Network Challenge, a contest called Tag Challenge was sponsored by the United States Department of State and the Institute of International Education.[19] Tag Challenge sought to have teams locate and obtain pictures of five individuals in five different cities across North America and Europe within twelve hours on March 31, 2012. Despite the fact that the potential winnings were considerably lower than for the DARPA Network Challenge, organizers sought to test the ability of the methods discovered in that challenge to "find a person of interest" rather than a statically located object.[20]

See also

References

  1. ^ "MIT wins $40,000 prize in nationwide balloon-hunt contest". CNN. 2009. Archived from the original on 2012-01-20. Retrieved 2012-02-21.
  2. ^ a b "MIT Red Balloon Team Wins DARPA Network Challenge" (PDF). DARPA. Archived from the original (PDF) on November 11, 2010. Retrieved 2009-12-06.
  3. ^ a b c d e f g John C. Tang; Manuel Cebrian; Nicklaus A. Giacobe; Hyun-Woo Kim; Taemie Kim; Douglas "Beaker" Wickert (2011). "Reflecting on the DARPA Red Balloon Challenge". Communications of the ACM. 54 (4): 78–85. doi:10.1145/1924421.1924441.
  4. ^ a b c d e f g Defense Advanced Research Projects Agency. "DARPA Network Challenge Project Report". Retrieved 2012-03-03.
  5. ^ "DARPA Network Challenge Final Standings" (PDF). DARPA. Archived from the original (PDF) on November 11, 2010. Retrieved 2010-10-07.
  6. ^ "How It Works". MIT Red Balloon Challenge Team. Archived from the original on 2010-01-11.
  7. ^ J. Kleinberg; P. Raghavan (2005). "Query Incentive Networks". Proceedings of 46th Annual IEEE Symposium on FOCS: 132–141.
  8. ^ a b Galen Pickard; Wei Pan; Iyad Rahwan; Manuel Cebrian; Riley Crane; Anmol Madan; Alex Pentland (2011). "Time-Critical Social Mobilization". Science. 334 (6055): 509–512. arXiv:1008.3172. Bibcode:2011Sci...334..509P. doi:10.1126/science.1205869. PMID 22034432. S2CID 2950817.
  9. ^ Adrian Hon (October 31, 2009). "How to Win the DARPA Network Challenge". Mssv.
  10. ^ Gross, Doug. "Nationwide balloon-hunt contest tests online networking". CNN. Archived from the original on 1 March 2012. Retrieved 3 March 2012.
  11. ^ "10 Balloonies - Groundspeak's DARPA War Room". Groundspeak. December 9, 2009.
  12. ^ "DARPA Network Challenge Balloon Coordinates" (PDF). DARPA. Archived from the original (PDF) on August 19, 2010. Retrieved 2009-12-13.
  13. ^ "Ten red balloons– and one's in Charlottesville!". The Hook. December 5, 2009.
  14. ^ "Crowdsourcing the 'most challenging puzzle ever". CNET. November 17, 2011. Retrieved 2011-12-01.
  15. ^ Drummond, Katie (December 2, 2011). "Programmers Shred Pentagon's Paper Puzzle Challenge". Wired. Retrieved December 5, 2011.
  16. ^ https://sloanreview.mit.edu/article/find-the-knights-this-weekend-social-mobilization-experiment/
  17. ^ McCullough, Marie (January 31, 2012). "Global contest will lead to help during heart attacks". The Philadelphia Inquirer. Retrieved 2012-02-02.
  18. ^ "MyHeartMap Challenge Media Page". University of Pennsylvania. Retrieved 2012-02-03.
  19. ^ "Tag Challenge". Archived from the original on 14 July 2013. Retrieved 22 March 2012.
  20. ^ Shachtman, Noah (March 1, 2012). "U.S. Wants You to Hunt Fugitives With Twitter". Wired. Retrieved 22 March 2012.

External links