Agent-based model

An agent-based model (ABM) (also sometimes related to the term multi-agent system or multi-agent simulation) is a class of computational models for simulating the actions and interactions of autonomous agents (both individual or collective entities such as organizations or groups) with a view to assessing their effects on the system as a whole. It combines elements of game theory, complex systems, emergence, computational sociology, multi-agent systems, and evolutionary programming. Monte Carlo Methods are used to introduce randomness. ABMs are also called individual-based models.

The models simulate the simultaneous operations and interactions of multiple agents, in an attempt to re-create and predict the appearance of complex phenomena. The process is one of emergence from the lower (micro) level of systems to a higher (macro) level. As such, a key notion is that simple behavioral rules generate complex behavior. This principle, known as K.I.S.S. ("Keep it simple and short") is extensively adopted in the modeling community. Another central tenet is that the whole is greater than the sum of the parts. Individual agents are typically characterized as boundedly rational, presumed to be acting in what they perceive as their own interests, such as reproduction, economic benefit, or social status,^[1] using heuristics or simple decision-making rules. ABM agents may experience "learning", adaptation, and reproduction.^[2]

Most agent-based models are composed of: (1) numerous agents specified at various scales (typically referred to as agent-granularity); (2) decision-making heuristics; (3) learning rules or adaptive processes; (4) an interaction topology; and (5) a non-agent environment.

History

The idea of agent-based modeling was developed as a relatively simple concept in the late 1940s. Since it requires computation-intensive procedures, it did not become widespread until the 1990s.

The history of the agent-based model can be traced back to the Von Neumann machine, a theoretical machine capable of reproduction. The device von Neumann proposed would follow precisely detailed instructions to fashion a copy of itself. The concept was then improved by von Neumann's friend Stanisław Ulam, also a mathematician; Ulam suggested that the machine be built on paper, as a collection of cells on a grid. The idea intrigued von Neumann, who drew it up—creating the first of the devices later termed cellular automata.

Another improvement was introduced by the mathematician John Conway. He constructed the well-known Game of Life. Unlike von Neumann's machine, Conway's Game of Life operated by tremendously simple rules in a virtual world in the form of a 2-dimensional checkerboard.

One of the earliest agent-based models in concept was Thomas Schelling's segregation model, which was discussed in his paper Dynamic Models of Segregation in 1971. Though Schelling originally used coins and graph paper rather than computers, his models embodied the basic concept of agent-based models as autonomous agents interacting in a shared environment with an observed aggregate, emergent outcome.

In the early 1980s, Robert Axelrod hosted a tournament of Prisoner's Dilemma strategies and had them interact in an agent-based manner to determine a winner. Axelrod would go on to develop many other agent-based models in the field of political science that examine phenomena from ethnocentrism to the dissemination of culture (Axelrod 1997).

In the late 1980s, Craig Reynolds' work on flocking models contributed to the development of some of the first biological agent-based models that contained social characteristics. He tried to model the reality of lively biological agents, known as artificial life, a term coined by Christopher Langton.

The first use of the word "agent" and a definition as it is currently used today is hard to track down. One candidate appears to be John Holland and John H. Miller's 1991 paper "Artificial Adaptive Agents in Economic Theory"^[3] which is based on an earlier conference presentation of theirs.

At the same time, during the 1980s, social scientists, mathematicians, operations researchers, and a scattering of people from other disciplines developed Computational and Mathematical Organization Theory (CMOT). This field grew as a special interest group of The Institute of Management Sciences (TIMS) and its sister society, the Operations Research Society of America (ORSA). Through the mid-1990s, the field focused on such issues as designing effective teams, understanding the communication required for organizational effectiveness, and the behavior of social networks. With the appearance of StarLogo in 1990, SWARM and NetLogo in the mid-1990s and RePast and AnyLogic in 2000, as well as some custom-designed code, CMOT—later renamed Computational Analysis of Social and Organizational Systems (CASOS) — incorporated more and more agent-based modeling. Samuelson (2000) is a good brief overview of the early history, and Samuelson (2005) and Samuelson and Macal (2006) trace the more recent developments. Bonabeau (2002) is a good survey of the potential of agent-based modeling as of the time that its modelling software became widely available.

