Navigation  without Java Scripts

LEM - Multi Agent Simulator Implemented
in Visual Prolog

Serguei Krivov** Anju Dahiya* , and Jaweed Ashraf *
**: scholar of Intercultural Open University, The Netherlands
present add: Indian Inst. of Ecology and Environment
A-15, Paryavaran Complex,
New Delhi 110030 INDIA e-mail: s_krivov@hotmail.com
$ * : Lab. 317, School of Life Sciences,
Jawaharlal Nehru University,
New Delhi-110067 INDIA e-mail: a_dahiya@hotmail.com
$ : address for correspondence

 Abstract

In this paper we describe implementation of general-purpose ecological-simulator called LEM (Logic for Eco- Modeling). LEM is a forward chaining rule-based system that supports interactive development of individual-based ecological models. The behavior of agents and reaction of environment on the actions of agents is specified by the sets of production rules. We have developed a number of ecological simulation sample models such as migration of avi-fauna within limited space; emergence of communication and cooperative behavior under various conditions and evolution of complex food webs in an ecosystem. No knowledge of computer languages is required for developing new models under LEM. It seems to us that LEM is the first general-purpose, individual-based modeling tool that could completely relieve ecologists and Alife researchers from programming work. Prolog has not been used earlier for developing simulators and the main objective of this paper is to show how Visual Prolog could be used for building simulators.

Key Words: LEM; multi-agent simulation; rule-based programming; model; trial-resolution-result algorithm.

1. Multiagent Simulation – New Approach to the Study of Complex Adaptive Systems

‘Complex adaptive system’ (CAS) is the term used to refer to a system with the following properties (Hraber et al.[13]): a collection of primitive components, called "agents"; nonlinear interactions among agents and between agents and their environment; unanticipated global behaviors that result from the interactions. Agents adapt their behavior to other agents and to the environmental constraints, thus behaviors of component evolve over time. Eco-systems and economies are often considered as an instances of this category of complex adaptive systems (Forrest and Jones [11]; Holland [12]; Hraber et al.[13]).

It is difficult to write a system of differential equations that take into account more than two or three factors that contribute to system dynamics. Useful and predictive mathematical treatments are difficult, primarily due to the non-linearities, discreteness, spatial inhomogeneities, and the changing behavior of the primitive elements of the system (Hraber et al.[13]). Such a complex system could be studied by creating an artificial universe of robotic animals via computer simulation and conducting experiments in so created universe. This approach termed as ‘multiagent simulation’ or as ‘individual based modeling’ has emerged during the last decade (Hraber et al.[13]; Drogoul and Farber [2]).

Development of a multiagent simulator that reproduces natural behavior in simulated environment is significant for enhancement of robots that operate in real environment. However, most often multiagent simulation is used as a tool for research in ethology and ecology and economics. The Boids by Reynolds [8], Tierra by Ray [7], ECHO (Holland, [12]), ant model – MANTA, (Drogoul and Ferber, [2]), LEE (Menczer and Belew, [6]), Food web simulator – Gecko, (Schmitz et al., [9]) are examples of multiagent simulators. Ecological concepts considered in these simulators are as follows: Trophic levels, Food chain and Food web, Community assembly processes, Niche, ,Biodiversity, Patchiness, Seasonality.

We believe that the development of methods for Multiagent simulation of societies may bring considerable contribution to the science of animal behavior and the study of ecosystems. This belief inspired us for a research project related to the development of a Visual Prolog based system for multiagent simulation of ecosystems. The overall structure of LEM models, syntax of model specification language and the functionality of LEM modules and a provisional manual for LEM users, are now available on Internet at the URL (s)-

http://www1.50megs.com/lem/ OR http://www.50megs.com/www1/lem/

http://geocities.com/SiliconValley/Cable/3109/

2. Logic Based General Systems Theory as a framework for modeling and simulation of CAS

2.1 Logic Based approach to General Systems Theory

Logic based approach to General Systems Theory has been introduced earlier by Krivov [5] as a formal framework for modeling and simulation of Complex Systems. This framework serves as the methodological basis for the implementation of LEM.   Krivov also showed that the new approach to system modeling is especially appropriate for research on Artificial Life and Complex Adaptive Systems. Its utility is illustrated by the fact that it provides natural expressions for such concepts as pattern of organization, emergence and evolution, chaos, order.

