Structure of Mercurial: a crowd simulation framework

To support my research in crowd dynamics models, I am developing a simulation framework: Mercurial. The aim is to simplify the testing of new models and see how they perform in different scenarios. At this stage, the framework is still a prototype, but I try to keep it as accessible and maintainable as possible.

Mercurial is written in Python 3. This makes for rapid prototyping, but can become a computational burden if not designed with caution. Therefore, almost all intensive computations are vectorised using the NumPy library or are deferred to a lower level implementation in Fortran.

In the rest of this post I describe the structure of the simulation. Information on how to install and use it can be found here.

API

The code is designed with separation of interface and implementation in mind. Simulations are created by calling the Mercurial API, built to enable potential integration in a larger framework. For example, a simulation can be created with the following lines.

from mercurial import Simulation
# Load the environment
sim = Simulation('env.png')
# Add 100 pedestrians
sim.add_pedestrians(100)
# Start the simulation
sim.start()

The Simulation object exposes several functions that add or modify simulation features, called ‘effects’. For example, one can add 300 pedestrians with a flocking behaviour by sim.add_pedestrians(300,'following'). Interaction effects can be added with the line sim.add_local('repulsion'). A list with all effects is supplied further down this page.

Configuration

All parameters relevant to the simulation (e.g. size of simulation environment, simulation step size and maximum pedestrian speed) are collected in one class called Parameters (in src/params.py). At the beginning of a simulation, one instance is created and passed to the other modules. As a result, parameters can be freely modified in the period between the initialisation and the start of the simulation, and flexible parameters even at runtime.

Modifying parameters is possible by creating a Parameters instance in the simulation file, and assigning the desired values to the corresponding attribute. For instance:

from mercurial import Simulation
from params import Parameters

# Load the environment
sim = Simulation('env.png')
# Add 100 pedestrians
sim.add_pedestrians(100)
# Create new Parameters object
parameters = Parameters()
# Change time step size
parameters.dt = 0.32
# Add parameters object to simulation
sim.set_params(parameters)
# Change density
parameters.min_density = 10
# Start the simulation
sim.start()

If you want to extend Mercurial, you can add your own parameters to the Parameters class to make them available to the rest of the simulation.

Modular

Mercurial is built up from different modules. If the API does not contain enough features (which it does not at the time of writing), new features can be added by writing new modules and integrating them into the framework.

The aim is that new modules can augment the simulation without interfering with the old ones, or improve upon and replace old modules.

The current modules fall in three categories: populations, effects, visualisations and post-processing: more information follows below.

Scene object

The result of the computations are processed in the Scene: an object that represents the environment in which the simulation takes place and contains the pedestrians. This Scene has a representation of this environment (together with entrances, obstacles and exits) as well as the position, velocity and other properties of the pedestrians.

The environment is stored as an image in PNG format. One such image is displayed below.

This image is a spatial representation of the environment, with accessible areas in red, exits in green, obstacles in black and less accessible (and preferably avoided space) in grey.

Before start of the simulation, the Scene computes a route planner from each position in the environment to the exit. It does so by applying a weighted distance transform to the image using Python’s image processing library PIL. It uses the same information to determine from which locations no exit can be reached.

In addition, the Scene takes care of moving the pedestrians, ensuring they do not run into obstacles, and that they are removed once they reach the exit. It does so by keeping track of all pedestrians in large arrays. The positions and velocities of all n pedestrians are stored contiguously in two (n,2) NumPy arrays, allowing for fast updating of positions and velocities.

Populations

New pedestrians are added in groups called Populations. A Population class imposes a certain behaviour on its pedestrian members, which can be used to model different types of evacuation scenarios, or interaction between different types of people.

At the time of writing, Mercurial supports two types of behaviours: Following, which represents a population of people that adjusts its position and velocity to the people around them, and Knowing, which represents a population of people that knows the environment by heart, and knows the fastest way to the exit from any location.

Other Populations can be implemented by extending the Population class in src/populations/base.py.

Under the hood, a Population is a wrapper class around a list of indices, which indicates which entries of the position and velocity arrays belong to the population. This list is used to slice the global arrays and manipulate only the slice.

Effects

At the time of writing, Mercurial supports the following effects:

• Fire and smoke
• Repulsion on microscopic level (minimum distance enforcement)
• Repulsion on macroscopic level (pressure enforcement)

Fire

Fire is represented as a point source. It has a location and a radius which represents its intensity. It exerts a repelling effect on the pedestrian by adjusting their velocities with a force inversely proportional to their distance to the source.