Kathleen M. Carley developed an early ABM, Construct , to explore the co-evolution of social networks and culture.

Joshua M. Epstein and Robert Axtell developed a large-scale ABM, the Sugarscape, to simulate and explore the role of social phenomenon such as seasonal migrations, pollution, sexual reproduction, combat, and transmission of disease and even culture.

Nigel Gilbert published the first textbook on Social Simulation: Simulation for the social scientist (1999) and established its most relevant journal: the Journal of Artificial Societies and Social Simulation.

In the late 1990s, the merger of TIMS and ORSA to form INFORMS, and the move by INFORMS from two meetings each year to one, helped to spur the CMOT group to form a separate society, the North American Association for Computational Social and Organizational Sciences (NAACSOS). Kathleen Carley, of Carnegie Mellon University, was a major contributor, especially to models of social networks, obtaining National Science Foundation funding for the annual conference and serving as the first President of NAACSOS. She was succeeded by David Sallach of the University of Chicago and Argonne National Laboratory, and then by Michael Prietula of Emory University. At about the same time NAACSOS began, the European Social Simulation Association (ESSA) and the Pacific Asian Association for Agent-Based Approach in Social Systems Science (PAAA), counterparts of NAACSOS, were organized. Nowadays, these three organizations collaborate internationally. The First World Congress on Social Simulation was held under their joint sponsorship in Kyoto, Japan, in August 2006. The Second World Congress was held in the northern Virginia suburbs of Washington, D.C., in July 2008, with George Mason University taking the lead role in local arrangements.

More recently, Ron Sun developed methods for basing agent-based simulation on models of human cognition, known as cognitive social simulation (see Sun 2006). Bill McKelvey, Suzanne Lohmann, Dario Nardi, Dwight Read and others at UCLA have also made significant contributions in organizational behavior and decision-making. Since 2001, UCLA has arranged a conference at Lake Arrowhead, California, that has become another major gathering point for practitioners in this field.

Theory

Most computational modeling research describes systems in equilibrium or as moving between equilibria. Agent-based modeling, however, using simple rules, can result in different sorts of complex and interesting behavior.

The three ideas central to agent-based models are agents as objects, emergence, and complexity.

Agent-based models consist of dynamically interacting rule-based agents. The systems within which they interact can create real-world-like complexity. These agents are:

• Intelligent and purposeful.
• Situated in space and time. They reside in networks and in lattice-like neighborhoods. The location of the agents and their responsive and purposeful behavior are encoded in algorithmic form in computer programs. The modeling process is best described as inductive. The modeler makes those assumptions thought most relevant to the situation at hand and then watches phenomena emerge from the agents' interactions. Sometimes that result is an equilibrium. Sometimes it is an emergent pattern. Sometimes, however, it is an unintelligible mangle.

In some ways, agent-based models complement traditional analytic methods. Where analytic methods enable humans to characterize the equilibria of a system, agent-based models allow the possibility of generating those equilibria. This generative contribution may be the most mainstream of the potential benefits of agent-based modeling. Agent-based models can explain the emergence of higher-order patterns—network structures of terrorist organizations and the Internet, power-law distributions in the sizes of traffic jams, wars, and stock-market crashes, and social segregation that persists despite populations of tolerant people. Agent-based models also can be used to identify lever points, defined as moments in time in which interventions have extreme consequences, and to distinguish among types of path dependency.

Rather than focusing on stable states, the models consider a system's robustness—the ways that complex systems adapt to internal and external pressures so as to maintain their functionalities. The task of harnessing that complexity requires consideration of the agents themselves—their diversity, connectedness, and level of interactions.

Applications

Agent-based models have been used since the mid-1990s to solve a variety of business and technology problems. Examples of applications include supply chain optimization and logistics, modeling of consumer behavior, including word of mouth, social network effects, distributed computing, workforce management, and portfolio management. They have also been used to analyze traffic congestion.^[4] In these and other applications, the system of interest is simulated by capturing the behavior of individual agents and their interconnections. Agent-based modeling tools can be used to test how changes in individual behaviors will affect the system's emerging overall behavior.

