Next: Learning Classifier Systems
Up: EMuds
Previous: Games and Text-based Virtual
Subsections
The objective of the model presented in this chapter is to provide an
experimental platform for multi-agent systems that can be used as an
abstraction for a network of computers. The concepts used to define
this model are strongly inspired from the Internet games called Muds
that were introduced in the previous chapter. Designing the system
was done by separating structural elements such as space topologies and
contents from the dynamics of the environments considered.
The resulting model gives an abstract description of virtual universes
that can easily be implemented on computers [49]. These universes can
either be seen as purely virtual structures or as a representation of
real world problem domains. When used as an experimental testbed, an
EMud environment will be implemented as a representation of a problem
that must be solved by agents living in it. To the agents, on the other
hand, the world acts as a purely imaginary structure in which they can
perceive local properties and change them, and where they must adapt their
behavior.
An EMud is an application that manages environments called Worlds. The
worlds define environmental structures and associated dynamics and
thus provide experiment testbeds. I will define here the model used
to describe a world.
Worlds can be described by separating structure and dynamics,
structure consisting in the virtual physical components of the world
and dynamics in the virtual physical laws that the structure obeys.
There are three main types of components in the world structure. These
components globally define the world's topology and are called
parts. The various parts, with the most important features in their
implementation scheme, have been outlined on figure
6.1 at the end of this subsection.
Elements are the physical objects of the virtual world. The objects
that have a substance and thus can be manipulated by other elements
possessing adequate detector/effector (in a general sense) equipment.
In comparison to the real world, elements are the car you drive, the
glass you drink from, your cat and even yourself or other human
beings. As seen from the preceding examples, elements encompass both
the intuitively active and passive objects of the
environment. Elements that can ``contain'' other elements are called
containers and are a specialisation of elements.
Spaces are the places where parts dwell. They serve as a mean to
regroup subworlds into zones and they provide a location
for elements to exist in and sense their surroundings, as well as
being the medium in which interaction can occur. Spaces come in two
varieties: zones that allow to regroup other spaces into areas and
loci which may hold elements. Within a locus, positions can also be
defined when specification is necessary. A room is a locus in a zone
and an inventory is a locus within a container.
An important feature to note is the recursive nature of spaces: spaces
may exist within spaces or elements. A typical real world example of
this is the universe space containing our galaxy space or a room space
containing crates that have internal space for contents. The default
top-level space is a zone called the void that contains all other
spaces.
Exits are the paths from locus to locus. The exits define the basic
physical neighborhood relation over spaces. Although the virtual
physical laws of an environment may define other neighborhood
relations, the exits form the basic topology for the set of structural
components. It is essential for any experiment to have at least this
topological feature, even though some active elements might not be
perceptually equipped to be aware of it.
Figure 6.1:
Structural components of and EMud.
 |
Elements within a world are given a set of perceptions (a sometimes
empty set). These perceptions consist in information channels where
events of a specific physical type or nature are recorded. The various
perceptible events are propagated through the world's structure
following rules of propagation defined by the actions that can cause
them, these events are only communicated to the elements if they possess
adequate perceptual channels, even if their position is ``within
range''.
Thus, shouting at a table (inactive, unperceptive virtual table of
course) has no effect on the table element. Generally speaking, if an
element is not perceptive to a specific type of physical event, that
type of event can have no effect on the element's internal mechanisms
(unless the event destroys the element, which then has no further
effect on the element...). Of course, the existence of translator
elements (comparable to radio receptors, magnifying glasses, etc.) is not
excluded by this rule, but otherwise, such unperceived events can be
considered as an epiphenomenon to the element in question.
Actions are the transformations that can be effected on the world's
structure. They are considered as components of the world in the sense
that elements may produce them and they are then stored until
execution time. Typical actions are moving, picking up elements,
emitting sound, etc. The events in the world that such actions
generate may be delayed or have durable effect, depending on the
action. To allow a variety of effects (such as temporary effects),
actions may generate other actions. A temporary effect is obtained by
an action that modifies the environment and then generates a new action
(with appropriate delay) to set it back to its initial state.
The set of all possible actions, with their internal applicability
rules, defines the physical laws governing the virtual world. This can
be understood by the fact that any transformation of the world must
result from the application of an action.
A component of the world that may generate actions is said to possess
skills, that is, a skill is the basic description of how an action is
to be generated. The set of skills of such a component is called its
proficiency.
Control algorithms are the means by which elements may
make decisions to commit actions in the world. As it was explained in
the element section, elements can be either active or passive. By
default, an element is passive, but it can be equipped with a control
algorithm that allows it to interact with the world. Such an algorithm
has access to both the perceptions and the internal state of the
element and from this information, may generate actions to effect the
environment.
Any type of control algorithm may be fitted to an element and in fact,
a human player connected to an element is considered as a control
algorithm (whatever the connection method). A typical experiment world
could contain elements driven by neural nets, genetic algorithms,
expert systems and remote human players connected via telnet ports.
Time in the EMud is a global, discrete ordering of the occurrence of
actions in the world. Since actions are executed sequentially, the
order of their execution is well defined and can be divided into time
slots. Every action has a positive integer execution delay that allows it to
be scheduled in world. The temporal evolution of the environment is
the sequence of environmental states taken before every time
step. In this context, the scheduler is the entity that coordinates all
actions in the world, it is through the scheduler that elements are
prompted for action and in the scheduler that element actions are
stored before the time of their execution (see figure
6.2 for an illustration of this mechanism).
Together, the previous components form the EMud world, where elements
``live'' in the structure formed by spaces connected through exits. In
this model, agents are implemented as elements with a control
algorithm. These agents, following our perception/action agent model
(see the section on autonomous agents), acquire information about the
world through perception channels and use actions as effectors to
modify this world.
Figure 6.2:
Scheduling of an element's actions.
 |
