Dream CDT Symposium
Dynamic Simulation Models & Data Assimilation
Nick Malleson
Associate Professor
School of Geography, University of Leeds, UK
nickmalleson.co.uk
These slides: https://urban-analytics.github.io/dust/presentations.html
Acknowledgements
Luke Archer & Kevin Minors, Data Science Interns, Leeds Institute for Data Analytics
Minh Kieu, Leeds Institute for Data Analytics
Jon Ward, School of Mathematics
Alison Heppenstall, School of Geography
Christoforos Anagnostopoulos, Jonathan Coello, and others at Improbable.
Overview
Agent-Based Modelling (for Urban Dynamics)
Dynamic City Simulation
Part 1: Agent-Based Modelling (for Urban Dynamics)
Why is it difficult to model urban spatial systems?
Extremely complex system:
Attributes of the environment (e.g. individual houses, pubs, transport hubs, parks, etc.).
Personal characteristics (heterogeneity).
Features of the local community.
Physical layout of the neighbourhood (e.g. street networks).
Why is it difficult to model urban spatial systems?
Traditional approaches often work at large scales, struggle to predict local effects
"Computationally convenient".
But cannot capture non-linear, complex systems.
Introduction to ABM
Aggregate v.s. Individual
'Traditional' modelling methods work at an aggregate level, from the top-down
E.g. Regression, spatial interaction modelling, location-allocation, etc.
Aggregate models work very well in some situations
Homogeneous individuals
Interactions not important
Very large systems (e.g. pressure-volume gas relationship)
Introduction to ABM
Aggregate v.s. Individual
But they miss some important things:
Low-level dynamics, i.e. “smoothing out” (Batty, 2005)
Interactions and emergence
Individual heterogeneity
Unsuitable for modelling complex systems
Introduction to ABM
Systems are driven by individuals
(cars, people, ants, trees, whatever)
Bottom-up modelling
An alternative approach to modelling
Rather than controlling from the top, try to represent the individuals
Account for system behaviour directly
Autonomous, interacting agents
Represent individuals or groups
Situated in a virtual environment
Agent-Based Modelling - Appeal
Modelling complexity, non-linearity, emergence
Natural description of a system
Bridge between verbal theories and mathematical models
Produces a history of the evolution of the system
Agent-Based Modelling - Difficulties
(actually he played with his trains...)
Tendency towards minimal behavioural complexity
Stochasticity
Computationally expensive (not amenable to optimisation)
Complicated agent decisions, lots of decisions, multiple model runs
Modelling "soft" human factors
Need detailed, high-resolution, individual-level data
Individual-level data
Modelling agent behaviours
Many behaviours are hard / impossible to model
Choose those that are the most important. Cannot include everything!
Some can be very simple - e.g. threshold-based rules (Kennedy, 2012)
IF hunger IS ABOVE hunger_threshold THEN search_for_food
OTHERWISE do_something_else
These are the most common (Birks et al. 2012, 2013; Dray et al. 2008; Groff 2007a,b; Hayslett-McCall, 2008)
More advanced cognitive frameworks exist
Beliefs, Desires, Intentions (Bratman et al., 1988)
PECS (Schmidt, 2000).
An experiment:
Choose a number between 1 and 4 (inclusive)
Were you able to chose a number at random?
Or did most people choose the number 3?
ABM Crime Example
Predictive: exploring the real world
ABM to explore the impacts of real-world policies
Urban regeneration in Leeds
ABM Predictive Example
Scenario Results
Part 2: Dynamic City Simulation
How many people are there in Trafalgar Square right now?
We need to better understand urban flows:
Crime – how many possible victims?
Pollution – who is being exposed? Where are the hotspots?
Economy – can we attract more people to our city centre?
Health - can we encourage more active travel?
Smart cities and the data deluge
Abundance of data about individuals and their environment
"Big data revolution" (Mayer-Schonberger and Cukier, 2013)
"Data deluge" (Kitchin, 2013a)
Smart cities
cities that "are increasingly composed of and monitored by pervasive and ubiquitous computing" (Kitchin, 2013a)
Large and growing literature
But how to combine messy, biased, disparate data?
Agent-Based Models of the Ambient Population
Agent-based modelling to the rescue?
Could combine diverse, up-to-date data with a model to create the most accurate estimate of the real world
But:
Urban systems are complex
They will diverge rapidly from model predictions
ABM development typically uses 'waterfall' approach
We lack tools to calibrate models in response to new data dynamically
Divergence
Complex systems
One-shot calibration
Nonlinear models predict near future well, but diverge over time.
Question
Can you suggest another field that is brilliant at incorporating up-to-date information about the world into their models?
Dynamic Data Assimilation
Used in meteorology and hydrology to constrain models closer to reality.
Try to improve estimates of the true system state by combining:
Noisy, real-world observations
Model estimates of the system state
Should be more accurate than data / observations in isolation.
Data Assimilation Methods
Particle filters
Indoor footfall (Rai and Hu, 2013.; Wang and Hu, 2015)
Kalman Filter
Air traffic (Chen et al., 2012)
Ensemble Kalman Filter (EnKF)
Pedestrian footfall (Ward et al., 2016)
Sequential Monte Carlo (SMC)
Wildfire (Hu, 2011; Mandel et al., 2012)
Approximate Bayesian Computation
?
Example 1:
Ensemble Kalman Filter (EnKF)
Maths
Broad literature, but generally tied to mathematical models (e.g. differential equations and linear functions)
Working with a mathematician to do the hard work!
In all its glory: Ward et al., (2016)
Advantages
Similar to Kalman Filter (best in class)
But better for nonlinear systems
Ensemble Kalman Filter - Basic Process
1. Forecast.
Run an ensemble of models (ABMs) forward in time.
Calculate ensemble mean and variance
2. Analysis.
New 'real' data are available
Integrate these data with the model forecasts to create estimate of model parameter(s)
Impact of new observations depends on their accuracy
3. Repeat
Ensemble Kalman Filter (EnKF)
Example 2
Bus Simulation with a Particle Filter
Context: simulate bus routes in real time
We have GPS bus positions, but to make good term forecasts we need to be able to infer other factors
Number of people waiting at bus stops
Number of people on the bus
Surrounding traffic levels
Etc.
Aim: test a particle filter as the means of assimilating real-time GPS positions into a model.
Particle Filter
A 'brute force' ensemble method
Create N realisations of the model ('particles')
Run each particle forward in time until you receive some new data
Compare the particles to the observation and:
Weight each particle depending on how close it is to the observations
Resample the population of particles using the weights (good particles are kept, bad ones disappear)
Repeat
Bus Simulation
Bus Simulation - No Data Assimilation
Bus Simulation with a Particle Filter
Example 3
Crowd Simulation with a Particle Filter
Context: simulate a crowd in real time
What methods can we use to assimilate data?
How much data do we need?
Track every individual?
Track some individuals?
Just aggregate counts (e.g. number of people passing a footfall camera)
Case study: a simple, hypothetical train station (Station Sim)
Crowd Simulation with a Particle Filter
Dynamic City Simulation: What Next?
Short-term
Crowd simulation with a * Kalman Filter - computationally feasible?
Bus simulation with real GPS traces - applications to real cities
Medium-term
Simulations of larger systems - high streets, villages, towns
Integrate disparate models (e.g. microsimulation, population projections ... )
Long-term
Real-time, dynamic simulation of an urban area (a 'digital twin')
Provide the best representation of now
Could transform the way that cities are managed
For more information about what we're doing
Data Assimilation for Agent-Based Models (dust)
Main aim: create new methods for dynamically assimilating data into agent-based models.
Uncertainty in agent-based models for smart city forecasts
Developing methods that can be used to better understand uncertainty in individual-level models of cities
Bringing the Social City to the Smart City
https://alisonheppenstall.co.uk/research/bringing-the-social-city-to-the-smart-city/
For more information about what we're doing
AAMAS presentation:
Understanding Input Data Requirements and Quantifying Uncertainty for Successfully Modelling ‘Smart’ Cities. Presentation to the 3rd International Workshop on Agent-Based Modelling of Urban Systems (ABMUS), part of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018). 10-15 July, Stockholm. Full abstract (pdf).
Now Recruiting:
Simulating Urban Systems
Post-doctoral Research Fellow (grade 7)
Full time, 3 years
Application deadline: April 2019
Summary
Agent-Based Modelling (for Urban Dynamics)
Dynamic City Simulation
Data assimilation
Simulating crowds
... and later, cities!