The starting point of Logic based approach to General Systems Theory is the observation that the classical definition of a system (Klir, [14]) is virtually identical to the definition of Model in predicate calculus. Models are used for the representation of algebraic structures such as groups, rings, fields’ etc. (Suppes, [17]; Lightstone, [15]). However, these may also be used as semantic structures representing the meaning of natural language expressions. Model and System both are defined as a pair <Objects, Relations> where Objects is a set of objects described and Relations is a set of relations i.e. predicates of different arity which pertain to the objects. The similarity between the definitions of a system and of a model brings forth the possibility of designing a logic based axiomatic theory of systems. The formal framework designed is the result of refinement of Krivov's earlier papers, where he considered the prospective for the use of models for description of imaginative activity (Krivov, [3]) and reasoning about common sense situations (Krivov, [4]).

The main idea of the present proposal for Logic Based General Systems Theory is the use of ‘models’ for the description of system states and histories. Model is redefined as a triple:

<Objects,Relations, ModalOperators>[time1,time2,time3…time_n];

Where the set ModalOerators describes interactions between Objects that take place during the given time-sequence and set Relations describes the relations between the Objects. Isomorphism of models may be interpreted as isomorphism of systems. When one model has different isomorphic images in some other model, it is a repetitive pattern for that model. A model has symmetry when it has an isomorphic mapping into itself. The existence of a repetitive pattern usually implies existence of some symmetry.

The dynamics of a system is described by the set of dynamic patterns:

Cond(t1),Cond(t2),…,Cond(tn)->OPS(tn+1) (If condition of the RHS could match the model then the model should be extended by the set of modal operators OPS(tn+1) that describe the state of the system at the time tn).

The Logic based General Systems Theory facilitates formal definition of the 'pattern of organization' that is more general and even more natural in comparison with such definitions phrased in terms of cellular automata or formal grammar theories. In consequence, the proposed theory gives a novel view of 'organization', 'structure', 'behavior', 'chaos', ‘order’, and 'emergence'. Logic Based General Systems Theory is intended to be a framework for simulation and analysis of Complex Adaptive Systems i.e. ecosystems, social systems, economies etc.

2.2 An abstract model of a Complex Adaptive system

Krivov [5] introduced the abstract computational model of the ecosystem. This model is based on the theoretical framework designed. The core algorithm of LEM is a practical implementation of this abstract model.

In the model agents are considered as collections of states and rules that define the agents' actions and states, depending on the state of the environment. Environment is a collection of cells that store agents and modal operators describing both the agents' actions and the reactions of the environment to their actions. There are two kinds of rule tables. Action_Table is a set of rules for computing actions. It is associated with agents. The_Law is a set of rules for computing the reactions of the environment to the actions of the agents. In the model the environment is reduced to the set of production rules that defines the outcome for all possible patterns of interactions that may take place in the ecosystem. . In fact, all the properties of the environment are completely defined by this rule table; it defines "The Laws of Nature" for the given system. The rules of this table could define patterns of social interactions, patterns of chemical reaction, or even a discreet approximation for the dynamic equations of a particle moving in the field of force. This model facilitates the study of adaptation and natural selection. The definition of the environment via rule tables reduces the problem of classification of the environment to classification of the logical properties of the production rules that constitute the environment.

Ecosystem is defined as a couple <{Site}I,The_Law >, where {Site}I is a square grid of sites and The_Law is a set of rules that define the law of interaction in the ecosystem.

Each site is a container that can keep a number of agents, relations, and operators. Thus at any particular moment of time a site may be represented as a model:

<Agents, Predicates, Operators >.

As far as LEM is concerned regarding the implementation of the Abstract model of CAS , there exist one to one correspondences between the description of LEM core algorithm and the description of abstract model. Last two sections of this paper are devoted to the detailed description of LEM architecture. A detailed description of abstract model may be found in the Ph.D. thesis of Krivov [5].

 3. The structure of LEM models

3.1 Agents

Agents are main entities of a LEM model. There are 3 main categories of agents: Envo-agents, Producers and Etho-Agents. Besides these three, there is also a special class of agents called landmarks that serve for identifying places. Landmarks are visible only to the modeler and they do not play any role in interaction of agents within an ecosystem.