Environment definition is made by creating an appropriate set of
structural definition files and dynamics definition files that are
then loaded into the application at startup. A simple grammar based on
name-value couples is used for writing the files and each couple
represents a parameter of the environment in a hierarchical
manner. The hierarchical decomposition is done through the use of
complex values for certain parameter names. Typically, an element is
described as an ELEMENT name with complex value consisting in
the various parameters defining an element. Within this complex value,
a parameter named LOCATION would have a simple value that is the
integer identifier of the element's location in the EMud
environment. Examples of complex values are those associated with part
descriptions, element attributes or element proficiencies. Examples of
simple values are those associated with description names, exit
lengths or space sizes (see figure 6.1).
An environment will usually consist in many such definition files, the
minimal environment having one each of the default space, element and
exit files. When creating a more complex environment, the
configuration files may be structured into any number of environment
areas, with space, element and exit files for each area, along with
one area description file. Since the world is structured into
sub-spaces thanks to the use of the space parts, building an extension
to an environment is done by adding a new space called a zone. The new
rooms to be added are then situated in this zone, delimiting the newly
built area. Elements and exits added in rooms of this zone are also
marked with their current zone identifier. For each zone, a separate
set of definition files is used. When the EMud is running, the current
state of the mud can be saved into these environment definition files
and when the mud shuts down, this operation is automatically
launched. Thus continuity of the world can be established by starting
up the mud from a previously saved state and a study of the world's
evolution can access successive states of the world in these various
files.
Control algorithm states are also stored in a similar fashion as
environment description files, but the current implementation of the
model does not yet provide a way of defining new control algorithms
for the EMud without touching the code of the application. The EMud
actions are also only modifiable at this time by transforming the EMud
application.
In an EMud, all parts are uniquely distinguished by a part identifier
that specifies their zone membership , their type identifier (whether
the part is a room, an exit, a player or another part type), and their
personal identity within these subsets of parts. This constraint of
unicity limits the maximal size of an EMud world to 254 zones,
each containing a maximum of 220 parts of each type (about a
million). Obviously, this limit is not too restrictive and I believe
the processing power of current computers is more the limiting
factor at the moment. I have currently implemented seven zones for
demonstration and experimental purposes, altogether containing about
300 parts among which twenty are active and controlled by elementary
control algorithms. In this configuration, no delays at runtime are
perceptible, but the use of complex control algorithms, such as an XCS
classifier system with a population of classifiers over 1000, does slow
down the environment slightly. It should be noted that, since its
complete rewriting in a project in collaboration with A. Soupper, the
application has become very stable, running for several weeks without
interruption.
The EMud environment model provides support for multi-agent system
experimentation. Special attention has been devoted to allow adaptive
agents to evolve in incrementally complex environments. To
fulfill this goal, it is possible to build environments in steps of
increasing complexity along the three distinct directions described
below; from pure simulation, towards real-world modelling.
The model uses high-level descriptions of environments through the use
of three basic building blocks: elements, spaces and exits. This
allows virtual environments such as those found in the typical
artificial life experiments to be built. For example the Santa Fe
trail or the Woods experiments can be reproduced by using sets of
interconnected rooms containing pheromone or food elements. On the
other hand, abstractions of the real-world can be achieved with the same
building blocks, for example by mapping a building layout on the
rooms/elements/exits framework, identifying offices to rooms, doors
and stairways to exits, interior equipment to elements. Since the
number of such components can be very large, a lot of detail can be
used for these descriptions.
As the elements of an EMud can be given active properties and the
actions available to elements can be customized, the laws of evolution
of an environment can be closely tailored to the desired
simulation. Elements reacting to specific environmental conditions can
be used and even hidden in the environment, so as to simulate
atmospheric conditions for example.
With the possibility of linking elements of the EMud environments with
real-world objects (most often human actors), the basic unpredictibility
of the real-world can be introduced into environments and used to
modify them dynamically. This allows to build environments that might
bridge the gap between simulation and real world experimentation.
Next: Learning Classifier Systems
Up: EMuds
Previous: Games and Text-based Virtual
Antony Robert
2000-02-11