Now scientists at Pasteur Institute and the University of Marseille, both in France, and at the University of California, Santa Barbara, have developed an algorithm that effectively mimics the zigzagging and veering of moths by sending entities trying to track a scent on paths that maximize information gain. The authors, reporting on their research in this week's issue of Nature, call their new scheme "infotaxis." They claim that the method's most practical application would be as software in a class of robots called "sniffers" used to track dilute odors emanating from chemicals, bombs or drugs.
With infotaxis, "you singled-mindedly go to the place where you think you'll gain more information," explains co-author Boris Shraiman, a U.C.S.B. physicist. "If you make a step and you find the source, boy, you've really localized it! That's a very informative step."
Infotaxis elegantly balances two essential behaviors: exploration, where a seeker, say a robot, attempts to accumulate information before making a definitive move in any one direction, and exploitation, a riskier method in which the sniffer strikes out in the direction where the estimated probability of finding the source is the highest.
Early on in a search, a robot may know very little about where a scent is coming from—every direction in which it could travel has a relatively equal probability of leading to the source. At this point, the seeker—using and continuously updating this probability map—would employ an exploratory behavior. It may move in a circular motion, spiraling out into progressively larger radii, until it accumulates more information—or encounters a few puffs of odor.
"Once this information accumulates, you have a better image of where the source might be, which is to say, your estimated source location probability distribution is much more peaked at some point," says Shraiman. "Then you start biasing you motion toward that point much more."
Dominique Martinez, a researcher at the Laboratoire Lorrain de Recherche en Informatique et ses Applications, commenting on the study in Nature, notes that when encountering odor plumes in turbulent air, the rate of information gain may be similar to chemotaxis' concentration gradient. "The striking feature of the infotaxis model is that the casting and zigzagging steps are not preprogrammed by imposing explicit rules of movement such as 'advance upwind' or 'turn crosswind,'" she says. "Rather, they both emerge naturally from locally maximizing information gain."