Lecture 1: Introduction
Agent-Based Modelling
1
Motivating example: Active commuter travel
Commuters are agents, interacting not only on roads but also in their choice of transport influenced by their social networks (friends, colleagues, neighbours, etc.)
Local authorities want to encourage active travel (more cycling/walking, less private cars) to improve health, reduce pollution, reduce congestion, etc.
How can simulation help governments understand what changes would encourage more active travel?
Today
Simulation using agent-based models
NetLogo
Emergent behaviour
Simulating social interventions
ABM design and validation
Computer simulation
Simulations enact abstracted models of real dynamic phenomena in a computer
Simulations can be used to test theories and gain evidence for the potential effects of interventions (e.g. changes to procedures or structure) without the cost of implementing them
They are useful to understand dynamic complex systems with interacting heterogeneous elements that act locally with incomplete knowledge of the system, such as human societies
Simulations generate data describing a hypothetical realistic world
Modelling the world
Models are abstractions: they simplify the world, and in doing so they leave a lot out.
Models are based on assumptions or theories of what is relevant to the phenomena under study.
Often, the decision to model something is motivated by a theory, and so a model is an attempt to express a theory in a simple form that we can manipulate and explore.
All models are wrong but some are useful.
George Box
Make your theory as simple as possible, but no simpler.
Albert Einstein
5
Why model?
What is our goal when we seek to ‘understand’ the world?
Predict
Explain
Explore
Generate Hypotheses
Discover New Questions
Illuminate Core Dynamics
Characterise Uncertainties
Education and Training
Guide Data Collection
Optimise Performance
Provide a Locus for Discussion
Challenge Prevailing Wisdom
Structure Thinking
Epstein J. 2009. Why model? Journal of Artificial Societies and Social Simulation. 11(4)
6
Model sufficiency
Simulation tends to focus on whether a theory or set of assumptions, suitably formalised as a model, are ‘sufficient’ or ‘practically adequate’ to generate a pattern of interest in a population.
Can we account for the configuration of some real-world pattern?
However, simulation doesn’t prove that process x caused the real-world pattern of interest, simply that it is a candidate explanation.
Other processes may have similar power to generate such patterns.
Further work may then be needed to establish which (if any) candidate explanation is a causal explanation.
7
Stages of simulation
Identify a question that the research will aim to resolve.
Define the real-world system of interest.
Gather some observations of the system of interest to inform the model.
Make some assumptions, or theorise about how the system of interest functions.
Design and build the model.
Verify the model – is the model working properly (in line with theory)?
Validate the model – does the behaviour of the model reflect the real-world system of interest?
Check sensitivity – is the model sensitive to initial conditions?
8
What is agent-based modelling?
Characteristics
Bottom-up modelling technique
Models constituents individually and separately
Comprises agents embedded in an environment
Agents can be heterogeneous
Agents interact and from these interactions, emergent properties and behaviour arise
Allows us to test agent-based interventions to see their effects
Bottom-up modelling
Instead of specifying system
dynamics, model each
component, agent, as an
individual
Agents may represent people,
households, machines, or some other unit regarded as autonomous
Apply knowledge or theories about the behaviour of the agents to construct the model
By not assuming particular behaviour of the
system as a whole, we allow for unexpected
consequences and emergent phenomena
An individual agent can have a substantial
effect on the outcome of the simulation
Environments in ABMs
ABM agents are embedded in an environment that influences how they behave, e.g. their neighbourhood, organisation, social media platform.
In spatial models, agents are distributed in a coordinate grid. Interactions are triggered by and limited to spatial proximity.
In network models, agents are connected by links such as a social network. Interactions are triggered by and limited to network link proximity.
Models can include networks and space
The environment may include non-autonomous resources that agents interact with, and parameters that vary and influence behaviour, e.g. weather
Heterogeneity
ABM agents can have heterogeneity by their different
‘positions’ in the environment
Because agents are modelled individually, they
can also be heterogeneous in their type,
characteristics, or behaviour, e.g. those who own cars vs those who don’t
Agents can have different roles to perform, authority relationships, etc.
Source: www.ea.com
Agent behaviour
Behaviour can be defined in a variety of ways, from simple rules to state-machines to complex plans of actions
Behaviour can be based purely on current state, e.g. what their neighbours are currently doing, or internal properties such as memory of past interactions
Commonly, agent behaviour is
probabilistic, so each simulation
run is unique
Interaction between agents
A critical characteristic of agent-based simulations is that agents interact
Interaction is part or all of an agents behaviour
Due to this interaction, the simulation has unpredictable emergent effects
Interactions can model
observation, conversation,
physical obstruction, or an
abstraction of a more complex
influence on a decision
14
Scales of agent-based model
Some ABMs include thousands of agents following comparatively simple rules over long periods, to expose network effects at scale
Others have comparatively few agents, but each following a rich
behavioural model and in a
complex environment
Many in between
We will see examples of both in
the following slides
Outputs of an ABM
Single simulation runs can be used for generating scenes for films or computer games, but more commonly we aggregate across runs
Each simulation run produces a trace of what has occurred, and we plot some metric to see how it varies over time
Determining how many runs is representative and when we have sufficient coverage can be complex
Individual traces can still be useful to examine outlier situations
NetLogo
NetLogo is a free, open source agent-based modelling platform
Limited compared to writing an ABM in a general programming language but still capable, and an easy and visual starting point for exploring modelling
There are versions for Windows, Mac and Linux plus a web version with cut-down functionality
It uses a variant of the programming language Logo
Includes a diverse models library of sample simulations
https://ccl.northwestern.edu/netlogo/
Many ABM frameworks exist for various languages
17
NetLogo demo
Spatial example
Rabbits-grass-weeds
Network example
Virus on a network
Note that agents are by default called ‘turtles’ and a spatial simulation is typically divided into a grid of ‘patches’ across which agents can move
NetLogo code sample
breed [rabbits rabbit]
rabbits-own [ energy ]
…
to go
if not any? rabbits [ stop ]
grow-grass-and-weeds
ask rabbits
[ move
eat-grass
eat-weeds
reproduce
death ]
tick
end
rabbit (plural ‘rabbits’) is defined as a type
of agent in this model
Each rabbit has an energy attribute
Each rabbit agent is asked to
– move to an adjacent patch
– eat grass/weeds if some on that patch
– spawn new rabbits if enough energy
– die if too little energy
Each of the above are agent-specific
procedures defined elsewhere in the code.
go is called repeatedly while the ‘go’ button
is pressed
Each time, stop if there are no rabbits left
and grow new grass and weeds
After the round is complete, tick the time
counter up by one
Exercise
Can you interpret this code from a single lane traffic jam sim?
Note: ’fd’ tells an agent to move forward in the direction its facing
to go
ask turtles [
let car-ahead one-of turtles-on patch-ahead 1
ifelse car-ahead != nobody
[ slow-down-car car-ahead ]
[ speed-up-car ]
if speed < speed-min [ set speed speed-min ]
if speed > speed-limit [ set speed speed-limit ]
fd speed
]
tick
end
Analysing emergence
Emergent behaviour/properties cannot be analysed by looking at just individual agents
A simulation allows you to see the effect of agent characteristics and their connections (spatial/network) over time
Feedback loops mean that the final results are not a simple function of the initial conditions of each individual agent
Emergence is due to the structure of a dynamic system not its size
Cellular Automata
Cellular automata are a simpler similar idea to agent-based models and an early influence on them
Regular grid (lattice) of cells
Each cell has a state from a fixed set
At each time step, each cell updates its state based on its neighbouring cells according to rules
Can be used, for example, to simulate cell growth in biology and societal phenomena where people’s behaviour is based on their neighbours
22
CA example: Game of Life
The classic example is Conway’s Game of Life
Cells have two states: dead or alive
The rules for a cell are:
If alive with fewer than 2 or more than 3 live neighbours, then become dead
If alive with 2 or 3 live neighbours, stay alive
If dead with exactly 3 live neighbours then become alive
Life in NetLogo
ABMs versus Cellular Automata
Cellular automata can be seen as comparable to agent-based models, where CA cells are the equivalent of ‘agents’
They are different in a few ways
In CAs, all cells follow the same rules, while in ABMs agents may differ in their behaviour
In CAs, each cell has a static location and neighbourhood, while in ABMs agents may move
In CAs, there is no environment beyond the spatial location (neighbourhoods) of cells, while ABMs may have rich dynamic environments
In CAs, cells are reactive, whereas in ABMs agents may memorise and react to the history of events
In general, ABMs allow richer behaviour to be simulated
Schelling’s Segregation Model
Thomas Schelling (1969) created a model of ‘discriminatory individual choices’.
He was interested in “systems that lead to aggregate results that the individual neither intends nor needs to be aware of, the results sometimes having no recognizable counterpart at the level of the individual
Does spatial segregation between groups in cities imply that individuals are intolerant?
25
Schelling’s Segregation Model
Two types of agents: Red and Green, roughly equal numbers.
The world is a grid. Only 1 agent can occupy a cell at a given time.
The neighbourhood is the 8 cells surrounding each cell.
Agents can be imbued with a rule concerning similarity.
What percentage of your neighbours should be the same as you?
An agent is either happy or unhappy with their home cell based on the rule.
Happy = stay put
Unhappy = move (at random) to an unoccupied space.
Segregation model in NetLogo…
NB agents don’t seem to mind if they have no neighbours.
The world wraps around.
What fraction of neighbours
26
Contemporary Segregation in New York City
New York Times – Dot Density Map of Segregation by Racial and Ethnic Groups.
https://www.nytimes.com/interactive/2015/07/08/us/census-race-map.html
Ethnic Distribution of Greater London Asian-Black-White Comparison (UK CeNSUS 2011)
https://en.wikipedia.org/wiki/Ethnic_groups_in_London
white
black
asian
28
Discussion
If someone was proposing to use this model to inform government social policy, what criticisms might be made about its realism?
Pragmatic evaluation
Accept that our models will never be ‘true’
Make this explicitly clear to model users/users of model output
Never over-sell the model – you (and science in general) will lose out in the long run
Model evaluation is about demonstrating the utility of a model, not about saying ‘yes, this model is correct’ or ‘no, this model is incorrect’
Exploring interventions
An intervention is something that changes agent behaviour
Could be a change to the agent rules or configuration, or the environment’s parameters or structure
An intervention can be explored by simulating the ‘before’ and ‘after’ and comparing
We use ABMs in this way to get evidence for the potential effect of an intervention
before it is implemented in
reality (which can be costly)
We may explore what
happens in unusual cases as
well as the typical/average
situation
Picture showing adding cycle superhighway to affect commuter travel choices
31
Influence maximisation
In a network of agents that can influence each other (e.g. a social network), we can try to identify the agents that have maximum influence
By affecting these individuals behaviour, we can affect a larger population
This can reduce the cost of an intervention
For example, by convincing a few people of the need to switch to greener modes of transport, can we cause a wider change in the culture and so the behaviour of the wider society?
Exercise
D
A
B
F
E
G
H
C
We can influence 1 agent in the social network below. Which agent
should we choose if the agent will also influence:
its direct connections?
its direct connections plus their direct connections? (2 hops)
its direct connections plus their direct connections plus their
direct connections? (3 hops)
33
Spreading functions
Different simulations use different models of how one agent influences another
Peer pressure, e.g. changing commuter behaviour, can be modelled as: an agent is influenced if a large enough number of their connections are influenced (similar to Game of Life)
Disease spread can be modelled as: an agent is influenced with a certain probability for each connection influenced
Engineering agent-based simulation models
Background research
Model construction
Conceptual modelling
Implementation
Verication & validation (V&V)
Experimentation / productive use
Example of creating an ABM for social analysis
In UK, children are admitted to state schools through admissions policies
Parents apply to a few schools they prefer
Policies vary but the distance between a school and where a child lives is always one factor
Parents try to move house to be nearer good schools ahead of applying
Richer parents can afford a greater range of houses so their children end up at better schools, increasing inequality
King’s Geography Department studied this in London using an ABM (created by Dr James Millington, see http://landscapemodelling.net)
Admissions policies
Other boroughs account for:
Special Educational Needs
Medical/Social Needs
Siblings
Example policy from one London borough
Empirical patterns
Empirical patterns
Barking Abbey
Warren
Empirical patterns
Barking Abbey
Warren
Empirical patterns
Objectives of the agent-based model
Generate empirical macroscopic patterns
Explore consequences of interventions, e.g.
Removal/addition of schools
Change in school inputs
42
Model structure
Agents in the model are families and schools
Family attributes include child age, aspiration, current location…
School attributes include location, GCSE (academic attainment) score, available places…
Families can move once prior to application
Families rank schools for moving and applying
Different families will follow different strategies based on their aspiration in ranking schools by distance and by attainment
The model’s parameters are tuned to reproduce the patterns seen in reality
The model in NetLogo
Another example social ABM
Implementing comprehensive offender behaviour in a realistic agent-based model of burglary, Malleson et al. 2012
Simulates burglary patterns in East Leeds (UK) based on incident data and behaviour theories, to make explainable predictions of city-level crime patterns.
The theory proposes that burglars become aware of potential victims either by active searching or passing them on unrelated journeys.
A simulated potential burglar’s mental state is characterised by the drugs in their system, how much they have socialised, and what sleep they’ve had, but the effects of these varies per individual.
The burglary process comprises deciding where to start looking for victims, searching for victims, and deciding upon a suitable target based on factors such as ‘community effectiveness’, traffic volume, accessibility, etc.
Designing agents
Agents in ABMs can be of any complexity
Those shown earlier in this lecture are quite simple and reactive
We can use BDI, subsumption architectures, or any of the techniques explored later in this module
Commonly ABM agents are simpler than agents engineered for productive function, e.g. Mars rover, sea rescue drones, etc.
ABM agents are sometimes defined by state machines
e.g. transition between states of happy, hungry, afraid and behave accordingly
Or by rules (often probabilistic)
e.g. if my neighbours do X, do X with P probability; else do Y
We want the simplest agent models to capture relevant reality
Psychological agents
For social simulations, we often want to simulate some aspect of the psychology of individuals, e.g.
Aspiration in the schools placement ABM
Comfort of familiarity in the segregation ABM
We can also include psychological models from literature as mathematical functions influencing behaviour, e.g.
Workplace stress levels affecting activity performance
Trust levels affecting whether transactions take place
ABM agents simulate learning using reinforcement learning (a category of machine learning)
Example: A&E ABM staff agent
Staff behaviour workflow
Staff stress model
(Yerkes-Dodson)
Purposes of A&E model
Service redesign
Understand capacity
Understand behaviour
Testing robustness/resilience
Forecasting
Data and model correctness
Calibration
Set agent and environment parameters to match reality
Verification
Are we building the simulation right?
Testing, formal verification (theorem proving, model checking), sensitivity analysis
Validation
Are we building the right simulation?
External correctness, sufficient correspondence with reality
Face validation: does what happens look plausible?
Comparison of emergent properties with real world data
Next week
Next week we will look at how to design agents in multi-agent systems can communicate and coordinate to complete tasks
/docProps/thumbnail.jpeg