Agent based modeling

• Filippo Castiglione, Institute for Computing Applications (IAC) - National Research Council of Italy (CNR), Rome, Italy

Agent-Based Modeling (ABM), a relatively new computational modeling paradigm, is the modeling of phenomena as dynamical systems of interacting agents. Another name for ABM is individual-based modeling.

Multi-agents systems: The emergence of complex behavior

Agent-Based Models (ABM) can be seen as the natural extension of the Ising model (Ising 1925) or Cellular Automata-like models (Wolfram 1994), which have been very successful in the past decades in shedding light on various physical phenomena.

One important characteristic of ABMs, which distinguishes them from Cellular Automata, is the potential asynchrony of the interactions among agents and between agents and their environments. In ABM agents typically do not simultaneously perform actions at constant time-steps, as in CAs or boolean networks. Rather, their actions follow discrete-event cues or a sequential schedule of interactions. The discrete-event setup allows for the cohabitation of agents with different environmental experiences. Also ABMs are not necessarily grid-based nor do agents "tile" the environment.

In particular, the richness of detail one can take into account in ABM makes this methodology very appealing for the simulation of biological and social systems, where the behavior and the heterogeneity of the interacting components are not safely reducible to some stylized or simple mechanism.

Computational science and simulation

Figure 1: Computational Science.

The modern scientific study of a phenomenon generally consists of three major approaches: theoretical, experimental, and computational.

The computational aspect is becoming increasingly important. Computational science has the flavor of both theoretical and experimental science. A good computational method often comes from a thorough theoretical analysis. On the other hand, the analysis of results is not much different from analyzing experimental data. Computational methods in science become advantageous when

1. the problem at hand is too difficult to do analytically;
2. an approximate theoretical result might not be reliable, and it is necessary to check it with a different method;
3. an experiment is expensive or not feasible to perform.

Mathematical modeling and numerical simulation complement the traditional empirical and experimental approaches to research since they provide effective ways for organizing existing data, focus experiments through hypothesis generation, identify critical areas where data are missing, and allow virtual experimentation when real experiments are impractical or just too expensive. Numerical simulations can also be used to forecast short and long-term consequences of particular choices of parameters and/or initial conditions in real experiments (de Oliveira et al. 1999, Stauffer et al. 2006).

Analytical models and simulations should generate specific testable predictions that can be checked through empirical observations. This experimental validation can also provide hints for corrections and refinements of the models, thus permitting an iterative approach towards better and more useful models.

Computational methods can be roughly divided into two groups: computational solution techniques; and computational modeling.

• The former group consists mainly of routines for solving ordinary differential equations or partial differential equations, or their difference equation counterparts. The basic idea is to represent the changes of a certain quantity, such as the number of cells or the concentration of a particular molecule, as a function of other quantities. The equations that represent such relationships are studied in different dynamical regimes (oscillatory, chaotic, etc.,) in order to make predictions about the behavior of the system under different initial or boundary conditions. A limitation of the differential equation approach is that often only the average behavior of systems can be modeled.

• The latter group consists of methods for the direct computational representation of systems. An example would be ABM, which aims at describing (and predicting) the evolution of dynamic systems by simulating the behavior of their constituent "agents" (individual parts). In ABM there is no description in terms of averages, such as average rates of production or degradation. Rather, each agent is a software program comprising both data and behavioral rules (processes) that act on this data. Thus, ABM represents dynamic systems in a manner permitting the systems to evolve over time through agent interactions, with a minimum of a-priori assumptions. Macroscopic system behaviors are then observed as emergent properties (emergent behavior).

Nowadays, the term agent is used to indicate entities ranging all the way from simple pieces of software to "conscious" entities with learning capabilities. For example, there are "helper" agents for web retrieval, robotic agents to explore inhospitable environments, agents in an economy, and so forth.

Roughly speaking, an entity is an "agent" if it has some degree of autonomy, that is, if it is distinguishable from its environment by some kind of spatial, temporal, or functional attribute. That is, an agent must be identifiable. Moreover, we further require that agents must have some autonomy of action and that they must be able to engage in tasks in an environment without direct external control.

