Workshop on Data-Driven Economic
Agent-Based Models (DDEABM)
Sant'Anna School of Advanced Studies, Pisa, 27-28 September 2022

Data Assimilation for Agent-Based Models

Nick Malleson and Patricia Ternes

University of Leeds, UK

n.s.malleson@leeds.ac.uk

Slides available at:
https://urban-analytics.github.io/dust/presentations.html

Quantifying Real-Time Urban Dynamics

People are the drivers of processes in cities

We need to understand mobility patterns:

Crime – how many possible victims?

Pollution – who is being exposed? Where are the hotspots?

Economy – can we attract more people to our city centres?

Disease - which times / places have large numbers of interactions

Vision

A digital twin (in engineering)

An ABM that simulates urban processes

Updated in real-time using data assimilation

A 'digital twin'?

Presentation Outline

Data assimilation and ABM challenges

Latest research with a Particle Filter and a crowd simulation:

'Vanilla' filter

Estimating categorical parameters

Other opportunities

Unscented / Ensemble Kalman Filters

MCMC sampling

Data Assimilation for Agent-Based Modelling

dust.leeds.ac.uk/

Thanks

Josie McCulloch, Alison Heppenstall, Keiran Suchak, Minh Kieu, Molly Asher, Kevin Minors, Andrew West, Dan Tang, Yannick Oswald, Robert Clay, Annabel Whipp, Jon Ward, Thomas Crols

Why we need Data Assimilation

Complex models will always diverge

(due to inherent uncertainties in inputs, parameter values, model structure, etc.)

Possible Solution: Data Assimilation

Used in meteorology and hydrology to bring models closer to reality. Combines:

Noisy, real-world observations

Model estimates of the system state

Data assimilation v.s. calibration

Example of optimising the model state using observations and data assimilation

Challenges for using DA with ABMs

Model size

10,000 agents * 5 variables = 50,000 distinct parameters

Agent behaviour

Agent's have goals, needs, etc., so can't be arbitrarily adjusted

Assumptions and parameter types

Maths typically developed for continuous parameters and assume normal distributions

... but, at least, many of these problems are shared by climate models

Real Time City Crowd Modelling

Image of escalators in a train station

Simulating a city in real-time is too hard!! (for now)

For now lets start a crowd

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)

Data assimilation with a Particle Filter

Flowchart of the experimental design. Lots of models ('particles') are run simultaneously.

Particle Filter & Crowd Simulation

Station PF experimental design.

Crowd Simulation with a Particle Filter

Animation of a crowding model with data assimilation

Preliminary Particle Filter Results

Box Environment: More particles = lower error

median absolute error change with number of agents and particles: greater complexity caused by larger numbers of agents can be mitigated by increasing the numbers of particles.
Malleson, Nick, Kevin Minors, Le-Minh Kieu, Jonathan A. Ward, Andrew West, and Alison Heppenstall. (2020) Simulating Crowds in Real Time with Agent-Based Modelling and a Particle Filter. Journal of Artificial Societies and Social Simulation 23(3) DOI: 10.18564/jasss.4266.

Difficulties (I)

Exponential increase in complexity

Number of collisions increases exponentially with number of agents
N. Malleson, K. Minors, Le-Minh Kieu, J. A. Ward, A. West and Alison Heppenstall (2020). Simulating Crowds in Real Time with Agent-Based Modelling and a Particle Filter. Journal of Artificial Societies and Social Simulation (JASSS) 23(3), 3.

Grand Central Terminal (New York)

Pedestrian traces

B. Zhou, X. Wang and X. Tang. (2012) Understanding Collective Crowd Behaviors: Learning a Mixture Model of Dynamic Pedestrian-Agents. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2012

http://www.ee.cuhk.edu.hk/~xgwang/grandcentral.html

Grand Central Terminal floor plan with entrances around the sides and an obstruction in the centre. Pedestrian trajectories estimated from the video