The location of the fire is not necessarily inaccessible, and if present, greater forces can direct pedestrians into that location. The effects of fire (either discomfort or perhaps exposure to the flames) can be measured for each pedestrian as a function of time.

Additionally, Fire serves as a source for the creation of smoke, described below.

Smoke

Smoke is modelled as a continuous quantity. It is prescribed by a convection-diffusion equation.

This partial differential equation is solved every time step to compute the evolution of the smoke as a function of the fire, wind, and the environment.

Smoke reduces the sight radius of the pedestrians, as well as their walking speed. Only the Following population is affected by the lack of sight, since the Knowing population know the environment by heart.

This means that over time, the larger part of the environment only experiences an increasing amount of smoke. Movement through the environment becomes increasingly difficult. If this is undesired, the smoke creation can be suppressed.

Currently, Fire is implemented as a stationary process. However, the module can be improved to account for expanding or moving fire zones without breaking the link to the smoke module.

Local repulsion

One way to model the interaction between pedestrians (read: collision avoidance), is simply to separate them when they move to close to each other. This is called a minimum distance enforcement. It is not a very subtle way of prescribing interaction, but it performs quite well for small time steps. Especially when using a smart route planner, this module can take care of some visual artefacts without any big changes to the planning algorithm.

Global repulsion

A second way to model interaction is to evaluate a measure of crowdedness at the global level. By interpolating the particle positions to crowd densities, we can compute a global repulsion that ensures pedestrians do not move into dense zones. More information on this procedure can be found here, in the section Macroscopic Formulation. This provides smoother motions and has a relatively low computational cost.

Best (visual) results are booked by combining the repulsion methods. This enables the global repulsion module to avoid most collisions, leaving a minimum of work for the local repulsion algorithm.

Composition

Each module has three main components: a initialisation function (__init__, called when creating the object), a setup function (prepare, called upon start of the simulation) and an iteration function (step, called on every time step).

• The __init__ function creates all class members that the module uses. All parameter-dependent attributes are set to None however, because at the time of module initialisation, not all parameters are fixed yet. Still, to satisfy PEP guidelines and make the code more comprehensible, all attributes are created here.

• The prepare function loads all required parameters into the module. It also performs all preprocessing required for the simulation: building the route planner, creating the data arrays, etcetera. It is also responsible for collecting the step functions for each module.

• The step function contains all functions that need to be called each time step. They are collected in a list on_step_functions. By collecting this list at preparation, we avoid the need of extensively building and going through lengthy if-else constructs at run-time.

Visualisation

The implemented visualisation is rather simple and built on the tkinter backend, by default available in Python. Using the PIL library we display the PNG on the simulation screen. Additionally, we are able to update every time step by redrawing all pedestrians.

If requested, Mercurial runs without visualisation, improving simulation speed significantly. This might be preferable if you are just interested in some metrics.

It would be nice to decouple the visualisation from the simulation kernel, so that both processes can run on different threads. Perhaps this could be implemented later.

Post-processing

Mercurial has two modules that log results. They are turned off by default, but can be enabled with through the API.

The first one, src/processing/log_results.py, takes all quantitative data from the simulation (microscopic attributes like pedestrian positions and velocities as well as macroscopic attributes like crowd density, crowd velocity and crowd pressure) and stores it in HDF5 format. This is a cross-platform file format that is optimised for reading and writing large structured datasets. It can be used to post-process in a myriad of different visualisation tools.

The second result logging tool, src/processing/show_results.py, stores the data in a Numpy/MatLab-compliant format. It is mainly meant for either the simple post-processing tool in display_results.py, which creates some plots and graphs displaying simulation results, or for manual post-processing.

Fortran modules

As mentioned above, some intensive computations are deferred to Fortran modules. These modules have been compiled with f2py so they can be called directly as Python libraries. They play well with NumPy arrays, greatly reducing any conversion overhead.

In general: all intensive computations that are difficult or impossible to express in vectorised form are implemented in Fortran. This includes the following routines:

• Velocity averaging (computing the trajectories for the Following population)
• Weighted distance transform (computing the route planner for the Knowing population)
• Smoke propagation (solve the smoke equation numerically with a simple iterative algorithm)
• Macroscopic quantity interpolation (compute global density, velocity and pressure)
• Minimal distance enforcing (separate pedestrians to satisfy the minimum distance constraints)

All Fortran source codes are collected in the folder src/fortran. Apart from the modules mentioned, it has some routines for representing sparse matrices and heap queues.

Building and compiling of these modules is taken care of by the distutils package. If you want to add new Fortran modules, list them in setup.py, and they will become available after running python3 setup.py install.