Fink Wins Huygens Probe Competition

November 28, 2006

The competition, based on a design proposed by Cara MacNish, senior lecturer at the University of Western Australia School of Computer Science and Software Engineering, was named for its several analogies with the European Space Agency's Huygens probe, which landed Jan. 14, 2005, on Saturn's largest moon, Titan.

Like rival space agencies, the programs that participated in the competition sent out "probes" to investigate a remote landscape on a fictional "moon" and find its lowest point. Every probe, sent through the Internet from a contestant's computer, consisted of a request for the altitude of a single point on the moon, generated by the competition's server in Australia. The responses from the probes were then used to refine the searches of every subsequent probe (with each program using a total of 1,000 probes per moon). Fink's winning algorithm bested all competitors on 11 of the 20 trial moons.

The purpose of the contest was to promote advances in the field of optimization. Optimization algorithms are step-by-step procedures for making efficient use of limited resources when searching a large set of alternatives for the "best" one. Their applications may be either very general or specialized for a small category of problems, depending on how "best" is defined. Changing that definition lets the same algorithm be used to seek out the "fastest," "cheapest," "safest," "most likely," or "most profitable."

Increases in computing power have led to an explosion of new algorithms, but they are difficult to compare when applied to different problems in different languages on different machines. MacNish observed that such diversity can hinder progress, "because it is difficult to evaluate the relative merits of proposed algorithms and modifications." In other words, it is hard to improve what you cannot compare.

MacNish's "Huygens Suite" proposal addressed these difficulties with a standard set of "benchmark" test problems, generated by the testbed server on request and made freely available through the Web. Algorithm designers wishing to evaluate their programs could run them privately, on their own computers, without having to translate their software for the testbed's computing environment.

In MacNish's proposal, the only extra software that algorithm designers need to write should be the simple interfaces linking their programs with the Huygens server. In the actual competition, getting that interface to work was not so straightforward. Fink credits Mark Tarbell, an associate in Fink's Visual and Autonomous Exploration Systems research laboratory, at Caltech, for helping to write it.

While no single benchmark problem can represent the universe of optimization, the pseudo-random fractal landscapes used for the competition were chosen as simple analogs for many practical problems. In fractal landscapes each local region looks like a scaled version of the entire landscape.

This fractal property ensured that even as algorithms narrowed their searches to smaller regions, the landscape appeared just as rugged and the optimization problem remained just as hard. Algorithms that do well on these problems should therefore generalize easily to problems with more limited scale.

Each moon was theoretically a vast data set, far too large for any computer to store. Yet like spelunkers tapping the roof of a low, pitch-black cave, the algorithms never explored more than 1,000 discrete points on the landscapes. MacNish's Huygens Suite solved the storage problem by assigning each moon a unique ID number, which it then used as a seed to generate only those neighborhoods that the probes asked about. The fractal worlds were never really created, except where they were looked at.

During the contest the algorithms were "flying blind" across the landscapes, but in a series of training moons the algorithms could see as much as they wanted. In the first training runs, Fink recognized that his algorithm could easily find the lowest basin region of each moon using about 20 probes. Exploring the fractal landscape at ever-smaller scales, however, required all 1,000 probes. "The battle was won in the fifth digit," he says.

Fink adapted an algorithm he had developed earlier for use in protein design, and he is currently using a similar approach for medical and geologic applications. He would like to see future contests searching in higher dimensions, but he is pleased that he entered this one. "It was quite a blast," he says.