Other models have analyzed the spread of epidemics, the threat of biowarfare, biological applications including population dynamics^[5] , the growth and decline of ancient civilizations, evolution of ethnocentric behavior,^[6] forced displacement/migration,^[7] language choice dynamics,^[8] and biomedical applications including inflammation and the human immune system.^[9] Agent-based models have also been used for developing decision support systems such as for breast cancer.^[10]

Recently, agent based modelling and simulation has been applied to various domains such as studying the impact of publication venues by researchers in the computer science domain (journals versus conferences).^[11] In addition, ABMS has been used to simulate information delivery in ambient assisted environments.^[12] In the domain of peer-to-Peer, ad-hoc and other self-organizing and complex networks, the usefulness of agent based modeling and simulation has been shown.^[13] The use of Computer Science based Formal Specification framework coupled with Wireless sensor networks and an Agent-based simulation has recently been demonstrated in.^[14]

Agent based evolutionary search or algorithm is a new research topic for solving complex optimization problems. Further details on the topic can be found in R. Sarker and T. Ray (2010) Agent based Evolutionary Approach: An Introduction, Agent Based Evolutionary Search, Springer series in Evolutionary Learning and Optimization, Springer, pp. 1–12.

Economics

Graphic user interface for an agent-based modeling tool.

Prior to and in the wake of the financial crisis interest has grown in ABMs as possible tools for economic analysis.^[15] ABMs do not assume the economy can achieve equilibrium and "representative agents" are replaced by agents with diverse, dynamic, and interdependent behavior including herding. ABMs take a "bottom-up" approach and can generate extremely complex and volatile simulated economies. ABMs can represent unstable systems with crashes and booms that develop out of non-linear (disproportionate) responses to proportionally small changes.^[16] A July 2010 article in The Economist looked at ABMs as alternatives to the DGSE models.^[16] The journal Nature also encouraged agent-based modeling with an editorial that suggested ABMs can do a better job of representing financial markets and other economic complexities than standard models^[17] along with an essay by J. Doyne Farmer and Duncan Foley that argued ABMs could fulfill both the desires of Keynes to represent a complex economy and of Robert Lucas to construct models based on microfoundations.^[18] Farmer and Foley pointed to progress that has been made using ABMs to model parts of an economy, but argued for the creation of a very large model that incorporates low level models.^[19]

Agent-directed simulation

The agent-directed simulation (ADS) [2] metaphor distinguishes between two categories, namely "Systems for Agents" and "Agents for Systems." Systems for Agents (sometimes referred to as agents systems) are systems implementing agents for the use in engineering, human and social dynamics, military applications, and others. Agents for Systems are divided in two subcategories. Agent-supported systems deal with the use of agents as a support facility to enable computer assistance in problem solving or enhancing cognitive capabilities. Agent-based systems focus on the use of agents for the generation of model behavior in a system evaluation (system studies and analyses).

Hardware

The Software described above is designed for serial von-Neumann computer architectures. This limits the speed and scalability of these systems. A recent development is the use of data-parallel algorithms on Graphics Processing Units GPUs for ABM simulation [3], [4] and [5]. The extreme memory bandwidth combined with the sheer number crunching power of multi-processor GPUs has enabled simulation of millions of agents at tens of frames per second.

Verification and validation of agent-based models

Verification and validation (V&V) of simulation models is extremely important.^[20][21] Verification involves debugging the model to ensure it works correctly; whereas Validation ensures that you have built the right model. Verification and validation in the social sciences domain can be seen in.^[22] In Computational Economics, validation can be examined in.^[23] In,^[24] the author proposes face validation, sensitivity analysis, calibration and statistical validation. Discrete-Event Simulation Framework approach for the validation of Agent-Based systems has been proposed in.^[25] A comprehensive resource on empirical validation of agent-based models is ^[26]

A formal approach for V&V of all agent-based models is based on building a VOMAS (Virtual Overlay Multi-Agent System),^[27] a software engineering based approach, where a virtual overlay Multi-agent system is developed alongside the agent-based model. The agents in the Multi-Agent System are able to gather data by generation of logs as well as provide run-time validation and verification support by watch agents and also agents to check any violation of invariants at run-time. These are set by the Simulation Specialist with help from the SME (Subject Matter Expert). An example of using VOMAS for Verification and Validation of a Forest Fire simulation model is given in ^[28]

