Encyclopedia of Complexity and Systems Science

Living Edition
| Editors: Robert A. Meyers

Agent-Based Modeling, Mathematical Formalism for

  • Reinhard LaubenbacherEmail author
  • Abdul S. Jarrah
  • Henning S. Mortveit
  • S. S. Ravi
Living reference work entry
DOI: https://doi.org/10.1007/978-3-642-27737-5_10-5
  • 611 Downloads

Definition of the Subject

Agent-based simulations are generative or computational approaches used for analyzing “complex systems.” What is a “system?” Examples of systems include a collection of molecules in a container, the population in an urban area, and the brokers in a stock market. The entities or agents in these three systems would be molecules, individuals, and stock brokers, respectively. The agents in such systems interact in the sense that molecules collide, individuals come into contact with other individuals, and brokers trade shares. Such systems, often called multiagent systems, are not necessarily complex. The label “complex” is typically attached to a system if the number of agents is large, if the agent interactions are involved, or if there is a large degree of heterogeneity in agent character or their interactions.

This is of course not an attempt to define a complex system. Currently, there is no generally agreed upon definition of complex systems. It is not the...

Keywords

Cellular Automaton Turing Machine Cellular Automaton Dependency Graph Boolean Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in to check access.

Bibliography

Primary Literature

  1. Bagrodia RL (1998) Parallel languages for discrete-event simulation models. IEEE Comput Sci Eng 5(2):27–38CrossRefGoogle Scholar
  2. Barrett CL, Reidys CM (1999) Elements of a theory of simulation I: sequential CA over random graphs. Appl Math Comput 98:241–259CrossRefzbMATHMathSciNetGoogle Scholar
  3. Barrett CL, Mortveit HS, Reidys CM (2000) Elements of a theory of simulation II: sequential dynamical systems. Appl Math Comput 107(2–3):121–136CrossRefzbMATHMathSciNetGoogle Scholar
  4. Barrett CL, Hunt III HB, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Tosic P (2001) Garden of eden and fixed point configurations in sequential dynamical systems. In: Proceedings of international conference on combinatorics, computation and geometry DM-CCG’. Paris, France, pp 95–110Google Scholar
  5. Barrett CL, Mortveit HS, Reidys CM (2001b) Elements of a theory of simulation III: equivalence of SDS. Appl Math Comput 122:325–340CrossRefzbMATHMathSciNetGoogle Scholar
  6. Barrett CL, Marathe MV, Smith JP, Ravi SS (2002) A mobility and traffic generation framework for modeling and simulating ad hoc communication networks. In: SAC’02. ACM, Madrid, pp 122–126Google Scholar
  7. Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2003a) On some special classes of sequential dynamical systems. Ann Comb 7(4):381–408CrossRefzbMATHMathSciNetGoogle Scholar
  8. Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2003b) Reachability problems for sequential dynamical systems with threshold functions. Theor Comput Sci 295(1–3):41–64CrossRefzbMATHMathSciNetGoogle Scholar
  9. Barrett CL, Mortveit HS, Reidys CM (2003c) Elements of a theory of computer simulation. IV. Sequential dynamical systems: fixed points, invertibility and equivalence. Appl Math Comput 134(1):153–171CrossRefzbMATHMathSciNetGoogle Scholar
  10. Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2006) Complexity of reachability problems for finite discrete sequential dynamical systems. J Comput Syst Sci 72:1317–1345CrossRefzbMATHMathSciNetGoogle Scholar
  11. Barrett CL, Hunt III HB, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Thakur M (2007) Computational aspects of analyzing social network dynamics. In: Proceedings of international joint conference on artificial intelligence IJCAI. Paris, France, pp 2268–2273Google Scholar
  12. Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Thakur M (2007b) Predecessor existence problems for finite discrete dynamical systems. Theor Comput Sci 1–2:3–37CrossRefMathSciNetGoogle Scholar
  13. Bartlett R, Garzon M (1993) Monomial cellular automata. Complex Syst 7(5):367–388zbMATHMathSciNetGoogle Scholar
  14. Bernaschi M, Castiglione F (2002) Selection of escape mutants from immune recognition during hiv infection. Immunol Cell Biol 80:307–313CrossRefGoogle Scholar
  15. Bernaschi M, Succi S, Castiglione F (2000) Large-scale cellular automata simulations of the immune system response. Phys Rev E 61:1851–1854ADSCrossRefGoogle Scholar
  16. Booch G, Rumbaugh J, Jacobson I (2005) Unified modeling language user guide, 2nd edn. Addison-Wesley, ReadingGoogle Scholar
  17. Brand D, Zafiropulo P (1983) On communicating finite-state machines. J ACM 30:323–342CrossRefzbMATHMathSciNetGoogle Scholar
  18. Cartier P, Foata D (1969) Problemes combinatoires de commutation et reárrangements, vol 85, Lecture Notes in Mathematics. Springer, BerlinzbMATHGoogle Scholar
  19. Castiglione F, Agur Z (2003) Analyzing hypersensitivity to chemotherapy in a cellular automata model of the immune system. In: Preziosi L (ed) Cancer modeling and simulation. Chapman and Hall/CRC, LondonGoogle Scholar
  20. Castiglione F, Bernaschi M, Succi S (1997) Simulating the immune response on a distributed parallel computer. Int J Mod Phys C 8:527–545. doi:10.1142/S0129183197000424ADSCrossRefGoogle Scholar
  21. Castiglione F, Duca K, Jarrah A, Laubenbacher R, Hochberg D, Thorley-Lawson D (2007) Simulating Epstein-Barr virus infection with C-ImmSim. Bioinformatics 23(11):1371–1377CrossRefGoogle Scholar
  22. Celada F, Seiden P (1992a) A computer model of cellular interactions in the immune system. Immunol Today 13(2):56–62CrossRefGoogle Scholar
  23. Celada F, Seiden P (1992b) A model for simulating cognate recognition and response in the immune system. J Theor Biol 158:235–270Google Scholar
  24. Celada F, Seiden P (1996) Affinity maturation and hypermutation in a simulation of the humoral immune response. Eur J Immunol 26(6):1350–1358CrossRefGoogle Scholar
  25. Chaudhuri PP (1997) Additive cellular automata. Theory and applications, vol 1. IEEE Computer Society Press, Washington, DCGoogle Scholar
  26. Colón-Reyes O, Laubenbacher R, Pareigis B (2004) Boolean monomial dynamical systems. Ann Comb 8:425–439CrossRefzbMATHMathSciNetGoogle Scholar
  27. Colón-Reyes O, Jarrah A, Laubenbacher R, Sturmfels B (2006) Monomial dynamical systems over finite fields. Complex Syst 16(4):333–342Google Scholar
  28. Dawson D (1974) Synchronous and asynchronous reversible Markov systems. Canad Math Bull 17(5):633–649CrossRefMathSciNetGoogle Scholar
  29. Ebeling W, Schweitzer F (2001) Swarms of particle agents with harmonic interactions. Theor Biosci 120–3(4):207–224CrossRefGoogle Scholar
  30. Elspas B (1959) The theory of autonomous linear sequential networks. IRE Trans Circuit Theor 1:45–60CrossRefGoogle Scholar
  31. Farmer J, Packard N, Perelson A (1986) The immune system, adaptation, and machine learning. Phys D 2(1–3):187–204CrossRefMathSciNetGoogle Scholar
  32. Frish U, Hasslacher B, Pomeau Y (1986) Lattice-gas automata for the Navier-Stokes equations. Phys Rev Lett 56:1505–1508ADSCrossRefGoogle Scholar
  33. Fukś H (2004) Probabilistic cellular automata with conserved quantities. Nonlinearity 17:159–173ADSCrossRefzbMATHMathSciNetGoogle Scholar
  34. Garcia LD, Jarrah AS, Laubenbacher R (2006) Sequential dynamical systems over words. Appl Math Comput 174(1):500–510CrossRefzbMATHMathSciNetGoogle Scholar
  35. Gardner M (1970) The fantastic combinations of John Conway’s new solitaire game “life”. Sci Am 223:120–123CrossRefGoogle Scholar
  36. Gouda M, Chang C (1986) Proving liveness for networks of communicating finite-state machines. ACM Trans Program Lang Syst 8:154–182CrossRefzbMATHGoogle Scholar
  37. Guo Y, Gong W, Towsley D (2000) Time-stepped hybrid simulation (TSHS) for large scale networks. In: INFOCOM 2000. Proceedings of nineteenth annual joint conference of the IEEE computer and communications societies, vol 2. IEEE, Washington, DC, pp 441–450Google Scholar
  38. Gupta A, Katiyar V (2005) Analyses of shock waves and jams in traffic flow. J Phys A 38:4069–4083ADSCrossRefzbMATHMathSciNetGoogle Scholar
  39. Hansson AÅ, Mortveit HS, Reidys CM (2005) On asynchronous cellular automata. Adv Complex Syst 8(4):521–538CrossRefzbMATHMathSciNetGoogle Scholar
  40. Hedlund G (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320–375CrossRefzbMATHMathSciNetGoogle Scholar
  41. Hernández-Toledo A (2005) Linear finite dynamical systems. Commun Algebra 33(9):2977–2989CrossRefzbMATHGoogle Scholar
  42. Hopcroft JE, Motwani R, Ullman JD (2000) Automata theory, languages and computation. Addison Wesley, ReadingGoogle Scholar
  43. Hopfield J (1982) Neural networks and physical systems with emergent collective computational properties. Proc Natl Acad Sci U S A 79:2554–2588ADSCrossRefMathSciNetGoogle Scholar
  44. Ilachinsky A (2001) Cellular automata: a discrete universe. World Scientific, SingaporeGoogle Scholar
  45. Jarrah A, Laubenbacher R, Stillman M, Vera-Licona P (2007) An efficient algorithm for the phase space structure of linear dynamical systems over finite fields (submitted)Google Scholar
  46. Jefferson DR (1985) Virtual time. ACM Trans Program Lang Syst 7(3):404–425CrossRefMathSciNetGoogle Scholar
  47. Kari J (2005) Theory of cellular automata: a survey. Theory Comput Sci 334:3–33CrossRefzbMATHMathSciNetGoogle Scholar
  48. Keyfitz BL (2004) Hold that light! Modeling of traffic flow by differential equations. Stud Math Libr 26:127–153MathSciNetGoogle Scholar
  49. Kozen DC (1997) Automata and computability. Springer, New YorkCrossRefzbMATHGoogle Scholar
  50. Laubenbacher R, Pareigis B (2003) Decomposition and simulation of sequential dynamical systems. Adv Appl Math 30:655–678CrossRefzbMATHMathSciNetGoogle Scholar
  51. Lidl R, Niederreiter H (1997) Finite fields. Cambridge University Press, CambridgeGoogle Scholar
  52. Liggett TM (2005) Interacting particle systems. Classics in mathematics. Springer, Berlin, Reprint of the 1985 originalGoogle Scholar
  53. Lind DA (1984) Applications of ergodic theory and sofic systems to cellular automata. Phys D 10D:36–44ADSCrossRefMathSciNetGoogle Scholar
  54. Lindgren K, Moore C, Nordahl M (1998) Complexity of two-dimensional patterns. J Stat Phys 91(5–6):909–951CrossRefzbMATHMathSciNetGoogle Scholar
  55. Mac Lane S (1998) Category theory for the working mathematician, 2nd edn. Springer, New York, No 5. in GTMGoogle Scholar
  56. Macy MW, Kitts JA, Flache A (2003) Polarization in dynamic networks: a Hopfield model of emergent structure. In: Dynamic social network modeling and analysis. The National Academies Press, Washington, DC, pp 162–173Google Scholar
  57. Martin O, Odlyzko A, Wolfram S (1984) Algebraic properties of cellular automata. Commun Math Phys 93:219–258ADSCrossRefzbMATHMathSciNetGoogle Scholar
  58. Milligan D, Wilson M (1993) The behavior of affine Boolean sequential networks. Connect Sci 5(2):153–167CrossRefGoogle Scholar
  59. Minar N, Burkhart R, Langton C, Manor A (1996) The swarm simulation system: a toolkit for building multi-agent simulations. Santa Fe Institute preprint series. http://www.santafe.edu/research/publications/wpabstract/199606042. Accessed 11 Aug 2008
  60. Misra J (1986) Distributed discrete-event simulation. ACM Comput Surv 18(1):39–65CrossRefGoogle Scholar
  61. Moncion T, Hutzler G, Amar P (2006) Verification of biochemical agent-based models using petri nets. In: Robert T (ed) International symposium on agent based modeling and simulation, ABModSim’06. Austrian Society for Cybernetics Studies, pp 695–700. http://www.ibisc.univ-evry.fr/pub/basilic/OUT/Publications/2006/MHA06
  62. Morpurgo D, Serentha R, Seiden P, Celada F (1995) Modelling thymic functions in a cellular automaton. Int Immunol 7:505–516CrossRefGoogle Scholar
  63. Mortveit HS, Reidys CM (2001) Discrete, sequential dynamical systems. Discret Math 226:281–295CrossRefzbMATHMathSciNetGoogle Scholar
  64. Mortveit HS, Reidys CM (2004) Reduction of discrete dynamical systems over graphs. Adv Complex Syst 7(1):1–20CrossRefzbMATHMathSciNetGoogle Scholar
  65. Nagel K, Schreckenberg M (1992) A cellular automaton model for freeway traffic. J Phys I 2:2221–2229Google Scholar
  66. Nagel K, Wagner P (2006) Traffic flow: approaches to modelling and control. Wiley, Hoboken, NJGoogle Scholar
  67. Nagel K, Schreckenberg M, Schadschneider A, Ito N (1995) Discrete stochastic models for traffic flow. Phys Rev E 51:2939–2949ADSCrossRefGoogle Scholar
  68. Nagel K, Rickert M, Barrett CL (1997) Large-scale traffic simulation, vol 1215, Lecture notes in computer science. Springer, Berlin, pp 380–402CrossRefGoogle Scholar
  69. Nance RE (1993) A history of discrete event simulation programming languages. ACM SIGPLAN Not 28:149–175CrossRefGoogle Scholar
  70. North MJ, Collier NT, Vos JR (2006) Experiences creating three implementations of the repast agent modeling toolkit. ACM Trans Model Comput Simul 16:1–25CrossRefGoogle Scholar
  71. Orponen P (1994) Computational complexity of neural networks: a survey. Nord J Comput 1:94–110MathSciNetGoogle Scholar
  72. Orponen P (1996) The computational power of discrete hopfield networks with hidden units. Neural Comput 8:403–415CrossRefGoogle Scholar
  73. Park JK, Steiglitz K, Thruston WP (1986) Soliton-like behavior in automata. Phys D 19D:423–432ADSCrossRefGoogle Scholar
  74. Reidys C (1998) Acyclic orientations of random graphs. Adv Appl Math 21:181–192CrossRefzbMATHMathSciNetGoogle Scholar
  75. Reidys CM (2001) On acyclic orientations and sequential dynamical systems. Adv Appl Math 27:790–804CrossRefzbMATHMathSciNetGoogle Scholar
  76. Reidys CM (2005) On certain morphisms of sequential dynamical systems. Discret Math 296(2–3):245–257CrossRefzbMATHMathSciNetGoogle Scholar
  77. Reidys CM (2006) Sequential dynamical systems over words. Ann Comb 10(4):481–498CrossRefzbMATHMathSciNetGoogle Scholar
  78. Rickert M, Nagel K, Schreckenberg M, Latour A (1996) Two lane traffic simulations using cellular automata. Phys A 231:534–550CrossRefGoogle Scholar
  79. Rothman DH (1988) Cellular-automaton fluids: a model for flow in porous media. Geophysics 53:509–518ADSCrossRefGoogle Scholar
  80. Russell S, Norwig P (2003) Artificial intelligence: a modern approach. Prentice-Hall, Upper Saddle RiverGoogle Scholar
  81. Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. BioSystems 51:123–143CrossRefGoogle Scholar
  82. Shmulevich I, Dougherty ER, Kim S, Zhang W (2002a) Probabilistic boolean networks: a rule-based uncertainty model for gene regulatory networks. Bioinformatics 18(2):261–274CrossRefGoogle Scholar
  83. Shmulevich I, Dougherty ER, Zhang W (2002b) From boolean to probabilistic boolean networks as models of genetic regulatory networks. Proc IEEE 90(11):1778–1792CrossRefGoogle Scholar
  84. Sipser M (1997) Introduction to the theory of computation. PWS Publishing Co, BostonzbMATHGoogle Scholar
  85. Vasershtein L (1969) Markov processes over denumerable products of spaces describing large system of automata. Probl Peredachi Inf 5(3):64–72MathSciNetGoogle Scholar
  86. von Neumann J, Burks AW (eds) (1966) Theory of self-reproducing automata. University of Illinois Press, ChampaignGoogle Scholar
  87. Whitham G (1999) Linear and nonlinear waves, reprint edition edn. Pure and applied mathematics: a Wiley-Interscience series of texts, monographs and tracts. Wiley-Interscience, New YorkCrossRefGoogle Scholar
  88. Wolfram S (1983) Statistical mechanics of cellular automata. Rev Mod Phys 55:601–644ADSCrossRefzbMATHMathSciNetGoogle Scholar
  89. Wolfram S (1986) Theory and applications of cellular automata, vol 1, Advanced series on complex systems. World Scientific Publishing Company, SingaporezbMATHGoogle Scholar
  90. Wolfram S (2002) A new kind of science. Wolfram Media, Champaign Books and Reviews, ChampaignzbMATHGoogle Scholar
  91. Wooldridge M (2002) Introduction to multiagent systems. Wiley, ChichesterGoogle Scholar

Copyright information

© Springer Science+Business Media New York 2013

Authors and Affiliations

  • Reinhard Laubenbacher
    • 1
    Email author
  • Abdul S. Jarrah
    • 2
  • Henning S. Mortveit
    • 1
  • S. S. Ravi
    • 3
  1. 1.Virginia Bioinformatics InstituteVirginia Polytechnic Institute and State UniversityVirginiaUSA
  2. 2.Department of Mathematics and StatisticsAmerican University of SharjahSharjahUnited Arab Emirates
  3. 3.Department of Computer ScienceUniversity at Albany – State University of New YorkNew YorkUSA