From simple agents, who interact locally with simple rules of behavior, merely responding befittingly to environmental cues, and not necessarily striving for an overall goal, we observe a synergy which leads to a higher-level whole with much more intricate behavior than the component agents (holism, from holos, a Greek word meaning all, entire, total), e.g. insect colonies, immune responses, financial markets, neural computation. The field of Artificial Life (AL) (Langton 1989) produced a number of models based on "swarms" of simple agent rules capable of producing a higher-level identity, such as the flocking behavior of birds.

Classical mathematical models vs agent-based simulation

A simple example might help to clarify the differences between differential equations models and agent-based models. Let's consider a predator-prey system that, in spite of its many limitations due to oversimplification, provides the perfect example of a system whose behaviour can be easily captured by a mathematical model. Foxes (\(F\)) predate rabbits (\(R\)): the relationships between the two populations can be expressed by means of the Lotka-Volterra system of ordinary differential equations: \[ \begin{matrix} \dot{R}(t) = aR-bFR\\ \dot{F}(t) = cFR-dF \end{matrix} \] The first equation for the rabbits (\(R\)) says that, while they grow at a rate \(a\ ,\) they are killed by the foxes (\(F\)) at a rate that is proportional to the size of the fox population (\(bF\)). The second equation says that the foxes grow proportionally to the food supply (term \(cR\)) and die by aging at a constant rate \(d\ .\)

This mathematical description of the predator-prey system assumes a completely different form when defined in terms of an ABM. First of all, an ABM description would require an explicit representation of the space, either discrete by means of a lattice of points, or continuous by assigning each spatial site a dimension/volume, an area of influence, and a position in a generic n-dimensional Euclidean space. Then, the different agents of the simulation would be defined and located on the space. Let's take the lattice as an example. Let foxes be indicated by F, rabbits be indicated by R, and vacant lattice points be indicated by 0. Only two bits of information are required to describe the four possible states of each lattice point, as follows: 00 (neither an F nor an R); F0 (only an F); 0R (only an R); or FR (both an F and an R). Note that this is not the only possible choice. For instance, one could define a three-state system for each lattice point, i.e., a lattice point is empty, occupied by a fox, or occupied by a rabbit, introducing in this way a sort of exclusion principle between the two species.

After defining the space, the agents inhabiting the space, and the possible states of each spatial site, the last remaining issue is the definition of the rules that describe how the system changes its status, i.e., the dynamics of the system. Coding the rules is the most important step in the definition of an ABM. A possible set of rules that reflects the fox and rabbit relationships described above, for simplicity described here in words, is as follows:

1. if a rabbit is "close" (i.e., at the same lattice point or at an adjacent point in case we are using the exclusion principle) to a fox, then with a certain probability \(p_b\) the rabbit disappears and a new fox occupies the point previously occupied by the rabbit;
2. if a lattice point is empty, then with a certain probability \(p_a\ ,\) a rabbit is born at this point;
3. if a lattice point is occupied by a fox then with a rate \(d\) the fox dies and the lattice point becomes empty (note that the death of rabbits and the birth of foxes are described by rule 1).
4. The last rule describes the random displacements of both species.

Note that the rates \(a, b, c\) and \(d\) in the system of equations above are not equal to the corresponding probability parameters of the ABM (\(p_a\) and \(p_b\)).

Figure 2: Figure A shows a couple of steps of a simple ABM of a Lotka-Volterra predator-pray system. Space is discretized into a 2D lattice. A lattice point is occupied either by a fox or a rabbit. Time passes in discrete steps. The application of the rules determines the fox-rabbit populations. An example of the overall population dynamics is shown in panel (B) that evidences the oscillatory behavior of the fox-rabbit coexistence. Small fluctuations are typical of ABMs and are not exhibited by ODE models whose dynamics are illustrated in panel (C) for comparison.

Panel A of the figure shows two steps of the fox-rabbit micro-simulation with all rules applied in parallel at each time step. In panel B of the same figure, the overall population is plotted versus time. For people familiar with simulations, it should be clear that the spikes in the curves are due to the stochastic nature of the ABM model. In fact, the solution of the equivalent system of differential equations reported in panel C of the same figure does not show such fluctuations. In other words, panel B has much more of the quality of real (observational) data than panel C, which is unnaturally smooth and regular.

