Bucket Brigade Algorithm Strategy Used To Win Darpa Balloons Challenge

Mon 14 December 2009

red-balloon-for-contest-3421The "MIT Red Ballon Challenge" won a contest sponsored by DARPA to spot 10 red balloons placed somewhere in the continental United States. The MIT group spotted all 10 balloons within just a few hours of the balloons being launched. Other teams submitted within a few minutes of the MIT group, but the MIT group was the first with all the balloons located properly.

The group used what is called a "bucket brigade" algorithm to entice people to join their effort. You got \\(2000 being the first to send in a balloon's coordinate. The person who signed you up as a potential spotter got \\)1,000. The person who signed them up got \\(500 and the person who signed *them* up got \\)250. The final \$250 went to charity. http://balloon.mit.edu/mit/payoff/

Bucket brigade algorithms are very helpful in a number of AI / machine learning scenarios, in which you are seeking not just a correct answer, but efficiency. For instance, a "classifier system" uses genetic techniques to generate a large number of rules for a blackboard-like solution generator. However, you're typically not seeking just a rulebase that works, but an efficient rulebase.

By incorporating a bucket brigade algorithm, individual rules gain strength / credit /money by contributing to a solution. They participate in a solution by "bidding" their previously-acquired (or inherited) strength. In other words, if a rule solves an important preliminary step, it might not ever get the \\(2000 for "spotting the balloon" but it might get multiple payoffs of \\)250 for being used in a large number of other solutions. Needless to say, the amount of strength/credit/money acquired by a rule is used to determine its fitness for breeding: the more strength/credit/money you've "earned," the more likely you are to reproduce.

Classifier systems are not quite as sexy as pure genetic programming (in which you breed actual programs to solve problems) nor as easy to program as a genetic algorithm (in which data is bred in an attempt to find a solution), but can produce useful results for hard problems.

The last classifier-blackboard system I wrote was in C++. It would certainly be a lot easier to do in today's dynamic languages!