VOMAS provides a formal way of Validation and Verification. If you want to build a VOMAS, you need to start designing VOMAS agents along with the agents in the actual simulation preferably from the start. So, in essence, by the time your simulation model is complete, you essentially have one model which contains two models:

1. An Agent Based Model of the intended system
2. An Agent Based Model of the VOMAS

Unlike all previous work on Verification and Validation, VOMAS agents ensure that the simulations are validated in-simulation i.e. even during execution. In case of any exceptional situations, which are programmed on the directive of the Simulation Specialist (SS), the VOMAS agents can report them. In addition, the VOMAS agents can be used to log key events for the sake of debugging and subsequent analysis of simulations. In other words, VOMAS allows for a flexible use of any given technique for the sake of Verification and Validation of an Agent-based Model in any domain.

See also

Agent-Based Computational Economics Agent-based model in biology agent-based social simulation (ABSS) ACEGES artificial life artificial society boids Comparison of agent-based modeling software complex system computational sociology Conway's Game of Life dynamic network analysis emergence

evolutionary algorithm flocking Generative sciences human fit Kinetic exchange models of markets Multi-agent system simulated reality social complexity social simulation software agent Swarming behaviour Swarm Development Group Web-based simulation Janus (multi-agent and holonic platform)

References

In-line

1. ^ Agent-Based Models of Industrial Ecosystems. Rutgers University, October 6, 2003.
2. ^ Agent-based modeling: Methods and techniques for simulating human systems. Proceedings of the National Academy of Sciences. May 14, 2002.
3. ^ Holland, J.H.; Miller, J.H.; (1991). "Artificial Adaptive Agents in Economic Theory". American Economic Review 81 (2): 365–71. http://zia.hss.cmu.edu/miller/papers/aaa.pdf. 
4. ^ Application of Agent Technology to Traffic Simulation. United States Department of Transportation, May 15, 2007.
5. ^ Caplat, Paul; Anand, Madhur, Bauch, Chris (10 March 2008). "Symmetric competition causes population oscillations in an individual-based model of forest dynamics". Ecological Modelling 211 (3–4): 491–500. doi:10.1016/j.ecolmodel.2007.10.002. 
6. ^ Lima, Francisco W. S., Hadzibeganovic, Tarik, and Stauffer, Dietrich. 2009. Evolution of ethnocentrism on undirected and directed Barabási–Albert networks. Physica A, 388(24), 4999–5004.
7. ^ The Chaos of Forced Migration: A Modeling Means to an Humanitarian End, Scott Edwards, 2010
8. ^ Hadzibeganovic, Tarik, Stauffer, Dietrich, and Schulze, Christian. 2009. Agent-based computer simulations of language choice dynamics. Annals of the New York Academy of Sciences, 1167, 221–229.
9. ^ Tutorial on agent-based modeling and simulation part 2: how to model with agents. Association for Computing Machinery, Winter Simulation Conference, 2006.
10. ^ Amnah Siddiqah, Muaz Niazi, Farah Mustafa, Habib Bokhari, Amir Hussain, Noreen Akram, Shabnum Shaheen, Fouzia Ahmed &Sarah Iqbal, "A new hybrid agent-based modeling decision support system for breast cancer research", IEEE ICICT, IBA, Karachi, August 15–16, 2009.Breast Cancer DSS
11. ^ Niazi, M., Baig, A. R., Hussain, A., and Bhatti, S. 2008. Simulation of the research process. In Proceedings of the 40th Conference on Winter Simulation (Miami, Florida, December 7 – 10, 2008). S. Mason, R. Hill, L. Mönch, and O. Rose, Eds. Winter Simulation Conference. 1326-1334. Simulation Of the Research Process
12. ^ Niazi, Muaz A. "Self-Organized Customized Content Delivery Architecture for Ambient Assisted Environments." UPGRADE '08: Proceedings of the third international workshop on Use of P2P, grid and agents for the development of content networks (2008): 45-54.Paper
13. ^ Muaz Niazi and Amir Hussain, Agent based Tools for Modeling and Simulation of Self-Organization in Peer-to-Peer, Ad-Hoc and other Complex Networks, Feature Issue, IEEE Communications Magazine, Vol.47 No.3, March 2009, pp 163 - 173.Paper
14. ^ Muaz Niazi, Amir Hussain (2011). A Novel Agent-Based Simulation Framework for Sensing in Complex Adaptive Environments. IEEE Sensors Journal, Vol.11 No. 2, 404–412. Paper
15. ^ • Scott E. Page, 2008. "agent-based models," The New Palgrave Dictionary of Economics, 2nd Edition. Abstract.
       • Leigh Tesfatsion and Kenneth Judd, ed., 2006. Handbook of Computational Economics, v. 2. Description & and chapter-preview links.
