Ants solve tough problems
By Kimberly Patch, Technology Research NewsFor well over a decade, scientists have been watching the way insects organize themselves with an eye toward making human tasks more efficient, and they're still learning.
A group of Swiss and U.S. researchers, for instance, have produced little robots that organize themselves with social behavior patterns derived from ants. Other researchers are looking to ant colonys to increase efficiency in truck routes, network routing, and distributed decision-making.
The robotics researchers are using ant algorithms to tackle one of the stickiest problems of their field: making machines that can deal with the unpredictable. Those researchers programmed a swarm of small robots with algorithms modeled after the decentralized control techniques of an ant colony.
The robots, like ants, recruited other robots when they discovered large piles of the "food" pucks they were programmed to collect, and this behavior increased their foraging efficiency. "Simple ant-based algorithms can be used efficiently to make a group of robots work together,” said Laurent Keller, a professor of evolutionary ecology at the University of Georgia, Athens.
The experiment also showed a more surprising result. As the number of robots involved in a task passed a certain size, the robots became less efficient. According to Keller, the relationship between group size and efficiency was similar to that documented in social insects. "There is an optimal group size, just as in ants," he said.
Keller's next step is to coax antlike division of labor out of the robots, he said. Eventually, ant algorithms could be used to help robots work without oversight in areas where humans cannot go, he said.
Meanwhile, another researcher is applying ant colony experience in discovering the shortest path to a food source to truck and network routing.
Ants are efficient as a group because they lay and follow chemical trails of pheromone, said Eric Bonabeau, CEO of Eurobios. "The first ants returning to the nest from a food source are those that take the shorter path twice -- from the nest to the source and back," he said. The ant's nestmates find the shortest trail by following the strongest chemical path.
Bonabeau is using this process to tackle problems that have so many variables they bog down today's computers. One example is the classic problem of finding the most efficient route for a traveling salesman who must visit several cities. It may sound easy, but for only 15 cities, there are billions of route possibilities.
One problem with ants is they won't select a shorter path that is discovered later because the original, longer branches are already marked with pheromone, said Bonabeau. Ant algorithms can overcome this problem by allowing the computer equivalent of pheromone to decay more quickly than the ant pheromone does, said Bonabeau. "When the pheromone evaporates sufficiently quickly, it is more difficult to maintain a stable longer path. The shorter branch can be selected even if presented after a longer branch."
This turns out to be a much more efficient way to tackle route problems then checking all the possibilities. In addition to finding a good route, the algorithms also provide a pool of alternate solutions, which can be tapped when conditions change, according to Bonabeau.
One of Bonabeau's real world applications is truck routing for a Swiss company. Bonabeau's company is a consulting firm that applies science like ant algorithms to business problems.
The route problem is "first expressed in mathematical form, often in terms of a graph with nodes and edges... the nodes would be cities and the edges the roads that connect the cities,” said Bonabeau. "The artificial ants go from node to node, reinforcing some of the edges with virtual pheromone." Bonabeau is also applying the algorithms to networks in a similar way.
Bonabeau's work is "novel and demonstrates a portion of the capability of [ant] techniques. It shows they do have mathematically attractive optimization characteristics," said H. Van Parunak, chief scientist at the Environmental Research Institute of Michigan (ERIM), and another longtime ant algorithm researcher.
The work is also practically useful because there are "a large selection of commercial problems that... are complex," he added.
But the ants still have uncracked secrets.
While Bonabeau's practical applications take advantage of ant's abilities to efficiently solve problems that have many possible solutions, the problems are solved with static data. Ants, on the other hand, change their behavior in real-time.
Parunak is working on adding the real-time element to ant algorithms. This means gathering distributed information that is changing as you gather it, he said. He is also aiming to distribute the decision processes out to where the real-time information is, which is how the ants do it.
For instance, if you want to use real-time information to make the most informed sales decision involving three cities, you need information on the state of the world at the same moment in all three cities, said Parunak. If a single person is making a decision involving distributed information it is usually based on static, somewhat mismatched information like yesterday's sales figures in New York and today's sales figures in Chicago. But "the world was never in that state,” he said.
With distributed decision-making, someone in New York would be "making a decision based on information in New York, ... not worrying about the information in Chicago," said Parunak. If you can do this, you can "change the weightings among different criteria dynamically as the system runs," he said.
This type of ant behavior is especially apt in situations that change very quickly, like Air Force maneuvers, Parunak said. "No plan survives contact with the enemy. [If] the planes take off, and something changes and the plan is now in the hopper ... everybody's got to figure out for themselves what's the right thing to do." Parunak's computer models show if planes act like a swarm of ants in finding their way through the enemy in these situations, they're more effective, he said.
Bonabeau's work has been funded by his three employers since 1990: France Telecom, the Santa Fe Institute and Eurobios. Parunak's work is funded by DARPA.
Keller's colleagues were Michael Krieger of the University of Lausanne in Switzerland and Jean-Bernard Billeter of the Swiss Federal Institute of Technology. Their work was funded by the Swiss government and the University of Lausanne in Switzerland. They published their work in the August 31, 2000 issue of Nature.
Timeline: Now
Funding: Corporate, Government
TRN Categories: Data Structures and Algorithms
Story Type: News
Related Elements: Technical Paper "Ant-like Task Allocation and Recruitment in Cooperative Robots" in Nature, August 31, 2000; Technical Paper "Inspiration for Optimization from Social Insect Behavior" in Nature, July 6, 2000.
Advertisements:
September 27, 2000
Page One
Ants solve tough problems
Camera gets all the exposure
Coated specks form nano building blocks
Sturdy virus makes tiny container
Freezing speeds rapid prototyping
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