In this simple example, the ABM rules reproduce the same oscillatory behavior as the ODE system, hence the descriptive power of the ABM does not enhance the comprehension of the phenomenon under study as compared to the solution of the ODE system. However, ABMs work better in representing situations in which small fluctuations can drive a system to a completely different state. This is pretty common, for example in complex biological systems, where the action of even a single entity (e.g., a virus, or a malignant cell) can affect the whole dynamics. On the contrary, dependencies like these are difficult to describe by ODE systems because they involve the accurate tracking of fast-growing instabilities out of tiny perturbations.

Definition and properties of ABMs

In general, when we build an ABM to simulate a certain phenomenon, we need to identify the actors first (the agents). We then need to consider the processes (rules) governing the interactions among the agents. To accomplish this, it is helpful to consider the following:

• Agents have internal states (attributes, data,...). These internal states can be represented by discrete or continuous variables.

Figure 3: Example of finite state automata.

• Given the choice of an agent's state variable(s), the agent's behaviour can be represented as a state-determined automata (or finite state machine): a state transition occurs whenever the agent interacts with another agent.

• However, more sophisticated ABM applications need to move beyond state-determined automata with the inclusion of random-access memory capabilities. That is, agents can engage with their environments beyond concurrent state-determined interaction by using memory to store descriptions and representations of their environments. They can also have access to shared knowledge among the members of their particular agent society. Such agents are dynamically incoherent in the sense that their next state or action is not solely dependent on the previous state but rather depends also on some (random-access) stable memory that keeps the same value until it is accessed and that does not change with the dynamics of the environment-agent interactions. In this sense, ABMs bridge traditional Artificial Life, Artificial Intelligence, and Game Theory.

• The range of agent interactions also needs to be specified. Possible specifications include:
  • global interaction (every agent interacts with every other agent);
  • local interaction (every agent only interacts with a local neighborhood of other agents);
  • local interaction with some degree of global reach (e.g., small-world networks).

• Agents' behaviors are determined by rules. These rules range from simple first order predicate logic to algorithms comprising thousands of lines of code.

• In many ABM applications, modelers introduce some form of spatial landscape (e.g., lattice, torus) that constrains potential agent interactions. In some cases this spatial landscape is represented as a purely passive platform upon which agents interact, as in the predator-prey model previously described. In other cases, however, the spatial landscape is itself represented as an agent with its own internal states and behavioral rules (e.g., a region of land with naturally growing food sources).

• The system evolves over time. The interactions of the agents take place in a certain order. This order should, in principle, not be sequential since agents behave individually in parallel with each other. In practice however, since computers are sequential in nature, the order needs to be serialized though randomized. Simulation of agents can also be done on parallel machines, in which case the asynchrony is easily and better represented.

• Both time and space can be discrete or continuous. Therefore we have
  • continuous space and continuous time,
  • continuous space and discrete time,
  • discrete space and continuous time,
  • discrete space and discrete time.

And the mathematics?

As indicated above, ABMs are typically represented directly as systems of interacting agents (software programs comprising data and behavioral rules) in order to increase the empirical clarity of the modeling process. However, alternative mathematical representations are possible.

One possibility is the theory of mappings, i.e., Dynamical Systems with discrete time \(t=1,2,3,\ldots\ .\) The macroscopic state \(X(t)\) of the "represented world" is given by the set of microscopic states of the \(n\) agents\[X(t)=(x_i(t))_{i=0,...,n}\ .\] The state transitions for all of the agents' internal states together yield the Dynamical System's transition function\[X(t+1) = F(X(t),\phi(t))\ .\] In other words, the transition function is a combination of all of the agents' rules \((R_j)_{j=0,...,m}\ .\) Therefore \(F = R_{i_1} \circ R_{i_2} \circ ... \) where the order \(i_1, i_2, ...\) is specified by the second argument \(\phi(t)\ .\) A random order \(\phi(t)\) results in a stochastic ABM, and the corresponding mathematical formalism is that of a Markov Chain. In this case one refers to the probability of finding the system in a particular state \(Pr[X(t) = x]\ .\) This probability is built on the micro-states and the transition function \(F\) made up by the rules.

Other researchers attempting to formalize the study of ABMs have used concepts from complex adaptive systems and artificial life (AL), such as entropy and evolution, as well as concepts from Game Theory such as strategic decision-making and Nash equilibria (Rocha 2000).