16. ^ ^{a b} "Agents of change". The Economist. 22 July 2010. http://www.economist.com/node/16636121. Retrieved 16 February 2011. 
17. ^ "A model approach" (Editorial). Nature 460 (7256): 667. 6 August 2009. doi:10.1038/460667a. http://www.nature.com/nature/journal/v460/n7256/full/460667a.html. 
18. ^ Farmer & Foley 2009, p. 685.
19. ^ Farmer & Foley 2009, p. 686.
20. ^ Sargent, R.G., "Verification, validation and accreditation of simulation models," Simulation Conference Proceedings, 2000. Winter , vol.1, no., pp.50-59 vol.1, 2000 Link
21. ^ Galán, J.M., Izquierdo, L.R., Izquierdo, S.S., Santos, J.I., del Olmo, R., López-Paredes, A. and Edmonds, B.(2009) "Errors and Artefacts in Agent-Based Modelling," Journal of Artificial Societies and Social Simulation , vol.12, no.1, [1]
22. ^ Validation and Verification of Agent-Based Models in the Social Sciences, Lecture Notes in Computer Science, Volume 5466/2009, Epistemological Aspects of Computer Simulation in the Social Sciences 130-140 SpringerLink
23. ^ Validating and Calibrating Agent-Based Models: A Case Study, Computational Economics, Volume 30 , Issue 3 (October 2007), 245–264, 2007 DOI
24. ^ Franziska Klügl, A validation methodology for agent-based simulations, Proceedings of the 2008 ACM symposium on Applied computing table of contents, Fortaleza, Ceara, Brazil, pages 39–43 DOI
25. ^ Fortino, G., A. Garro, and W. Russo. "A Discrete-Event Simulation Framework for the Validation of Agent-Based and Multi-Agent Systems." 2005. Paper
26. ^ Verification and Validation of Agent-Based Computational Models Link
27. ^ Muaz Niazi, Amir Hussain and Mario Kolberg , Verification and Validation of Agent-Based Simulations using the VOMAS approach, Proceedings of the Third Workshop on Multi-Agent Systems and Simulation ’09 (MASS '09), as part of MALLOW 09, Sep 7–11, 2009, Torino, Italy Paper
28. ^ Muaz Niazi, Qasim Siddique, Amir Hussain and Mario Kolberg, Verification & Validation Of An Agent-Based Forest Fire Simulation Model, Proceedings of the Agent Directed Simulation Symposium 2010, as part of the ACM SCS Spring Simulation Multiconference, pp142-149, Orlando, FL, April 11–15, 2010 Paper

General

• Barnes, D.J.; Chu, D. (2010). Introduction to Modelling for Biosciences (chapter 2 & 3). Springer Verlag. ISBN 978-1-84996-325-1. http://www.cs.kent.ac.uk/projects/imb/ 

• Axelrod, Robert (1997). The Complexity of Cooperation: Agent-Based Models of Competition and Collaboration. Princeton: Princeton University Press. ISBN 978-0-691-01567-5 

• Bonabeau, Eric, Agent-based modeling: methods and techniques for simulating human systems. Proc. National Academy of Sciences 99(3): 7280–7287, 2002.

• Carley, Kathleen M., Smart Agents and Organizations of the Future. In Handbook of New Media, edited by Leah Lievrouw & Sonia Livingstone, Ch. 12 pp. 206–220, Thousand Oaks, CA, Sage. [6]

• Epstein, Joshua M. and Robert Axtell, Growing Artificial Societies: Social Science From the Bottom Up. MIT Press/Brookings Institution, 1996.[7]

• Farmer, J. Doyne; Foley, Duncan (6 August 2009). "Nature". Nature 460 (7256): 685–686. doi:10.1038/460685a. PMID 19661896. 

• Gilbert, Nigel, and Klaus Troitzsch, Simulation for the Social Scientist, Open University Press, 1999; second edition, 2005.

• Grimm, Volker, and Steven F. Railsback, Individual-based Modeling and Ecology, Princeton University Press, 2005.

• Holland, John H., "Genetic Algorithms," Scientific American, 267:66–72, 1992.

• Holland, John H., Hidden Order: How Adaptation Builds Complexity, Addison-Wesley:Reading, Mass., 1995.

• Miller, John H. and Page, Scott E., Complex Adaptive Systems: An Introduction to Computational Models of Social Life, Princeton University Press:Princeton, NJ, 2007.

• V.K.Murthy and E.V.Krishnamurthy (2009)," Multiset of Agents in a Network for Simulation of Complex Systems", in "Recent advances in Nonlinear Dynamics and synchronization, (NDS-1) – Theory and applications, Springer Verlag, New York,2009. Eds. K.Kyamakya et al.

• O'Sullivan,D. and Haklay, M., Agent-based models and individualism: Is the world agent-based? Environment and Planning A, 32:1409–25, 2000.

• Naldi G., Pareschi L., Toscani G., "Mathematical modeling of collective behavior in socio-economic and life sciences", Birkhauser, 2010. http://www.springer.com/birkhauser/mathematics/book/978-0-8176-4945-6

• Preis, Tobias et al., "Multi-agent-based Order Book Model of financial markets", Europhysics Letters 75:510-516, 2006. http://dx.doi.org/10.1209/epl/i2006-10139-0

• Rudomin, B. Hernandez, E. Millan, Fragment shaders for agent animation using finite state machines, In Simulation Modelling Practice and Theory Journal, Volume 13, Issue 8 , Programmable Graphics Hardware November 2005, Pages 741-751 Elsevier,

• Salamon, Tomas (2011). Design of Agent-Based Models : Developing Computer Simulations for a Better Understanding of Social Processes. Bruckner Publishing. ISBN 978-80-904661-1-1. http://www.designofagentbasedmodels.info/ 

• Sallach, David, and Charles Macal, The simulation of social agents: an introduction, Special Issue of Social Science Computer Review 19(3):245–248, 2001.

• Samuelson, Douglas A., “Designing Organizations,” OR/MS Today, December 2000.

• Samuelson, Douglas A., “Agents of Change,” OR/MS Today, February 2005.

• Samuelson, Douglas A. and Charles M. Macal, “Agent-Based Modeling Comes of Age,” OR/MS Today, August 2006.

• Shoham, Yoav, and Kevin Leyton-Brown, "Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations". Cambridge University Press, 2009.

• Sun, Ron, Cognition and Multi-Agent Interaction: From Cognitive Modeling to Social Simulation. Cambridge University Press, 2006. http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521839645

External links

Articles/General Information

• From System Dynamics and Discrete Event to Practical Agent-Based Modeling: Reasons, Techniques, Tools Compares the three major methods in simulation modeling
• Agent-based models of social networks, java applets.
• On-Line Guide for Newcomers to Agent-Based Modeling in the Social Sciences
• Introduction to Agent-based Modeling and Simulation. Argonne National Laboratory, November 29, 2006.
• Agent-based models in Ecology - Using computer models as theoretical tools to analyze complex ecological systems
• Open Agent-Based Modeling Consortium's Agent Based Modeling FAQ
• Multiagent Information Systems - Article on the convergence of SOA, BPM and Multi-Agent Technology in the domain of the Enterprise Information Systems. Jose Manuel Gomez Alvarez, Artificial Intelligence, Technical University of Madrid - 2006
• Artificial Life Framework
• Article providing methodology for moving real world human behaviors into a simulation model where agent behaviors are represented
• Agent-based Modeling Resources, an information hub for modelers, methods, and philosophy for agent-based modeling

Simulation model

• Multi-agent Meeting Scheduling System Model by Qasim Siddique