ISSN 1320-0682
|
|
|
|
ISSN 1320-0682 |
| Source: | http://www.complexity.org.au/ci/vol06/baray/baray.html | Received: | 01/07/1998 | ||
| Vol 6: | Copyright 1998 | Accepted for publication: | 15/10/1998 |
Cristobal Baray
Cognitive and Computer Science Departments
Indiana University
215 Lindley Hall
Bloomington, IN 47405
Email: cbaray@cs.indiana.edu
WWW: http://www.cs.indiana.edu/~cbaray/ecmas
Previous work defined a simple artificial world and evolved agents that utilized several effective communication schemes that aided the agents with a foraging task and predator avoidance . The agents were able to extend their average life span by coordinating their actions via undirected communication. The model did not force the agents to communicate -- instead the model was designed to explore the types of communication schemes that could evolve and the situations that facilitated the evolution of communication. This work examines some of the assumptions within the previous work. Specifically, population size is altered to study the effectiveness of the communication scheme over varying conditions. This work shows that the population size can effect the group behavior and introduces a method for quantifying the emergent effects of individuals upon group behavior. The results show that the coordination techniques developed in the previous work are not always beneficial and that this cooperative model displays diminishing returns.
Multi-agent systems offer many advantages over their single agent counterparts. The parallel nature of multi-agent systems facilitates scaling to handle larger, more diverse problems. The redundant property of multi-agent systems provides robustness with graceful degradation in the event of individual failures. Simple control architectures are often sufficient for the agents since multi-agent systems take advantage of emergent behaviors that arise from inter-agent actions and the interaction between the agents and their environment.
However, these advantages do not come for free. Coordinating the actions of the agents is not a trivial problem. Predicting and controlling group behavior is not a straightforward task because the relations between the system parameters and the group behavior are often complex. This research is focused on studying the parameters that effect coordination within multi-agent systems. Part of this process involves creating a method through which one can measure the effectiveness of a group's coordination. This paper describes one such method as it examines the relationship between group size and the group's performance.
Distributed artificial intelligence has worked extensively on the problem of coordination ([1], [12]). However, the majority of the work in the field uses sophisticated individual agents, with belief systems and mechanisms that allow them to estimate the state of other agents and how to react to the information gathered. These agents are relatively complex and the behavior generated as they interact with each other is even more complicated. Design issues in these systems have remained hot research topics. Instead of adding to the complexity, Ferber [6] has worked with reactive agents. Reactive agents are stimulus-response machines, without any state or planning capabilities. Yet, in the work described by Ferber, the agents could only communicate by altering objects in the world. There were no facilities analogous to the auditory system. Mataric's [9] work on coordinating simplistic agents, the agents are given a variety of primitive actions, but none of the actions involve communication. Coordination in these models is based solely upon visual input. Looking at animal societies, one notices that auditory communication can coordinate activity (elephants [13], vervet monkeys [15], and Belding's ground squirrels [16] are all examples of auditory animal communication systems). These societies can be used as inspiration for using undirected communication schemes to coordinate reactive agents.
Indeed, there has been work done on evolving communication systems with simplistic agents. MacLennan and Burghardt [7] describe their model within which they evolved a communication system. In their experiments one agent was in a position to receive environmental cues. This agent was then given the opportunity to communicate with other agents to inform them of the current state of the world. The others are rewarded for performing the proper action in response to the environmental cue provided to the single agent. With the aid of a genetic algorithm, agents evolved that were able to reliably respond appropriately to the environmental cue. Noble and Cliff [11] have reproduced and critiqued MacLennan and Burghardt's work. Their work can serve as a reminder that even in the simplest systems, small assumptions in design can have substantial side-effects in performance. Yanco and Stein [19] used two robots in a model similar to MacLennan and Burghardt's. The ``leader'' robot would receive an environmental cue then transmit a signal to the ``follower''. Their robots converged upon a communication scheme via reinforcement learning (the learning signal was supplied by humans observing the robots). Saunders and Pollack [14] describe a model that utilizes continuous channels of communication instead of discrete symbols. Their work evolved agents that would use one communication channel for recruitment in a search task. These systems all share the characteristic that communication occurs between only two agents, which could eliminate some of the advantages that communication systems have to offer.
Werner and Dyer [17] presented a model of a communication system evolved within a system of many agents interacting in a two dimensional environment. The females in their model were unable to move but were able to see and speak. The males in the model were able to move and hear but were blind and mute. After many generations of a genetic algorithm, the population of males and females converged upon representations that allowed them to efficiently find each other via the female's instructional signals. This model, along with some of the models mentioned earlier make distinctions between the sender and the receiver in the system. If an agent is designated as a sender, and others are made to receive the messages, then communication has to occur. In a sense, there is no other solution to the problems at hand besides communication.
Werner and Dyer [18] introduced a new model without these distinctions. They created `BioLand' where the agents were modeled after Braitenburg's vehicles [4]. The model developed agents which displayed predator/prey dynamics. Though the agents were capable of communicating, the agents did not utilize a communication system. The lack of communication was attributed to the success of the agents' visual system. The agents were capable of visually sensing enough information for their survival and there was no need to communicate.
Drawing from the previous simulations, as well as from animal societies, I designed a new artificial world to study undirected communication schemes and their potential coordination benefits. The world is updated in an asynchronous manner. An object is picked at random and then is activated. When the object is done performing its actions, another object is picked. Agents are allowed to roam freely about the world and since it is toroidal, they cannot fall off the edges. There is a coordinate system on the world, with each object only one spatial unit in size. Any number of objects can be at any spot in the world.
The agents have initial health values, which are reduced each time they are activated. When the agent's health value reaches 0 it is considered dead and removed from the world. Currently, only homogeneous populations of agents are introduced into the world. By creating a population of agents from a single genetic representation, the agents can take advantage of the fact that they will only encounter agents that are identical to themselves. A biological analogy would be the similar innate behaviors found in a closely related group of animals.
In addition to the agents, the world contains areas spanning many spaces that either increase or decrease an agent's health. These areas are meant to be abstractions of food and danger. In a real world search task, these areas could represent various goal objects and novel obstacles. The areas appear periodically in random locations and would remain for varying durations. The areas are biased towards the dangerous type to create a less agent-friendly environment. Mobile predators are also part of this world and their sole purpose is to decrement the agent's health.
The agents have 6 input channels. A single tactile channel responds to objects in contact with the agent. They have one visual channel, of a very limited range, that can sense immediately ahead, with a 40 degree field of view. They have four auditory channels, one for each direction. All the types of objects in the world have a different identifier, detectable on the visual and tactile channels. There are three distinct auditory signals recognized. The signals are discrete, in that they are heard or not heard. The clarity or strength of the signal does not degrade within an agent's sensory range.
The range for vision is five spatial units while the auditory system has a range of fifteen units. The values for the vision and auditory ranges attempt to model an agent with poor vision and decent hearing. Tall grass can limit visibility for smaller animals but their hearing is mostly unaffected and elephants use low frequency signals in order to communicate distances much further than they can see. There is no facility that the agents can use to maintain an internal sense of state. Severely limiting the abilities of the agents is an attempt to insure that the behaviors are emergent rather than an inherent ability. This work's long term goal is to study the development of intelligent systems, without necessarily developing intelligent agents.
The behavior of an agent is controlled by a simple production system. Each agent can have up to ten rules. The conditions of the production rules are combinations of possible input values logically OR'ed together. A logical NOT effecting the entire set of conditions is optional. If a production rule's condition is matched by environmental cues received by the agent, then one of seven actions is performed:
Each time an agent is activated its health value is checked. If it is zero or less the agent is removed from the world. Otherwise, information is gathered from the local environment according to the limits of the agent's sensory system. This creates a list of inputs to use within the production system. The inputs are stored in a limited sized buffer to simulate a finite mental capacity and an imperfect sensory system. Thus, there is no guarantee that all the inputs (or any specific input) from the environment would be available to the agent. The rule set then uses the inputs to trigger actions, with the actions taking effect immediately. Finally, the agent's health value is adjusted. One health unit is subtracted for the activation, and whenever an agent contacts a beneficial or dangerous area its health is also appropriately adjusted.
The predators in the world are similar to the agents with only a few differences. Their sensory system has 3 visual channels (forward, left and right) with a greater range (15 units) and no auditory channels. They do not have the ability to emit sounds. If a predator is in contact with an agent, it will subtract a certain amount of health from the agent and add it to its own health. In order to make the predators a real threat, the predators' activation routine will loop probabilistically. This results in the predators being able to move several spaces per activation, essentially making them `faster' than the agents. Also, the production rules that control the predators do not evolve, they were designed by hand and unchanged in order to remain a constant threat. Their rules instruct them to head towards any agent they see. If a predator does not detect any agents, it will move forward, occasionally turning to the left or right.
Early experiments [3] used a genetic algorithm to search through the space of rule sets to control the agents. Eventually a cooperative foraging behavior was evolved using a population of 15 identical agents. The foraging was accomplished by two rules -- one that emitted a signal when food was found and another that oriented towards the signal when heard. Although this behavior does not directly help the sender, this communication does help extend the average life span of the group. The average life span is used to calculate the fitness of the homogeneous group's control set. The genetic algorithm then selects for these behaviors.
Later work [2] introduced the non-evolving mobile predators to the artificial world. Again, a genetic algorithm was used to evolve the rule sets further. A derivation of the foraging communication scheme was discovered. The general purpose recruitment scheme emits the attracting signal when food is found as well as when a predator is found. This behavior sounds counter-intuitive at first, but does extend the average life span of the agents more than the foraging call. This scheme takes advantage of the simple architecture of the predators. When the agents crowd the predators, the predators are not able to accurately track any particular agent. This distributes the damage done by the predator among all the nearby agents, as well as sometimes even disorienting the predators enough that they lose contact with the flock of agents entirely. Indeed, this phenomena is common in natural systems and is known as the ``confusion effect''[5].
Another communication scheme evolved that used two different signals -- one in response to food and one in response to predators. The agents orient towards the signal emitted for food and away from the signal generated for the predator. This scheme also had a successful derivation. Some rule sets found by the genetic algorithm would propagate the alarm call. That is, when the predator call was heard, not only would the agent orient away from the signal, but the agent would emit the alarm signal as well. This extended the effective range of the alarm call, providing the information of a threat to a wider audience.
The last two communication schemes mentioned above were examined in this work. They were chosen because it was not clear if they would continue to produce beneficial results as the number of the agents increased. Since the model uses undirected communication, population density effects the number of recipients for each signalling. The more dense the population is, the more likely a larger number of agents will receive the signal. This behavior can lead to a noisy environment, where the abundance of signals becomes confusing and diminishes the value of the signals.
To test the effects of population size on group behavior, three agents were placed into the world with fifteen predators. The average life spans of the agents in the populations were recorded. To account for the variation in performance of the agents, this procedure was repeated nine more times and the values (average life span) were averaged over the 10 samples. This methodology was then applied with agent populations of size seven, ten, fifteen, twenty-two, thirty, forty-five, sixty, and seventy-five. The predators were kept constant at fifteen in order to keep the environment as constant as possible while the agent population size changed.
The task of survival was chosen because it had the advantage that it can be accomplished as an individual. Foraging is a task that can be performed as an individual or as a group via communication. Allowing foraging to effect survival creates a relationship between cooperation and survival. The task doesn't demand cooperation or coordination, but individual performance can benefit from it, and it is a measurable benefit (increases in average life spans). When evaluating the performance of various population sizes, a similar metric is needed. This work proposes dividing the average life span of the group by the population size, creating the coordination advantage :
This value determines the cases where the agents are actually coordinating their actions enough to benefit the group's behavior. This quantifies the effects of the emergent group phenomena as a measure for each agent's average contribution to the group's overall fitness. Figure 1 shows the Coordination Advantage values for the two models tested so far. The graph shows that the advantage is lost as the population size grows, reaches a minima, then starts to climb back up. However, the minima for the two schemes have different values and occur at different population sizes.
Figure 1: The coordination advantages for the agent populations that don't propagate the alarm signal and that do propagate the alarm signal. The propagation of the signal is more efficient with smaller population sizes, but then loses its advantage as the population size grows.
Population size plays an important role at the extremes of Figure 1. When the population is small, the agents would have to die very quickly in order for them to have a small Coordination Advantage (since the denominator is small). This is unlikely due to the imperfections of the predators -- they just aren't that efficient. In smaller populations, the propagation of the alarm call proves to be a better strategy, as the signal range of the individuals is extended via the propagation.
When the population is very large, the Coordination Advantage begins to increase. This can be attributed to the confusion effect. The large number of agents makes it hard for the predators to track any particular agent. While other communication schemes explicitly attracted other agents to confuse the predators, the confusion effect can also be seen as a side effect of a large population of agents. The random distribution and movements of the agents can be enough to keep the predators from tracking any particular agent.
This leaves the propagation of the alarm call responsible for the differences in behavior for moderately sized groups. By propagating the alarm call, the agents are able to coordinate their activity better while the populations are in the low and middle ranges. In fact, all the population sizes of twenty-two or smaller are more productive per agent when the alarm calls are propagated. As the population size grows, less communication (no propagation of the call) is a more effective scheme.
Indeed, the extra communication in large populations that propagate calls degrades the performance of the group as a whole. The agents are propagating the call to too many other agents as the signal spreads too far. This creates a feedback effect, as the agents receive signals that were generated in response to their own, or even worse -- that have wrapped around the world. The significance of the signal becomes questionable as an individual cannot tell how immediate the threat is. In some cases, the threat signal could drive the individual away from food sites, even when there is no nearby threat. Therefore, propagating the alarm call isn't effective in large populations. But through the confusion effect, the agents are able to increase their Coordination Advantage in large populations, even though it is not explicit coordination.
In order to gain another measure of the effectiveness of the group, the amount of food foraged by the group was measured. This data doesn't rely on the abilities of the predator, but only on the ability of the agents to cooperate as a group. From one population size to the next, the amount of food gathered increases (due to more agents) so the change in harvest amount is measured instead, and that is averaged over a population size.
This data in Figure 2, shows that there are diminishing returns when it comes to foraging. The larger groups are again able to collect more as a whole, but the performance does not steadily increase. In this case there is not competition for the food, but instead, the agents are not communicating clearly. The excess communication deteriorates a large group's effectiveness, through inaccurate warning signals. As more agents are added to the system, the individuals become increasingly less productive. In smaller groups the propagating alarm call provides additional warning for the agents. This allows the individuals to live longer and have more chances to harvest. These agents end up being more productive individuals on average.
Figure 2: The amount harvested per individual changes with the population density. For instance, the average individual in the population of size 7 harvests more than the average individual in a population of size 3. The amount harvested increased by 6.14 items in the non-propagating case and 13 in the propagating case. As the population size increases, productivity of the individuals obeys the law of diminishing returns. The propagating model peaks earlier, showing that in small groups, the agents are able to forage more as they have a better warning system. In large groups, there is excess communication which degrades the signal propagating group's effectiveness.
The Coordination Advantage value proved useful in analyzing the differences between communication schemes. By looking at the graphs of performance over the population size, one can infer that the global trends (the U shaped curves) are due to environmental traits. The differences between the trends, the local changes, then can be attributed to the behavior differences. Via the Coordination Advantage metric this work has shown that there is an advantage to be gained at smaller population sizes with the propagation of the alarm call. However, the effort of propagating the call is wasted as the agent population increases.
Note that as each larger population dies off, the population size will enter a smaller range where communication does have benefits, which should increase their effectiveness. Yet it the end, some of the larger populations still have very bad Coordination Advantage values. This could be explained by the agents leaving food sources when they hear alarm calls. If alarm calls are propagated over relatively long distances, the agents would be leaving food sources for threats that are not nearby. This prevents the agents from extending their life spans -- which decreases their Coordination Advantage value. The decrease in the amount of food foraged seems to support this hypothesis.
This model demonstrates that there are trade-offs between explicit coordination and population size. While the system harvests optimally at moderate population sizes, the average lifetime does not reflect that. This result reinforces the notion of coordination that arises as a side effect from the interactions between the agents and their environment. The environment does not have an intrinsic limit, creating the diminishing return. Instead the phenomena responsible for the diminishing returns arises from the interaction of the agents with each other. Their success is not due to their coordination, but instead the sheer number of agents in large populations is able to confuse the predators, making the predators less effective. This type of coordination is hard to plan for and can even be difficult to identify, but that does not mean it will not play a role in group behavior.
It would be of interest to further investigate the communicating animal societies, like Belding's ground squirrels and their alarm calls, to guide further research. In natural systems it isn't clear whether population size was limited by the effectiveness of communication or whether population size, limited by other forces, facilitates cooperative communication. This model provides a framework within which one can study the interplay between group size, communication, and group behavior, with the possibility of gaining insight into the behavior of natural systems. Regarding the design of multi-agent systems, this work also exposes some of the limitations of the systems. The systems cannot escape the law of diminishing returns, but we can study the agent-environment interactions to better predict the effects of system parameters on final returns.
This research is supported by the National Science Foundation under grants GER93-54898 and CDA93-03189.
 |
EMail Contact: Complexity International Editor