Evolution breeds cooperation
By Eric Smalley, Technology Research NewsEvolution has certainly been good for human beings and it looks like it could be good for intelligent agents, too.
Two teams of researchers have used genetic algorithms to develop groups of intelligent agents that use cooperative strategies to solve a shared task. In both cases, the agents that used the cooperative strategies worked more efficiently than those that did not.
The results could lead to more efficient teams of robots and better Web search tools. They could also shed light on how humans evolved language.
Both research teams conducted experiments using predator-prey problems in which several predator agents attempt to capture a prey agent. The agents inhabited grid environments that allowed them to move only in one of four directions. The researchers used genetic algorithms to produce successive generations of predator agents, each more efficient than the last.
In the NEC Corporation researchers' experiment, four predator agents attempted to surround a prey agent that moved either randomly or in one direction. The predators also had access to a shared virtual bulletin board and some agents used it to post strings of bits.
"It just so happened that the agents... using these strings were the ones who outperformed the agents who didn't learn to use them," said Lee Giles, now a professor of information sciences and technology at Penn State University. "Not only that, but they outperformed all the other scenarios and strategies which have been developed over the years for this problem."
The researchers also found that if the agents were allowed to post longer strings to the bulletin board, they were more efficient.
Though it was clear that the agents were communicating, the researchers weren't able to analyze the agents' language. "We don't know... what exactly the agents are saying to each other," said Giles.
Because the problem of coordinated action requires communication the NEC researchers' results aren't surprising, said Stuart Russell, a professor of computer science at the University of California at Berkeley. "You know already that the communicating ones will do better," he said.
Evolving communications could prove useful for multiagent systems in which the agents are designed to communicate, said Giles.
"In some space exploration scenarios you can't always anticipate the situations you will be in," he said. "If you want agents to communicate with each other, what language would you design for them? The language you design actually might not be the most appropriate language for the scenario you find yourself in."
Whether or not evolved agent communications can be applied to practical systems, they could prove a beneficial tool for science.
"It's always interesting to find... a task and a setting where communication actually is advantageous, and maybe that way we can eventually understand how and why [humans evolved] communication," said Risto Miikkulainen, an associate professor of computer science at the University of Texas at Austin and one of the researchers on the other team that evolved cooperative agents.
However, the results from the NEC experiment suggest that the communication was not a full-blown language complete with grammar and semantics, he said. "The question arises what kind of mechanisms or environmental pressures would be necessary to evolve a language?"
The University of Texas team's experiment used three predator agents that attempted to capture a prey agent programmed to move away from predators.
Because the predator agents did not have to surround the prey agent, communication wasn't required. "We found that when the agents did not have to consider what the other agents were doing -- they did not receive any inputs from them, no communication, not even visual location -- they evolved very efficient roles," said Miikkulainen.
For this kind of task the researchers found that role-based cooperation is more efficient than communication-based cooperation.
"One of the agents in this team would just sit and wait and the other agents would drive the prey towards the waiting agent," said Miikkulainen. "It actually makes sense if you think about it. That's how, say, a good soccer team or hockey team or basketball team works. When you play with the same guys and you practice the same plays, you know what they're doing and where they are and things work very smoothly," he said.
The usefulness of genetic algorithms for multiagent systems is limited in part because uniform agents that function as a team are only a subset of multiagent systems in general, said Russell. "Multiagent systems is not really about designing individuals. It's really about designing the mechanisms that allow all kinds of individuals to work together successfully," he said.
Giles' research colleague was Kam-Chuen Jim of Physiome Sciences, Inc. They published the research in the Summer, 2000 issue of Artificial Life. The research was funded by NEC Corporation. Evolved agent communications could be applied to real-world problems in three to five years, said Giles.
Miikkulainen's research colleague was Chern Han Yong of the University of Texas at Austin. The research was funded by the National Science Foundation.
Timeline: 3-5 years
Funding: Corporate; Government
TRN Categories: Artificial Life and Evolutionary Computing; Multiagent Systems
Story Type: News
Related Elements: Technical paper, "Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem," Artificial Life, Summer, 2000; Technical report, "Corporative Coevolution of Multi-Agent Systems," Department of Computer Sciences, University of Texas at Austin
Advertisements:
February 28, 2001
Page One
Robots learn soft touch
Evolution breeds cooperation
Chip promises brighter wearable displays
Light source brightens prospects for security
Bound bits could bring bigger disks
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.
