Urban Modelling & Complexity Science
19-20 September 2019, CASA, London
Simulating Pedestrian Systems in Real Time using Agent-Based Models
Nick Malleson
Professor of Spatial Science
School of Geography, University of Leeds
and Fellow of the Alan Turing Institute
These slides: http://dust.leeds.ac.uk
The paper: arxiv.org/abs/1909.09397
Abstract
Background.
Agent-based modelling has been shown to be a valuable method for modelling systems whose behaviour is driven by the interactions between distinct entities. They have shown particular promise as a means of modelling crowds of people in streets, public transport terminals, stadiums, etc. However, the methodology faces a fundamental difficulty: there are no established mechanisms for dynamically incorporating real-time data into models. This limits simulations that are inherently dynamic, such as pedestrian movements, to scenario testing on historical data.
Method.
This work begins to address this fundamental gap by demonstrating how a particle filter could be used to incorporate real data into an agent-based model of pedestrian movements at run time.
Results.
The experiments show that it is indeed possible to use a particle filter to perform online (real time) model optimisation. However, as the number of agents increases, the number of individual particles (and hence the computational complexity) required increases exponentially.
Future.
By laying the groundwork for the real-time simulation of crowd movements, this work has implications for the management of complex environments (both nationally and internationally) such as transportation hubs, hospitals, shopping centres, etc.
Data Assimilation for Agent-Based Models (DUST)
5-year research project (€1.5M)
Funded by the European Research Council
Main aim: create new methods for dynamically assimilating data into agent-based models.
Simulating Crowds in Real Time with Agent-Based Modelling and a Particle Filter
Nick Malleson
Kevin Minors
Le-Minh Kieu
Jonathan A. Ward
Andrew A. West
Alison Heppenstall
The paper: arxiv.org/abs/1909.09397
What is happening in Kings Cross station right now?
Real-time simulations of crowds will allow us to:
Better understand what is happening now
Improved day-to-day management of busy places
Management of emergency situations
Make more accurate short-term forecasts
Detect problems arising before they become serious
Real Time Crowd Modelling
Agent-based modelling: Simulate the (synthetic) individuals whose behaviour drives the system
Models predict near future well, but diverge over time.
We need a way to assimilate new data into our models
Real Time Crowd Modelling
Context: simulate a crowd in real time
What methods can we use to incorporate 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)
Collisions in StationSim
Agents move from one side to the other
If a fast agent reaches a slow agent, the try to move round to the left or right
Random binary decision
Only source of uncertainty
Particle Filter Results
Exponential increase in complexity
Problem
How can we incorporate up-to-date data into our crowd model?
Question
Can you suggest a field that is brilliant at incorporating up-to-date information about the world into their models?
Data Assimilation
Used in meteorology and hydrology to constrain models to reality.
Assumptions:
Data have relatively low uncertainty, but are sparse
Models are detailed, but uncertain
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
Other advantages
Move information from data-rich to data-poor areas
Quantify the uncertainties in the model
I.e. model structure v.s. parameter / variable values
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
?
Particle Filter
A 'brute force' ensemble method
No Gaussian assumptions
Create N realisations of the model ('particles')
Run all the particles 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
Re-sample the population of particles using the weights (good particles are kept, bad ones disappear)
Repeat
Experimental Setup
'Identical twin' experiment: known 'real world' conditions
Crowd Simulation with a Particle Filter
Crowd Simulation with a Particle Filter
Particle Filter Results
Particle Filter Results
Particle Filter Results - Summary
Real-time assimilation of data into a crowd model is possible. But:
Very few model parameters & variables are unknown (easy)
It knows entrance gate and time, destination, max speed, etc...
Assumes we can track individuals
Unrealistic and unethical?
Future work moving towards aggregated population counters
High computational cost
10,000 particles for only 40 agents in a simple system, will need millions for more realistic scenarios
Opportunities to make more efficient, e.g. 'component set resampling' (Wang &Hu, 2015), or through use of GPU clusters
What about an Unscented Kalman Filter?
Ethical Implications
Data Bias
Need to be very careful: biased data -> biased models
The digital divide
Tracking People
Advantage with these methods is we don't need to track people
Models work with counts of flows
One other example:
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.
Bus Simulation
Bus Simulation with a Particle Filter
Towards Digital Twins of Human Systems
Join up simulations at multiple spatial and temporal resolutions
Simulations of traffic and crows in real time
Predictions of longer-term changes (e.g. new roads, trains, etc.)
Models of long term demographic change (migration, ageing, birth, etc.)
Real-time analysis tools and sandpits for policy development
Urban Analytics Programme
Cities are the home to the majority of the world's population
They drive economic growth, wealth creation, social interaction, well-being
But also: inequalities in health, affluence, education and lifestyle
Programme aim: Develop data science and AI focused on the process, structure, interactions and evolution of agents, technology and infrastructure within and between cities.
For more information:
www.turing.ac.uk/research/research-programmes/urban-analytics
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
turing.ac.uk/research/research-projects/uncertainty-agent-based-models-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
Using AI and machine learning to understand and simulate cities
turing.ac.uk/research/research-projects/bringing-social-city-smart-city
Now (almost!) Recruiting:
Research Fellow in Urban Analytics
4* Post-doctoral Research Fellow (grade 7)
Full time, 2 years +
Advert is imminent!