ngineering
ttiunb158364
ABMSCoursework9notes.pptxIntroduction
ABMS
www.drandrewjcollins.com
Outline
Here is what is covered
Definition
History
Important Concepts
Related Subjects
Classic Examples
Software
www.drandrewjcollins.com
Introduction
Agent-based Modeling and Simulation (ABMS)
The purpose of this lecture is to:
Introduce ABMS
Give an overview of its history
Discuss some basic concepts and related subjects
Introduce some classic examples
www.drandrewjcollins.com
Check go add-ins now for later.
Definition
There is no clearly accepted definition what agent-based modeling is. Multiple definition exist, for example:
North and Macal
Gilbert
Why?
ABMS is a relatively new subject that is used by a lot of different groups, e.g., social scientist, computer scientist, operations researcher, biologist
Each group has its own view on the world and its own terminology
www.drandrewjcollins.com
Check go add-ins now for later.
North and Macal
Agent-based simulation are built around agents. The characteristics of an agent being: adaptive, capability to learn, modify behaviors, autonomous, and heterogeneous
North, Michael J., and Charles M. Macal. 2007. Managing Business Complexity: Discovering Strategic Solutions with Agent-Based Modeling and Simulation. New York: Oxford University Press
Operations Researcher and Computer Scientist
Focus on technical design of ABMS
www.drandrewjcollins.com
Check go add-ins now for later.
Gilbert
“Agent-based modeling is a computational method that enables a researcher to create, analyze, and experiment with models composed of agents that interact with an environment”
Gilbert, Nigel. 2007. Agent-Based Models. Thousand Oaks, CA: Sage Publications
Social Scientist
Not use of words like simulation, adaption, etc.
www.drandrewjcollins.com
Check go add-ins now for later.
North and Macal’s definition focuses on the requirements of ABMS
Not all agree with them
N.B. Under their definition, the most famous ABMS, i.e., Schelling’s Segregation model, would not be an ABMS
Gilbert’s definitions focuses on the model’s purpose
Definition Conflict
www.drandrewjcollins.com
www.drandrewjcollins.com
History
www.drandrewjcollins.com
1970
1970
Game of Life
John Conways (British)
Gardener, Martin. “Mathematical Games - The Fantastic Combinations of John Conway’s New Solitaire Game ‘Life’.” Scientific American, 1970
1971
Schelling’s Segregation Model
Schelling, Thomas C., 1971. Dynamic Models of Segregation. Journal Of Mathematical Sociology, 1(2), pp.143–186.
www.drandrewjcollins.com
Conway could publish work in 100 journals now!
1980
1984
Iterated Prisoner’s Dilemma
Axelrod, Robert. 1984. The Evolution of Co-operation. Basic Books.
Axelrod, Robert. 1997. The Complexity of Cooperation: Agent-based Models of Competition and Collaboration. Princeton: Princeton University Press.
1986
Boids
Craig W. Reynolds
Reynolds, Craig W. “Flocks, Herds and Schools: A Distributed Behavioral Model.” In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, 25–34. SIGGRAPH ’87. New York, NY, USA: ACM, 1987.
Tron (1982)
www.drandrewjcollins.com
http://en.wikipedia.org/wiki/Craig_Reynolds_(computer_graphics)
Axelrod is a politicial scientist
Reynolds was also a computer graphics guy and worked on the first version of Tron
1991
Coined term “agent”
Holland, John H., and John H. Miller. “Artificial Adaptive Agents in Economic Theory.” The American Economic Review 81, no. 2 (1991): 365–370.
John H. Miller
See 2000s
John Holland
Father Genetic Algorithm
Holland, John. 1996. Hidden Order: How Adaptation Builds Complexity. First Edition. Basic Books.
1996
Sugarscape
Epstein, Joshua M., and Robert L. Axtell. Growing Artificial Societies: Social Science from the Bottom Up. 1996. Brookings Press: Washington DC
Formed AI ABM Society
1990
www.drandrewjcollins.com
Societies
North American Association of Computational Social & Organization Sciences (NACSOS)
Was Computational & Mathematical Organization Theory
Part of The Computational Social Science Society of Americas (CSSAS)
http://computationalsocialscience.org/
Died
European Social Simulation Association (ESSA)
Journal of Artificial Societies and Social Simulation (JASSS)
Founder: Nigel Gilbert
Gilbert, Nigel. 2007. Agent-Based Models. Thousand Oaks, CA: Sage Publications, Inc.
1990
www.drandrewjcollins.com
Textbooks
Generative Social Science
Epstein, Joshua .M., 2007. Generative Social Science: Studies in Agent-Based Computational Modeling, Princeton University Press.
“If you didn’t grow it, you didn’t explain it”
Complex Adaptive Systems
Miller, John H., and Scott E. Page. 2007. Complex Adaptive Systems: An Introduction to Computational Models of Social Life. Princeton University Press.
2000
www.drandrewjcollins.com
Conferences
Agent 20XY
SwarmFest
Autononmous Agents and Multiagent Systems (AAMAS)
International Conference on Social Computing, Behavioral-Cultural Modeling, & Predication (SBP)
Practical Application of Agents and Multi-agent Systems (PAAMS)
2000
www.drandrewjcollins.com
PAAMS has died as of 2013
Network for Computational Modeling for SocioEcological Science (CoMSES Net)
Standardization
Unified Modeling Language (UML)
Overview, Design concepts, and Details (ODD)
You?
2010
www.drandrewjcollins.com
Important Concepts
www.drandrewjcollins.com
Micro level modeling considers each individual agent
Macro level modeling amalgamates agents into groups, flows or statistics (averages)
Continuous simulation
What is an agent?
The research questions determines what is the agent of interest
Usually a human, vehicle or organization
But a human is an amalgamation of cells, and cells are amalgamations of atoms, and atoms are … (don’t care)
Macro and micro
www.drandrewjcollins.com
Emergent Behavior is observing macro-level phenomenon from micro-level behaviors
Emergence is an important concept for ABMS
Why?
It is the emergent macro behavior/phenomenon that makes ABMS a useful tool
Example
Observing a property market collapse due to individuals strategically defaulting
Emergent Behavior
www.drandrewjcollins.com
Complex Adaptive Systems (CAS)
Founding theory for ABMS
Miller and Page 2007
Complex vs. Complicated systems
Complicated Systems
A complicated system is made up of elements that are independent of each other
Removing one element does not alter the systems behavior apart from a direct result of what was removed.
Complex Systems
A complicated system is made up of elements that are dependent of each other
Removing one element fundamentally alters the system.
Emergence
www.drandrewjcollins.com
Example (Miller and Page, 2007, p. 9)
Removing a seat from a car makes it less complicated.
Removing a timing belt from a car makes it less complex (and useless)
Emergence
www.drandrewjcollins.com
Idea of complexity is in conflict with reductionist
Reductionist hypothesis
Get right simplifications then can understand everything.
Extreme would be that everything can be communicated through applied physics
Called “Greedy Reduction”
Problems for emergent behavior
Says things are only sum of parts so can look at them individually
CAS view says need consider whole system to observe emergent behavior
Emergence
www.drandrewjcollins.com
Emergence has lead to a call for there to be a new kind of science:
Traditional Science: Make hypothesis and test it with data from the real world
e.g., Chemical X turns blue when added to water
Axiomatic Science: Make hypothesis and test against existing theory
Paradigm Shifts: Change theory if necessary
e.g., Increased internet access means increased economic growth
New Science: Make hypothesis and test with data from simulations built using existing theory and data
A New Kind of Science?
www.drandrewjcollins.com
Adaption is the ability to change behavior or self-organization based on environmental stimulus or collection of stimulus
Ability to learn
Natural Selection (for a species)
N.B. Does not always mean that the change is for the better
Adaption
www.drandrewjcollins.com
Within an simulated agent, adaption can be modeled a number of different ways:
Artificial Intelligence
Can make the simulation more complex and hard to write code for
e.g., reinforcement learning, genetic algorithms, neural networks
Threshold Equations
Allows for simple changes
e.g., Agent waiting in line has some attribute called “impatience”; when impatience level reaches a certain threshold, agent leaves line.
Adaption
www.drandrewjcollins.com
Heterogeneity is defined as the quality of being diverse and not comparable in kind
Homogeneity is opposite
Homogeneity used when you need to amalgamate all the agents
Continuous Simulation
Macro Simulation
Hard to implement
Does just labeling agents differently make them heterogeneous?
What about giving the different spatial locations?
Heterogeneity
www.drandrewjcollins.com
No, because does not matter how label
If there locations can be interchanged without fundmentally affecting the agents, then no
Related Subjects
www.drandrewjcollins.com
“Standing to the shoulders of giants”
ABMS development has been dependent of other academic subjects
Its roots are formed from
Game Theory, Cellular Automata, DES, Multi-agent Modeling
Each subject brings with it its own existing knowledge
And its own baggage of expectations, terminology, and assumptions
Related Subjects
www.drandrewjcollins.com
Game Theory is the modeling of situations involving multiple decision-makers
Von Neumann, John, and Oskar Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press.
Thomas Schelling
2005 Noble Prize for Game Theory
Robert Axelrod
Iterated Prisoner’s Dilemma
Game Theory
www.drandrewjcollins.com
Note all these names from earlier
Cellular Automata is a collection of "colored" cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells.
Von Neumann, John and Ulum, Stanislaw
1940s
Manhattan Project
Wolfram, Stephen.
2002. A New Kind of Science. 1st ed. Champaign, IL: Wolfram Media.
Mathematica
www.wolframalpha.com
Cellular Automata
www.drandrewjcollins.com
Von neumann again
www.drandrewjcollins.com
A glider
www.drandrewjcollins.com
Glider
Discrete Event Simulation (DES) is when the operation of system is represented as an ordered sequence of events and changes of state in the system, it is event driven.
Can (and has) been argued that ABMS is just a subset of DES
How else implement ABMS?
Discrete Event Simulation
www.drandrewjcollins.com
But implementation is not the only factor of a paradigm.
By this argument DES is just a software nothing more….
Could impliment ABMS with real human actors. Would be cool to see.
Computer Science subject
Concern with autonomous computer software agents interacting
From Wikipedia:
“An agent-based model (ABM) (sometimes confused with the term multi-agent system or multi-agent simulation)
Multi-agent Modeling
www.drandrewjcollins.com
So pleased someone but this on wikipedia. It is confused at LOT
Historical Examples
www.drandrewjcollins.com
Schelling’s Segregation Model (1971)
Often quoted as first example of ABMS
Developed model to explain the formation of social segregation in US cities
Schelling did the work for this model using:
Graph paper
Nickels and Quarters
NO computer
Segregation Model
www.drandrewjcollins.com
www.drandrewjcollins.com
Two types of agent: red and blue
Living in a grid with empty spaces
Rules of Segregation Model:
If an agent finds the proportion of neighbors of the other type is greater than some “tolerance” threshold then they will move to a new random location
Results
Schelling found that even for high tolerance thresholds segregation occurred
What would happen if the agents were complete tolerant of neighbor type?
Segregation Model
www.drandrewjcollins.com
John Conways (1970)
Form of cellular automata
Conway called it “recreational mathematics”
So did not publish
Idea was to try and replicate requirements for life
Important: the game of life was an abstraction of realty; a model
Game of Life
www.drandrewjcollins.com
AJC: wish I had published this.
It is the abstraction that makes a difference. The modeling part of M&S
Rules of Game of Life
Survivals. Every agent with two or three neighboring agents survives for the next generation.
Deaths. Each agent with four or more neighbors dies (is removed) from overpopulation. Every agent with one neighbor or none dies from isolation.
Births. Each empty cell adjacent to exactly three neighbors--no more, no fewer--is a birth cell. A new agent is placed on it at the next move.
Game of Life
www.drandrewjcollins.com
Craig W. Reynolds (1986)
Boids was an attempt to replicate flocking behavior of birds
Was very successful
Followed on by Social Force Dynamics for crowd modeling
“Boids” is pronounced like a New Yorker would say “birds”
Boids
www.drandrewjcollins.com
www.drandrewjcollins.com
Rules of Boids:
Separation: Avoid Crowding
Not allowed to get too close to neighbor
Alignment: Steer Average Heading
Cohesion: Steer to center of Mass
These rules are translated into forces which are amalgamated to choose new direction for the boid.
Boids
www.drandrewjcollins.com
Epstein and Axtell (1996)
Abstract representation of a simple society
The model follows agents that live, trade, reproduce, and die on a doughnut-shaped surface that contains growing sugar
Brahms
Software tool derived from Sugarscape
Sugar Scape
www.drandrewjcollins.com
Know how make surface into a doughnut?
Software
www.drandrewjcollins.com
Anylogic
Multi-paradigm
Discrete Event Simulation
System Dynamics
XJ Technologies ($3500)
Brahms
From Sugarscape
Mason
Multi-Agent Simulator Of Neighborhoods... or Networks
Java Based
George Mason University
ABMS Software
www.drandrewjcollins.com
Netlogo
Most widely used
Repast Simphony
Java Based
Argonne National Lab
Michael J. North & Charles Macal
Swarm
Sante Fe Instituate
Is dying
ABMS Software
www.drandrewjcollins.com
Railsback, S.F., Lytinen, S.L. & Jackson, S.K., 2006. Agent-based Simulation Platforms: Review and Development Recommendations. SIMULATION, 82(9), pp.609–623
Paper says that:
Netlogo is the easiest
Repast is the quickest
Comparison
www.drandrewjcollins.com
Net Logo
Uri Wilensky. 1999. Netlogo. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL. http://ccl.northwestern.edu/netlogo/.
Repast Simphony
North, M.J., T.R. Howe, N.T. Collier, and J.R. Vos, "A Declarative Model Assembly Infrastructure for Verification and Validation," in S. Takahashi, D.L. Sallach and J. Rouchier, eds., Advancing Social Simulation: The First World Congress, Springer, Heidelberg, FRG (2007)
References
www.drandrewjcollins.com
End Presentation
www.drandrewjcollins.com