Preliminary Particle Filter Results

Grand Central Station: Filtering makes it worse!

Entrance gate is known; speed and exit gate are unknown

Distance between agent and real trajectory (Pedestrian time).

Ternes, P., J. Ward, A. Heppenstall, V. Kumar, Le-Minh Kieu, N. Malleson (2022) Data assimilation and agent-based modelling: towards the incorporation of categorical agent parameters. Open Research Europe 1(131).

Particle Filter & Categorical Parameters

(video)

Difficulties (II)

  • Exponential increase in complexity
  • Categorical Parameters
  • Non-linear trajectories (change in categorical parameters)

Categorical-Noise PF Step

Overview

Shows that some pedestrian trajectories are linear, others very curved
Ternes, P., R. Clay, A. Heppenstall, N. Malleson. Assimilating realistic data into agent-based models in real-time with a categorical-noise particle filter step. Under Production.

Categorical-Noise PF Step

Results

Shows that some pedestrian trajectories are linear, others very curved Shows that some pedestrian trajectories are linear, others very curved
Ternes, P., R. Clay, A. Heppenstall, N. Malleson. Assimilating realistic data into agent-based models in real-time with a categorical-noise particle filter step. Under Production.

Other DA methods (i)

Unscented Kalman Filter (UKF)

Similar to the (very popular) Ensemble Kalman filter

Should be more efficient

But assumes Gaussian distributions

A few sigma points are chosen to represent the model state

Then some complicated maths happens ...

Unscented Kalman Filter (UKF)

Observe a proportion of the agents

Results of the UKF. Most agent positions are estimated reasonably well.
Clay, Robert, J. A. Ward, P. Ternes, Le-Minh Kieu, N. Malleson (2021) Real-time agent-based crowd simulation with the Reversible Jump Unscented Kalman Filter. Simulation Modelling Practice and Theory 113 (102386) DOI: 10.1016/j.simpat.2021.102386

Unscented Kalman Filter (UKF)

Observed v.s. Unobserved agents

Results of the UKF (2). For agents who we have no information about ('unobserved'), the algorithm is sometimes able to infer their behaviour from that of agents who we do have information about.
Clay, Robert, J. A. Ward, P. Ternes, Le-Minh Kieu, N. Malleson (2021) Real-time agent-based crowd simulation with the Reversible Jump Unscented Kalman Filter. Simulation Modelling Practice and Theory 113 (102386) DOI: 10.1016/j.simpat.2021.102386

Other DA methods (ii)

Monte-Carlo Markov Chain

Tang, D. and N. Malleson (2022). Data assimilation with agent-based models using Markov chain sampling. Open Research Europe 2(70). DOI: 10.12688/openreseurope.14800.1

Define an ABM using a particular scheme (similar to normal ABM definition)

New algorithm to allow efficient sampling from the ABM

Use MCMC to combine the model with data to create a posterior

Monte-Carlo Markov Chain

Posterior estimates of predators and prey

Results of the MCMC algorithm: posterior estimates of locations of predators and prey
Tang, D. and N. Malleson (2022). Data assimilation with agent-based models using Markov chain sampling. Open Research Europe 2(70). DOI: 10.12688/openreseurope.14800.1
Nature article: Make more digital twins

Conclusions

Feeding data into agent-based models is hard!

Computational and methodological challenges

Particle filters work on simple models, but naive filter breaks down

Future Work

Towards Digital Twins of Human Systems

Join up simulations at multiple spatial and temporal resolutions

Real-time analysis tools and virtual labs for policy development

Workshop on Data-Driven Economic
Agent-Based Models (DDEABM)
Sant'Anna School of Advanced Studies, Pisa, 27-28 September 2022

Data Assimilation for Agent-Based Models

Nick Malleson and Patricia Ternes

University of Leeds, UK

n.s.malleson@leeds.ac.uk

Slides available at:
https://urban-analytics.github.io/dust/presentations.html