Each category of agents could be further subdivided into species. The agents that belong to the same specie have similar appearance on the screen. They have the same shape and color. They may also share some other parameters.

Envo-Agents represents non-living environmental factors such as buildings, rocks, lakes etc. They may be used for the representation of the types of landscape. They may also be used for representing those living elements of environment that are used by all other agents merely as elements of environment. Envo-agents have no state variables.

Producers represent the producers of the ecosystem. They have one integer state variable that represents their biomass. Producers have also fixed growth rate that is common for producers of the same specie.

Etho-agents represent primary, secondary and tertiary consumers. Only etho-agents are capable of generating actions. Each etho-agent has a schemata- a set of rules that define the behavior of the agent. The action of an etho-agent is calculated by applying the rules from its schemata to the current environmental conditions and the current states of the agent. Etho-agents could have any number of states. Each state has double representation- as integer and as symbol. The state map is the set of pairs <symbol, integer range> that defines the quality of the current integer state. Agents are sensitive only to the qualitative aspect of their states. Etho-agents are unisexual i.e. either male or female. They could interact with each other and they could interact with producers and envo-agents.

LEM-multi1.gif (82440 bytes)

LEM screenshot

3.2 Ecosystem

The eco-systems of LEM are grids of sites. Each site is a right square that could accommodate any number of agents of all the three categories. Landmarks are not kept on the sites, they are stored separately from other agents. In LEM, ecosystem agents could interact only with those agents that are located at the same site at the moment of interaction. From topological point of view the ecosystem is either 2 dimensional surface or tore. If an ecosystem is a 2-dimensional surface then all agents that reach the border of the ecosystem change their direction of motion by 180 degrees. If an ecosystem is a tore then all agents that reach the border of the ecosystem should vanish at the border and arrive from the opposite site of the ecosystem.

The most important part of LEM ecosystem is the rule table that specifies the patterns of interaction among agents and their outcome. This rule-table called The_Law assigns one reaction to each action of etho-agent. The producers that in fact are distributed on the site could receive many reactions during one time-step. The overall effect or the actual reaction on producer is obtained by summing up the reactions that producer had received.

Etho-agents are free to select any action which they "consider" to be appropriate under given environmental conditions. The law table defines the success or failure for the actions of the agents. Thus, it actually defines the environmental pressure that an agent has to bear. The law table is especially important for developing ALife evolutionary models. It gives an opportunity to study the evolution of the same category of agents under different types of environmental pressure.

3.3 Types of models

Currently LEM supports 4 types of models. The type of a model is to be specified by the term:

model_type(MODELTYPE1,MODELTYPE2),

Where MODELTYPE1 is either simple or evolution and MODELTYPE2 is either linear or cyclic.

In a simple model, all etho-agents share one set of schema. The schemata should be preprogrammed. This class of models is intended for individual based simulations of ecological systems. When MODELTYPE1 takes the value evolution each etho-agent has it’s own private schemata. The schemata are rules that define the agent’s behavior. In evolutionary models, these rules serve as chromosomes. It means that each newborn etho-agent inherits its schemata from parents after schemata of parents undergo the processes of crossover and mutation. MODELTYPE2 defines the representation of time in the model. The linear time is just integer value that denotes the current step of the simulation. In cyclic models there are options for representation of seasons and periods of the day i.e. morning, night etc. The day and the year could be divided into any number of periods. The modeler should specify the list of these periods and their duration.

3.4 Interactions of agents within LEM ecosystem

Unlike Swarm [10] LEM has only one rigid schedule of simulation. It would be appropriate to call it "Trial-Resolution-Result" algorithm (TRR). While designing this algorithm, we pursued the objective to represent the dichotomy between the `will' of an individual and the `will' of its surroundings in an algorithmic form.

There are 3 major steps in TRR algorithm: In the first step, all etho-agents select actions that they consider as being the most relevant to their current situation. The action of an agent could be either transitive i.e. directed to another agent, or non-transitive. While selecting, the action and making an effort to perform this action the agents enter into different forms of interactions with others.