ABM programming

ABM programming can be done in any language, but Object Oriented Programming (OOP) is the most appropriate language since the concept of an object is similar to the concept of an agent. It is worth mentioning the idea of "frames" introduced by Marvin Minsky (in the early 1970s). The "frames" are representations of super-agents; agents inherit their variable assignments from previously defined frames (Minsky, M. 1987). Frames are often considered to be an early form of OOP. In this view the frames are the classes of OOP.

Today it is not difficult to find toolkits that facilitate ABM. SWARM is one of these. Others include Repast, Netlogo, and Mason. See [1] for an extensive list of pointers to software and toolkits currently being used by ABM researchers.

References

• Ising, E. (1925) "Beitrag zur theorie des ferromagnetismus." Zeitschr. Physik. 31:253-258.
• Wolfram, S. "Cellular Automata and Complexity." Addison Wesley, New York, NY.
• Langton, C.G. (1989) "Artificial life." In: Artificial Life. C. Langton (ed.). Addison-Wesley.
• Levy, H., Levy, M. and Solomon, S. (2000). "Microscopic Simulations of Financial Markets". Academic Press, New York.
• de Oliveira, M.S, de Oliveira, P.M.C. and Stauffer, D. (1999) "Evolution, Money, War, and Computers - Non-Traditional Applications of Computational Statistical Physics". Teubner, Stuttgart-Leipzig.
• Stauffer, D., de Oliveira, S.M., de Oliveira, P.M.C. and Sa Martins,J.S. (2006) "Biology, Sociology, Geology by Computational Physicists". Elsevier, Amsterdam.
• Rocha, Luis M. (2000). "Syntactic autonomy, cellular automata, and RNA editing: or why self-organization needs symbols to evolve and how it might evolve them". In: Closure: Emergent Organizations and Their Dynamics. Chandler J.L.R. and G, Van de Vijver (Eds.) Annals of the New York Academy of Sciences. Vol. 901, pp 207-223.
• Minsky, M. (1987) "The Society of Mind" Simon & Schuster. New York, NY.

Internal references

• Jeff Moehlis, Kresimir Josic, Eric T. Shea-Brown (2006) Periodic orbit. Scholarpedia, 1(7):1358.
• Frank Hoppensteadt (2006) Predator-prey model. Scholarpedia, 1(10):1563.
• Philip Holmes and Eric T. Shea-Brown (2006) Stability. Scholarpedia, 1(10):1838.

Recommended reading

• Norman Ehrentreich. Agent-based Modeling - The Santa Fe Institute Artificial Stock Market Model Revisited. Springer-Verlag Berlin and Heidelberg GmbH & Co. KG. ISBN: 3540738789

• Nigel Gilbert, G. Nigel Gilbert. Agent-Based Models (Quantitative Applications in the Social Sciences Series). SAGE Publications. ISBN-13: 9781412949644

• K. Arai (Editor), H. Deguchi (Editor), H. Matsui (Editor). Agent-Based Modeling Meets Gaming Simulation. Springer. ISBN-10: 4431294260.

• M. Luck, R. Ashri, M. d'Inverno. Agent-Based Software Development (Agent-Oriented Systems). Artech House Publishers. ISBN-10: 1580536050

External links

• Filippo Castiglione's website

• ABM, from Wikipedia, the free encyclopedia
• [www.brookings.edu/topics/agent-based-models.aspx The Brookings Institution, Agent-based Models]
• International Society of Artificial Life
• Swarm Development Group Wiki
• Tools for Agent-Based Modelling
• Individual-Based Models, an annotated list of links by Craig Reynolds
• IMA "Hot Topics" Workshop: Agent Based Modeling and Simulation
• Repast, Agent modeling toolkit
• Guide for Newcomers to Agent-Based Modeling in the Social Sciences
• Agent-Based Computational Economics (ACE)
• Agent-Based Models: Methodology and Philosopy

See also

Cellar Automata, Ising model, Artificial Life, Dynamical Systems, Object Oriented Programming Agent-based Computational Economics

Sponsored by: Eugene M. Izhikevich, Editor-in-Chief of Scholarpedia, the peer-reviewed open-access encyclopedia

Reviewed by: Anonymous

Accepted on: 2006-09-29 18:31:09 GMT