University Park, PA --- An NEC Institute/Penn State study shows that computer programs, known as autonomous agents, not only can evolve their own language and talk with one another, but also can use communication to improve their performance in solving the classic predator-prey problem.
Like kids playing hide and seek, the autonomous agents used in the study hunted for and found their prey faster and more efficiently if they communicated with one another. "Talking," via a message board, enabled the agents to perform better than in all previous predator-prey studies –better even than when they had been programmed with a hunting strategy by humans.
Dr. C. Lee Giles, the David Reese Professor of Information Sciences and Technology and co-author of the study, says, "The findings have a number of possible applications, for example, smart web crawlers that communicate with one another as they scour the web automatically retrieving information. One can also imagine military applications or intelligent robots that explore other planets or the sea bed in groups while talking to one another."
The findings are detailed in a paper, "Talking Helps: Evolving Communicating Agents for the Predate-Prey Pursuit Problem," published in the current (6:3) issue of the journal, Artificial Life. The work was performed when Giles and co-author Kam-Chuen Jim were both at NEC Research Institute, Inc. Jim is currently at Physiome Sciences, Inc. Giles joined Penn State's new School of Information Sciences and Technology in Fall 2000.
In the study, four predator agents inhabiting a virtual, four-sided, two-dimensional-grid world, were set in pursuit of a fifth agent who served as the prey. The agents all moved simultaneously, at the same speed in north, south, east or west directions. No diagonal shortcuts were permitted. The predators could not see each other and did not know each other's location.
The researchers write that this scenario is probably more difficult for the predators than any considered in previous studies of the predator-prey problem.
The predator agents' goal was to capture the prey by surrounding it on all four sides. Each of the predator agents could "speak" a short string of zeros and ones, the binary alphabet, simultaneously. The communicated strings of symbols were placed on a message board. Each agent could then read all the strings communicated by all the predators in order to determine the next move and what to say next.
The researchers explain that the agents created their own vocabulary, the strings of zeros and ones, in a random manner. Self-organization into meaningful "language" occurred because the agents are coupled in the sense that they must conform to a common vocabulary in order to cooperate through communication. Since the predators cannot see each other and do not know each other's location, the predators have to evolve a language that can represent such information. The researchers found that as the size of the language increased, the performance of the predators improved. Using this observation, the researchers developed a method for incrementally increasing the language size that results in a coarse-to-fine search that significantly reduces the time required to find a solution.
The researchers write that "Future work could focus on the semantics of the evolved languages." Giles notes that "We can compute the upper bound of the number of useful meanings that the predators can evolve. The actual number of useful meanings that they did evolve was much smaller."
Jim added, "We found that in the evolved languages each word can have multiple meanings, with the meaning determined by the semantic context. This phenomenon is also observed in natural languages."
"As the size of the language increases, the average number of meanings assigned to each word decreases," he said.
The researchers conclude by writing, "It would be an important step to extend the analysis introduced here to other forms of multi-agent communication structures, such as a system of agents that communicate asynchronously or only to their nearest neighbors.
Editors: Dr. Giles is at 814-865-3528 or clg20@psu.edu by email.
Journal
Artificial Life