Belief propagation in multi-agent communities
Juan de Lara, Manuel Alfonseca Juan.Lara@ii.uam.es, Manuel.Alfonseca@ii.uam.es http://www.ii.uam.es/~jlara, http://www.ii.uam.es/~alfonsec Dept. Ingeniería Informática, Universidad Autónoma de Madrid Ctra. De Colmenar, km. 15, 28049 Madrid, Spain This paper has been submited to JASS. It is an interactive
article, in the sense that it has interactive simulations in it.
This article has been generated automatically using C-OOL.
Abstract
In this paper, we present several experiments of belief propagation
in multi-agent communities. Each agent in the simulation has an initial
random vocabulary (4 words) corresponding to each possible movement (north,
south, east and west). Agents move and communicate the associated word to
the surrounding agents, these agents can be convinced by the 'speaking agent',
and change these corresponding word by 'imitation'. Vocabulary uniformity is
achieved, but strong interactions and competition can occur between dominant
words. Several moving and trusting strategies as well as agent roles are
analyzed.
Keywords
Agent-Based simulation, Web-based simulation, Multi-Agent Communities, Belief propagation.
Introduction
Computer modellization of large communities [Resn99]. is an active area of research.
Several objectives can be pursued with this kind of simulations:
- Resolution and optimization of mathematical problems [Dori96].
- Study of emergent global behaviour and social interactions [Edmo98],
[Daut97]. In this paper, we will focus in these kinds of experiments.
- Study of population tendencies and evolution [Ophi98].
Obviously, validation of simulations of kind two and three is difficult, or impossible in
some cases. Care must be taken when making generalization and analogies from simulation
results. Anyway, by means of computer simulation, we can obtain data that would be impossible
to obtain by other means, or at much lower costs.
Social interactions can be studied in several ways:
- By means of robotic artefacts [Daut99].
- By means of software artefacts. In this case, several techniques and formalisms
have been applied successfully to community simulations, among others:
- Software agents, in which population individuals are treated as separate entities
able to exhibit an autonomous behaviour in a common micro-world. Some kind of intelligence can
be assigned to each agent [Wool95].
- Genetic programming, where population individuals are usually much simpler than
in the previous case, but the emphasis is put on evolution rather than on social interactions.
- Cellular automata, in which the micro-world is represented as a regular n-dimensional
grid, where the state of every cell at each time step depends on simple rules involving each cell's
neighbours [Hegh98].
Our approach is similar to software agents, but agent complexity is reduced to a minimum: their
behaviour is governed by simple rules, limited memory and limited world perception. To construct
the simulation, we use our own object oriented simulation language: OOCSMP [Alfo99].
This language is specially suited when simulations are composed of similar interacting entities
that can be modelled as objects. A compiler that we have constructed for this language allows us
to obtain easily Java applets and HTML pages from the simulation models.
Other courses and interactive articles generated with these tools can be accessed from:
http://www.ii.uam.es/~jlara/investigacion
In this paper, we present several experiments and situations related to information and belief
propagation. In some of these situations agent roles are used, in others, we also investigate
different belief propagation schemes.
This work has some common points with memetics [Dawk76], in which the replicating
units are the ideas [Hale98]. However, our agents do not transmit ideas or guides
for agents behaviour, at least in a direct form. We don't consider evolution or reproduction, either.
What our agents transmit are 'words' that name each of their possible movements. What is more, we
don't share some of the memetic stances.
The paper is organized as follows: section 2 presents the world of the 'talking bugs' and the
basic experiments. In section 3 we describe some other experiments that add non-determinism to
the way agents trust each other. In section 4 we present several agent strategies for belief
transmission. In section 5 experiments are carried out with roles.
Finally, in section 6 we present the conclusions
and the future work.
The world of the 'talking bugs'
Our micro-world is a 20x20 mesh, with periodic boundary conditions, namely, the north
mesh border is connected with the south border and the east with the west in the form
of a plane torus. The mesh defines the number of different agent positions, in this
case 400. Each position can be occupied by zero or more agents.
Agents have a word to designate its movements to the north, east, west and south.
In our experiments, each agent will start with a random word for each direction, and there
are 1000 different words. In the simulation, a word is represented by an integer number.
At each time step, every agent will move randomly, and then communicates the word associated
with this movement to the agents it encounters. If their words are different, the colliding
agent has to decide to believe in the other agent (and change its own word) or mantain its previous belief.
For this basic experiment, each agent has also a 'belief indicator', that measures the degree
of confidence the agent has in each word of its vocabulary. This indicator grows
(reinforcing) when the agent finds another agent that uses the same word. In the
case that two colliding agents use different words, the agent with less confidence changes its
word. In a draw case, a word becomes dominant.
In this way, the main simulation loop is composed of three main steps:
- Each agent choses a movement. In this case, randomly.
- Each agent move to a new location.
- The agents sharing the same location 'talk each other'. For this basic experiment, the
agent with the strongest belief keeps its word, the other agents change their word and their
associated belief indicator to the 'winning' word. Each agent in the same location
communicates in turns, the communicated word is the one associated with its last
movement. This experiment is a kind of 'imitation' game: one agent shows the other how it names
one movement, and the others imitate it (if convinced, i.e., they have lower or equal belief indicators).
We have made experiments using 400, 600 and 1000 agents. In all cases, the simulation ends in the
establishment of a common vocabulary for all movements. Notice that there is not a a-priori 'better word', agents don't
have any global information of the situation, only local interactions are allowed. The next
applet shows one of the simulations carried out (with 400 agents). The upper left panel shows the mean deviation of
the four words in the agent community. When this deviation reaches zero for one word, there is
a general consensus to designate the associated movement. The upper right panel shows a listing
with the mean of the words. When the deviation is zero, this panel shows the word that the
community has chosen to designate each movement. The lower left panel shows the mean of the
belief indicators of the community for each word. For this basic situation, this quantity is
always growing. The lower right panel shows a map of all the agent positions. The colour
represents the word chosen for the "north" movement. This panel is specially interesting,
because it is possible to observe the dynamics of word distribution during the simulation.
Press the 'Continue' button to start the simulation
This is the complete OOCSMP code for the previous simulation.
In our results (in the range from 400 to 1000 agents) the time to reach a uniform
vocabulary does not depend on the number of agents involved in the simulation.
In the simulation, it can be observed that belief indicators increase faster for
the word that takes longer to reach a general agreement. It is always like this in this basic
experiment. Sometimes acquisition of uniformity for a particular word takes a long
time, and the mean deviation panel shows a straight line parallel to the X axis.
The cause of this delay is that the agents split in two sets, each group believing
in its own word with similar degree. Belief indicators grow much faster in
these situations.