EF4 – Particles and Agents

Project

EF4-3

Learning Reduced Models for Large-Scale Mobility ABMs

Project Heads

Carlo Jaeger, Stefan Klus, Christof Schütte, Sarah Wolf

Project Members

Jan-Hendrik Niemann (ZIB) 

Project Duration

01.01.2019 – 31.12.2021

Located at

ZIB

Description

Agent-based models (ABMs) are easily explainable and powerful tools to simulate complex dynamical behavior emerging in social systems. The simulation of such models however, is often being time-consuming and hard to analyze due to their high-dimensionality.  The aim of this project is to obtain simpler, coarse-grained representations from black box data of the real dynamical systems of a large-scale agent-based models. The reduced models help with validation, parameter optimization, sensitivity analysis and more.

Data-driven methods based on transfer operators can be used for tasks such as metastability analysis, system identification or model reduction.  The Koopman operator theory provides a framework to describe the relationship between the evolution of observables (e.g. any kind of measurement) and the evolution of state. In [1], we developed an extension of the classical EDMD (extended dynamic mode decomposition) algorithm to approximate the infinitesimal generator of the Koopman operator from data. The novel framework called gEDMD can be applied not only to deterministic but also non-deterministic dynamical systems. Similarly to EDMD and related algorithms, it also allows a decomposition into eigenfunctions, eigenvalues and modes, which then can be used for system identification, model reduction or the discovery of conservation laws.

In [2], studied the metastable behavior of ABMs with very large numbers of agents or long time scales or both. Understanding metastability can be of interest for many applications, e.g., to mitigate or prevent disasters or to initiate changes. A dynamical system is said to be in a metastable state when it is in an apparently stable state, although the system can transition to another (apparently) stable state. Therefore, we studied agent-based models given as continuous-time Markov jump process and their path wise approximations by stochastic differential equations (SDEs). We showed that the transfer operator approach bridges the gap between the pathwise results for large populations, i.e., the SDE approximation, and approaches built to study dynamical behavior on long time scales. The main insights are that the transfer operator approach allows to uncover metastable structures and long time scales associated with rare events for either the considered agent-based model or the SDE processes by means of (many) finite-length trajectories of the corresponding process. For large enough numbers of agents, the metastable structures detected by the transfer operator approach of the agent-based model and SDE process are very close. This implies that the characteristics of the long-term behavior of the agent-based model process can be determined by simulating (many) short trajectories of the SDE process instead. As a consequence, the computational costs can be reduced as simulating the SDE is essentially not dependent on the number of agents. We illustrated our results using the well-known voter ABM.

Building on [1, 2], we then showed how the Koopman generator can be used to obtain data-driven reduced models represented as ODEs or SDEs from aggregate state variables of agent-based systems. Aggregate state variables can represent quantities such as the number of agents sharing the same opinions, the number of predators and prey, or other summarized quantities. The difficulty here is that data is often (highly) noisy and not provided by an idealized benchmark problem. We demonstrated the techniques using agent-based models of different complexity such as the voter model, a spatially-explicit predator-prey model with non-constant number of agents, and a spatially-explicit civil violence model with heterogeneous agents, see Figures (A-F). For a successful identification of a reduced model from data, we require accurate, pointwise estimates of the drift and diffusion terms. One pitfall is the dependence of the ABM state on the spatial structures, e.g., clustering, coexistence or spatial heterogeneity, which must be taken into consideration. For example, in [4], it was demonstrated that heterogeneity of the interaction network connecting the agents can be handled by introducing memory into the reduced model. More precisely, a new method, SINAR (sparse identification of autoregressive models), an extension of the well-known SINDy method, is proposed that permits to estimate an SDE with memory from ABM simulation data and allows to tackle systems with loosely clustered interaction networks. Heterogeneity in space has been taken account for in [5], where we discussed how to aggregate an ABM spatially into a discrete Master equation by Galerkin projection to an appropriate ansatz space. We showed that the resulting reduced models are good agreement with existing limit models in case of existence and furthermore allow for qualitative forecasts also in the case when no underlying limit process is known. We refer the reader to [3] for further details. The code for simulating the agent-based model used in [3] is available at GitHub.

Lastly, we demonstrated that the reduced models can serve as surrogate in multi-objective optimization of agent-based system. 

J.-H. Niemann submitted his Ph. D. thesis in February 2022.

Project Webpages

Selected Publications

  1. S. Klus, F. Nüske, S. Peitz, J.-H. Niemann, C. Clementi, and C. Schütte. Data-driven approximation of the Koopman generator: Model reduction, system identification, and control. Physica D: Nonlinear Phenomena, 406:132416, 2020. (Physica D)
  2. J.-H. Niemann, S. Winkelmann, S. Wolf, and C. Schütte. Agent-based modeling: Population limits and large timescales. Chaos: An Interdisciplinary Journal of Nonlinear Science, 31 (3), 2021. (Chaos)
  3. J.-H. Niemann, S. Klus, and C. Schütte. Data-driven model reduction of agent-based systems using the Koopman generator. Plos One, 16 (5), 2020. (PLoS One)
  4. N. Wulkow, P. Koltai and C. Schütte. Memory-Based Reduced Modelling and Data-Based Estimation of Opinion Spreading, 31 (1), 2020. (J. Nonlinear Sci.)
  5. S. Winkelmann, J. Zonker, C. Schütte and N. Djurdjevac Conrad. Mathematical modeling of spatio-temporal population dynamics and application to epidemic spreading. Mathematical Biosciences, 336:108619, 2021. (Math Biosci)

Selected Pictures

Figure (A) shows the state space of a predator-prey ABM, where red and green dots represent predators and prey, respectively. The radius of vision, i.e., the range within a predator can hunt for prey, is indicated by the red-shaded area around the predators. Figures (B) and (C) show the expected phase portraits of the predator-prey ABM and corresponding reduced model. Figure (D) shows the state space of a civil violence ABM, where red and green dots represent rebellious and peaceful agents, respectively. Blue dots mark law enforcement officers. Figures (E) and (F) show the temporal evolution of the ABM and the reduced model. For further details see [3].

Please insert any kind of pictures (photos, diagramms, simulations, graphics) related to the project in the above right field (Image with Text), by choosing the green plus image on top of the text editor. (You will be directed to the media library where you can add new files.)
(We need pictures for a lot of purposes in different contexts, like posters, scientific reports, flyers, website,…
Please upload pictures that might be just nice to look at, illustrate, explain or summarize your work.)

As Title in the above form please add a copyright.

And please give a short description of the picture and the context in the above textbox.

Don’t forget to press the “Save changes” button at the bottom of the box.

If you want to add more pictures, please use the “clone”-button at the right top of the above grey box.