In the second step, the actual results of the interaction are defined. As a matter of fact, viz. interactions of individuals in human, animal and even plant societies are often accompanied by the contradictions of `wills'. In such a case, the individuals participating in the interaction are `interested' in opposite outcomes from the interactions. The rule table-The Law-serves for the purpose of resolution of contradictions between individual efforts of agents. This table assigns certain symbolic or numeric value to the action of individual, which is called `reaction'. The `reactions' may denote success or failure as a consequence of the given action. They may also denote the income and the loss in the value of some parameter.

In the third stage, the real spatial positions and the states of the agents are modified according to the rate specific for the combination of given action and reaction.

3.5 LEM model specification

LEM models or model templates are specified via text editor in a special Model Specification Language (MSL). At the moment, this language consists of Visual Prolog terms. Loading and saving of models employ Visual Prolog Data Base predicates.

3.6 LEM database

LEM has fast internal database system that allows saving the most important elements of the simulations. Database could be kept in RAM or in hard drive. Database has a query system and a pattern tracer. Pattern tracer is a simple data-mining tool that allows detecting patterns in the information stored in the database.

4. How LEM Was Implemented In Visual Prolog?

4.1 OOP in Visual Prolog

Visual Prolog has full-fledged OOP subsystem that was extensively used in the implementation of LEM. The complete description of the subsystem is available online in PDC home page. In Visual Prolog, all Class predicates are as it is called in the C++ terminology Virtual methods. (Refer the Visual Prolog Manual [16])

4.2 Class Hierarchy

The diagram that represents LEM class hierarchy:

LEM-diagram.gif (6215 bytes) (click for full size)

4.3 One cycle of a simulation

This section describes the cycle of simulation. As soon as many classes are involved in the core simulation cycle the description will be given separately for each class.

One cycle of a simulation in Ishvara

The method step (integer NTimes) of the class Ishvara is the top predicate of the simulation cycle. As it could be seen from the method definition given below it call NTimes times the method step() of the class Ecosystem (ES:step())..

step(Times):-

ecosys(ES),!,

step2(ES,Times).

step2(_ES,0):-!.

step2(ES, N):-

ES:step(),

monitore_pop_dynamics(),

NN = N - 1,!,

step2(ES,NN).

The formal syntax for using the members of an object is:

[ObjectVariable:] name_of_member_predicate[( list_of_arguments ) ]

Here the square brackets are used to mark optional elements. (Visual Prolog Manual [16]). Thus code ES:step() , represents the call of predicate step(),which is a member predicate of object ES. Object ES belongs to the class Ecosystem.

One cycle of a simulation in Ecosystem

The following is the definition of method step() in class Ecosystem:

step():-kill(),

Dynamic::step_time(),

step_db1(),

step_agents1(),

step_sites(),

step_agents2(),

reproduce(),

step_db2().

The call of static predicate Dynamic::step_time() increments time variable. Methods reproduce()and kill() performs the operations of creation for agent that should be born and destruction of agent that should die. The call step_db1() performs necessary database initialization. The predicate step_db2() is responsible for tracing of patterns in runtime.

The predicate step_agents1() is defined as follows:

step_agents1():-

agent(_Id, Ag),

Ag:step1(),

fail.

step_agents1().

As it could be seen from this code, the predicate step_agents1() calls virtual method step1() for each agent kept in agents data base ( agent(_Id, Ag)).

Method step_sites() calls method Site:step() for each side kept in the site database (site(_X,_Y,Site)).

step_sites():-

site(_X,_Y,Site),

Site:step(),

fail.

step_sites().

The predicate step_agents2() is defined as follows:

step_agents2():-

monitore(Mon),

display_grid(Mon),

agent(_Id, Ag),

Ag:step2(),

Ag:monitore(gui,Mon),

fail.

step_agents2().

As it could be seen from this code , the predicate step_agents2() calls virtual methods step2() and monitore(gui,Mon) for each agent kept in agents database .

One cycle of a simulation in Site

The method step() of class Site is defined as follows:

step():-

retractall(reaction(_,_,_)),

retractall(moveto(_,_)),

time_from(T),

T1 = T-1,

retractall(sound(_,_,T1)),

death(),

the_law(TheLaw),

reactions(TheLaw).

The main task of this method is to apply the Law-rule-table to the set of agents located currently at the site. This task is accomplished by the call reactions (TheLaw) which is defined as follows:

reactions(TheLaw):-

TheLaw:rule(LHS,RHS),

matchlist(LHS,Env),

select(RHS,Choise),

firelist(Choise,Env),

fail.

reactions(_TheLaw).

One cycle of a simulation in agents

As it could be seen from previous section, two methods step1()and step2() of the class Agent play important part in simulation cycle. These two methods are `virtual' methods and they are defined by different ways in different subclasses of the class Agent. The definitions are as follows:

1. In Envo-agent

step1().

step2().

Both methods do nothing.

2. In Producer

step1().

step2():-

place(TheSite),

this(TheAgent),

TheSite:total_consumption(TheAgent, TC ),

growth_rate(GR),

biomass(BM),

NewBM = BM + GR*BM - TC,

NewBm>0,!,

assert(biomass(NewBM)).

step2():-

place(TheSite),

this(TheAgent),

assert(TheSite:saction(TheAgent, "producer" ,aact1(die))).

First method does nothing. Second one updates the variable biomass(Biomass)

2. In Etho-Agent

step1():- !,

do_action().

step2():- !,

change_state(),!.

First method computes the action of the agent and deposits the action into the site where the agent is currently located. Second method changes the states and the spatial location of the agent. The second method uses the facts

OldSite:reaction(TheAgent,_, React) and OldSite:moveto(TheAgent,xyza(X,Y,Z,A))

which come as the output from the method step() of the class Site.

do_action():-

place(TheSite),

this(TheAgent),

ag_specie(Sp ),

retract(TheSite:ag(TheAgent,Sp)),!,

compute_action(TheSite,Action ),!,

assert(myaction(Action )),

assert(TheSite:ag(TheAgent,Sp)),

assert(TheSite:saction(TheAgent,Sp ,Action)).

change_state():- !,

place(OldSite),

this(TheAgent),

OldSite:reaction(TheAgent,_, React),!,

OldSite:moveto(TheAgent,xyza(X,Y,Z,A)),

set_state(React),!,

update_route(),

set_location( xyza(X,Y,Z,A)),

world(EcoSys),

ag_specie(SpName),

Site::site_coord(X,Y,SX, SY),

EcoSys:site(SX,SY,NewSite),!,

retract(place(_)),

retractall(OldSite:ag(TheAgent,SpName)),!,

assert(place(NewSite),situation),

assert(NewSite:ag(TheAgent,SpName)).

5. How rule-based programming could enhance the simulation technology

Although LEM is rule-based system, it has surprisingly high performance. On Pentium 133 MHz, 32 Mb RAM LEM could handle a population of 1000 –10000 agents with a reasonable speed (0.2-1 steps per one second). LEM could maintain huge populations of agents. The maximum population that appears in one of the experiments is 18000 (Krivov [5]). However, this is not the ultimate limit.

LEM is applicable to the study of a variety of problems related to complex adaptive systems. These include, among others: migration; emergence of collective behavior; social interaction; sexual reproduction; evolution of environments; evolution of learning; multiple species, ecologies and even prey-predator population dynamics. Some important kinds of sample models (still in developing stage) implemented under LEM are:

  1. Daily migration of Peafowl in the Campus of Jawaharlal Nehru University (Dahiya et al., [1]). This is the part of an ongoing project (undertaken in collaboration with the lab. of Prof. Jaweed Ashraf at School of Life Sciences, Jawaharlal Nehru University, New Delhi) to design an individual based ecological modeling methodology for the assessment of the distribution of the individual species. The ultimate objective of this work is to create a computer program for environmental impact assessment.
  2. Emergence of communication and cooperative behavior under various conditions.
  3. Emergence and evolution of a complex food web in an ecosystem

The interactive character of modeling makes LEM outstanding among other general-purpose simulators. So far as LEM is based on rule based methodology it inherits all the strengths of this methodology along with the shortcomings. Nevertheless, LEM models are not as fast as compiled models. Our experience shows that the penalty for speed required while using rule based programming paradigm is negligible in comparison to the convenience and flexibility that LEM inherits from rule based systems. The specification of ecological model on specific to this area language makes LEM modeling affordable for ecologists (who do not have special training in programming). LEM supports interactive development of individual based ecological models. User could define any number of species of agents with different behaviors that belong to 3 basic types -environmental agents, producers, and etho-agents. Thus LEM could model ecosystems with an arbitrary and as complex food chain as desired.

We conclude with the hope that LEM will represent both a remarkable theoretical framework and a useful simulation tool for Ecologists and the Alife research community.

Acknowledgements

We are grateful to Carsten Cristoffersen from Prolog Development Center (PDC) Denmark for timely sending a complementary copy of Visual Prolog compiler. Outstanding features of Visual Prolog 5.1 helped Dr. Krivov to implement the design of LEM in a very short time. The grants provided by Council of Scientific and Industrial Research (CSIR), New Delhi, India, to Dr. Dahiya are humbly acknowledged. We are grateful to Peter Van Wonterghem, Ph.D. Scholar of Jawaharlal Nehru University who lent us his laptop for implementing LEM and typing this paper.

References

Journals & Proccedings:

[1] Dahiya, Anju, Serguei Krivov and Jaweed Ashraf (1999), "Study of route selection dynamics and local migration of avi-fauna within a real ecosystem using LEM multi-agent simulator", Proccedings of Vth International Conference on Cognitive Systems, Dec. 15th-18th- New Delhi India.

[2] Drogoul, Alexis and Jacques Ferber (1992). "Multi-agent simulation as a tool for modeling societies: application to social differentiation in ant colonies". Lecture notes in artificial intelligence, Cristiano Castelfranchi, Eric Werner (Eds.). Artificial Social Systems 4th European workshop on modeling autonomous agents in a multi-agent world, MAAMAW’92, S. Martino al Cimino, Italy. Springer Verlag, 830, pp. 3-23.

[3] Krivov, Serguei (1988). "On one version of Computer Methaphor". In: Proceedings of 25th All Soviet Union student conference, philosophy section, Novosibirsk University. (in Russian).

[4] Krivov, Serguei (1998). "The formal semantic for Jaina logic". Arhat Vachana. Vol.10 (4): pp 9-29.

[5] Krivov, Serguei (1999). A logic based framework for artificial Life. Ph.D. Thesis. The Inter-cultural Open University, The Netherlands.

(Web site: http://geocities.com/SiliconValley/Cable/3109/serguei.html

[6] Menczer, Filippo and Richard K. Belew, (1994). "Complex Environments to Complex Behaviors". Adaptive Behavior. Vol. 4(¾): pp.317­363.

[7] Ray T. (1992). "Evolution, ecology, and optimization of digital organisms". Santa Fe Institute working paper 92-08-042. (http://www.hip.atr.co.jp/~ray/tierra/tierra.html)

[8] Reynolds, Craig W. (July 1987). "Flocks, Herds, and Schools: A Distributed Behavioral Model". In: the proceeding of SIGGRAPH `87 (Computer Graphics 21(4), edited by Maureen C. Stone, pp. 25­34).

(Web site: http://reality.sgi.com/employees/craig/boids.html)

[9] Schmitz, O.J. and G. Booth. (1996). "Modeling food web complexity: the consequence of individual based spatially explicit behavioral ecology on trophic interactions". Evolutionary Ecology (in press).

[10] Swarm Development Group (1998). Brief overview of Swarm. SantaFe Institute. USA.

Books:

[11] Forrest, S. and T. Jones (1994). "Modeling complex adaptive systems with Echo". In: R.J. Stonier and X.H. Yu, Eds. Complex Systems: Mechanisms of Adaptation. IOS Press, Amsterdam. 3­21.

[12] Holland, J. H. (1995). Hidden order: how Adaptation builds Complexity. Addison- Wesley, Reading, MA.

[13] Hraber, Peter T, Terry Jones and Stephanie Forrest (1996). "The Ecology of ECHO". Artificial Life (in Press).

[14] Klir, George J. (1991). Facets of Systems Science. Plenum Press New York.

[15] Lightstone, A. H. (1978). "Mathematical Logic". In: An Introduction to model theory. H. B. Enderton University of California. Plenum Press New York. Pp. 107-128.

[16] Prolog Development Center (PDC), (1999).Visual Prolog reference Manual. PDC Denmark. (Web site: )

[17] Suppes, Patrick (1969). Introduction to Logic. 12th publishing D. Van Nostrand Company. INC Holland. Pp. 246-304.