Addressing equifinality in agent-based modeling

In the past we have blogged about the challenges of agent-based modeling but one thing we have not written much about is the challenge of uncertainty especailly when it comes to model calibration. This uncertainty is a challenge when it when it comes to situations where various parameter sets fit observed data equally well. This is known as equifinality which is a principle or phenomenon in system theory that implies that different paths can lead to the same final state or outcome. 

In a new paper with paper with Moongi Choi, Neng Wan, Simon Brewer, Thomas Cova and Alexander Hohl entitled "Addressing Equifinality in Agent-based Modeling: A Sequential Parameter Space Search Method Based on Sensitivity Analysis" we explore this issue. More specifically we introduce an Sequential Parameter Space Search (SPS) algorithm to confront the equifinality challenge in calibrating fine-scale agent-based simulations with coarse-scale observed geospatial data, ensuring accurate model selection using a pedestrian movement simulation as a test case.  

If this sounds of interest and you want to find out more, below you can read the abstract to the paper, see the logic of our simulation and some of the results. At the bottom of the page, you can find a link to the paper along with its full reference. Furthermore, Moongi has made the data and codes for indoor pedestrian movement simulation and Sequential Parameter Space search algorithm openly available at https://zenodo.org/doi/10.5281/zenodo.10815211 and https://zenodo.org/doi/10.5281/zenodo.10815195.

Abstract 

This study addresses the challenge of equifinality in agent-based modeling (ABM) by introducing a novel sequential calibration approach. Equifinality arises when multiple models equally fit observed data, risking the selection of an inaccurate model. In the context of ABM, such a situation might arise due to limitations in data, such as aggregating observations into coarse spatial units. It can lead to situations where successfully calibrated model parameters may still result in reliability issues due to uncertainties in accurately calibrating the inner mechanisms. To tackle this, we propose a method that sequentially calibrates model parameters using diverse outcomes from multiple datasets. The method aims to identify optimal parameter combinations while mitigating computational intensity. We validate our approach through indoor pedestrian movement simulation, utilizing three distinct outcomes: (1) the count of grid cells crossed by individuals, (2) the number of people in each grid cell over time (fine grid) and (3) the number of people in each grid cell over time (coarse grid). As a result, the optimal calibrated parameter combinations were selected based on high test accuracy to avoid overfitting. This method addresses equifinality while reducing computational intensity of parameter calibration for spatially explicit models, as well as ABM in general. 

Keywords: Agent-based modeling equifinality calibration sequential calibration approach sensitivity analysis.

Detail model structures and process of the simulation.

Pedestrian simulation ((a) Position by ID, Grouped proportion – (b) 0.1, (c) 0.5, (d) 0.9).

Multiple sub-observed data ((a) # grid cells passed by each individual, (b) # individuals in 1x1 grid, (c) # individuals in 2x2 grid cells).

Validation results with train and test dataset ((a) Round 1, (b) Round 2, (c) Round 3).

Full Reference: 

Choi, M., Crooks, A.T., Wan, N., Brewer, S., Cova, T.J. and Hohl, A. (2024), Addressing Equifinality in Agent-based Modeling: A Sequential Parameter Space Search Method Based on Sensitivity Analysis, International Journal of Geographical Information Science. https://doi.org/10.1080/13658816.2024.2331536. (pdf)

NetLogo Reproduction of Walk This Way

Several months ago, we posted that we had just had a paper accepted entitled "Walk this Way: Improving Pedestrian Agent-Based Models through Scene Activity Analysis. The original model was created in MASON but know it has been reproduced in NetLogo. The purpose of this exercise was to see if the model could be reproduced from the description in said paper along with the availability of the source code and data. Specifically whether there is sufficient information in the paper to reproduce the model and the results. It was an interesting exercise translating methods from MASON into NetLogo procedures (also a lot less lines of code). 

A: NetLogo Graphical User Interface (GUI), B: Original MASON GUI.

In order to really ensure this was a good reproduction it was also necessary to provide the data we compared the results to from the original model (something which is not very common in ABM publications). This way we could could see if the re-implemented model really did match the results of the original model. 

To the left, you can see the graphical user interfaces for the NetLogo model and the original model implemented in MASON.

More information about the re-implementation and the code can be found over at Yang's Blog: http://bit.ly/geospatialcss

Full Reference to the Original Paper:

Crooks, A.T., Croitoru, A., Lu, X., Wise, S., Irvine, J. and Stefanidis, A. (2015),  Walk this Way: Improving Pedestrian Agent-Based Models through Scene Activity Analysis,  ISPRS International Journal of Geo-Information, 4(3): 1627-1656. (pdf) 

Pedestrian Modeling Examples

Readers might know that we like pedestrian models here. So in keeping with the theme of NetLogo models and the use of GIS below are two simple pedestrian models. In the first model (shown in the movie below), agents just exit the room, taking the shortest path (calculated via a cost surface). The idea behind this first model is to highlight how changing the width of the exit (i.e. the door) can impact on the evacuation time (the model can be downloaded from here).

In the second model (shown in the movie below and the code is here) we show a more complicated configuration based on a floor plan that has been first converted from a CAD file to a Shapefile  before being converted into a raster where each cell is 50cm by 50cm that can then be used in the NetLogo model (coming soon there will be a bunch of tutorials on how we do this).

From CAD File (A) to Shapefile (B) to Raster (C)

In this model, agents like in the simple model above, walk to the exit. In essence, one could consider this as a fire evacuation scenario. The agents are assumed to walk to the nearest exit, analogous to following exit signage. Similar to the first example, user can explore what happens if an additional exit is added.

More information about the models (and the code) can be found over at Geospatial Computational Social Science.

Agents on Campus: A NetLogo Example

In the past I have blogged on how one can use Repast Simphony to get agents to move around a network, which also inspired a similar model in  GeoMason (see here for the movie). Keeping with this theme Yang has recently finished a NetLogo model whereby agents use an A-star algorithm to find the shortest path between two locations. The movie below shows the basic model functionality.


For more information and code click here.

Walk this Way

We recently had published in ISPRS International Journal of Geo-Information a paper entitled "Walk this Way: Improving Pedestrian Agent-Based Models through Scene Activity Analysis". In the paper we explore how new data can help inform our agent-based models. Specifically, pedestrian modeling which has been traditionally faced with the challenge of collecting data to calibrate and validate such models of pedestrian movement. Below is the abstract for the paper:

Pedestrian movement is woven into the fabric of urban regions. With more people living in cities than ever before, there is an increased need to understand and model how pedestrians utilize and move through space for a variety of applications, ranging from urban planning and architecture to security. Pedestrian modeling has been traditionally faced with the challenge of collecting data to calibrate and validate such models of pedestrian movement. With the increased availability of mobility datasets from video surveillance and enhanced geolocation capabilities in consumer mobile devices we are now presented with the opportunity to change the way we build pedestrian models. Within this paper we explore the potential that such information offers for the improvement of agent-based pedestrian models. We introduce a Scene- and Activity-Aware Agent-Based Model (SA ² -ABM), a method for harvesting scene activity information in the form of spatiotemporal trajectories, and incorporate this information into our models. In order to assess and evaluate the improvement offered by such information, we carry out a range of experiments using real-world datasets. We demonstrate that the use of real scene information allows us to better inform our model and enhance its predictive capabilities.

Keywords: pedestrian modeling; pedestrian tracking; activity monitoring; spatiotemporal trajectories; agent-based modeling

As with many of our models, the source code of the model can be downloaded from here. To give a sense of the model, the movie below shows how agents traverse the scene.

Full Reference: 

Crooks, A.T., Croitoru, A., Lu, X., Wise, S., Irvine, J. and Stefanidis, A. (2015),  Walk this Way: Improving Pedestrian Agent-Based Models through Scene Activity Analysis,  ISPRS International Journal of Geo-Information, 4(3): 1627-1656. (pdf)

Project Geppetto

Project Geppetto from Autodesk attempts to make it it easy, fast, and fun to add crowds to 3ds Max scenes. It is part of Autodesk's  "People Power" concept, where the basic idea is to try to assemble all the components one needs to create, manage, and control large crowds of characters. Specificcally it attempts to create believable motion, allow for cultural influences (Evolver) and to create a framework for thousands of characters to interact in. Below are some examples of the project.

Oxford Circus pedestrian crossing opens

Apologies for the lack of posts in recent weeks but I been busy finishing up my course about Agent-based Modeling of Urban Systems at Department of Computational Social Science at George Mason University, along with writing a few new papers.

One thing I have been meaning to blog about for a while is the opening of the Oxford Circus pedestrian crossing. Actually the crossing opened on the 2 November 2009 but its still worth blogging about. A previous post (click here) shows what the planners had in mind (Click here to read the BBC's coverage of the event).

The two movies below show what the designers had in mind using a pedestrian model created by Atkins Intelligent Space which closely matches how people are actually using the crossing (the second movie) and how at the intersection of the crossing, the density of people restricts movement.

The movie below shows what the designers had in mind:

While the second movie shows what it actually looks like and how people are using it.

More about "Oxford Circus 'X-crossing' opens", posted with vodpod

On a side note there is also a lot of work going on about how placing obstacles near exits to speed up the flow of crowds exiting large events such as rock concerts or football games (click here to read more).

Critical mass: When does a crowd become dangerous

There was an interesting article in the UKs' The Guardian a few months ago entitled "Critical mass: When does a packed but happy crowd become a dangerous, even lethal one?" which discusses as the title suggests when does a crowd become dangerous? The article starts with an incident in occurring at a Walmart's store in the US on Black Friday in 2008 where a crowd rushed into a store searching for bargains and a security guard died in the rush.

The reason I am blogging about it is that the paper sums up quite nicely and in understandable way the use of pedestrian modeling to understand such events and ways to potentially mitigate such occurrences from happening again.

One line I like is this that "in the almost weekly occurrence, somewhere in the world, of someone being injured or killed in a crowd." Other incidents for example, include the opening of the Primark flagship store in London in 2007 (below) or Jamarat bridge incident, where in 2004 more than 250 people were killed during a ritual part of the hajj known as the "stoning of the devil".

Shoppers at the opening of Primark in London tussle to get into the store (see the article).

Muslim pilgrims walk over a Jamarat bridge during the 'Jamarat' ritual, in Mina near Mecca.

The full article can be found here.

Modelling large crowds

The last few days I been reading up on pedestrian models, 3D cityscapes and the simulation of large crowds. One such paper that caught my eye was by Treuille et al. (2006) entitled Continuum Crowds. The abstract of the paper is:

"We present a real-time crowd model based on continuum dynamics. In our model, a dynamic potential field simultaneously integrates global navigation with moving obstacles such as other people, efficiently solving for the motion of large crowds without the need for explicit collision avoidance. Simulations created with our system run at interactive rates, demonstrate smooth flow under a variety of conditions, and naturally exhibit emergent phenomena that have been observed in real crowds."

The movie below shows their work:

Reference

Treuille, A., Cooper, S. and Popovic, Z. (2006), 'Continuum Crowds', in Dorsey, J. (ed.), Proceedings of ACM SIGGRAPH 2006 ACM, Boston, MA, pp. 1160-1168

Pedestrian modelling of Oxford Circus redesign

Oxford Circus in London is a busy intersection between Regent Street and Oxford Street with more than 200m visitors a year (BBC). Work is to begin on a £5m project to pedestrianise part of Oxford Circus. Based on crossings in Tokyo, the new design will stop all traffic in all directions, and allow people to cross diagonally as well as straight ahead. Street clutter and barriers at the junction of Oxford Street and Regent Street will also be removed.

Graphic showing the Oxford Circus redesign

Why blog about this? The movie below created by Designhive shows how Atkins' two-dimensional traffic and pedestrian models can be coupled with 3D Studio Max in such a way it is difficult to distinguish the model from a real piece of video footage. Combining the models in the simulation in this way makes the finished product particularly compelling. Furthermore it has the benefit of being based on the technical models developed to test the proposals prior to their implementation (such as the removal of street clutter).

The pedestrian model is a particle-based system controlling 5000 agents to match up the data produced by Atkins Intelligent Space. When the final simulation was rendered, the 'particles' were replaced with animated people, programmed to walk while the points were moving and idle when the points stopped for traffic lights.

Thanks to Duncan Smith for flagging this. Further information:

• Intelligent Space
• designhive
• BBC News Item: Oxford Circus crossing redesigned
• Building Design website news item
  
  

CASA S4 Modelling Tour Workshop

Last week CASA hosted a two day workshop showcasing our work along with researchers from the University of Leeds as part of the of the S4 European Spatial Analysis network modelling tour. Over 150 people both from the public and private sector came to the event from all across Europe. The first day of the event was designed to showcase CASA's use of new technologies for mapping and visualizing information about cities and was entitled "Geographic Information in a Web-Based World."

Talks ranged from introducing GMapCreator and MapTube which enable web-based mapping for sharing and visualising geographic information, to public engagement via the London Profiler, Public Profiler and the E-Society Classification websites. The geography and ethnicity of people's names was explored which introduced the WorldNames and Onomap websites.

Other talks on the first day explored the use of MapTube and GMapCreator for Crowdsourcing near-real time spatial surveys and understanding crowdsourced geographical information via the analysis of OpenStreetMap. On a more data oriented side, there were talks on exploring urban data collection and mapping, analysing and visualising fine scale urban form and socio-economic datasets. The day concluded with a talk by Andrew Hudson-Smith from Digital Urban on Web 2.0 and neogeography in real and virtual spaces: from geocaching through to Second Life.

The second day of the workshop was entitled "Developments in Urban Models, Simulation and Spatial Analysis" and talks ranged from: rank clocks and scaling in city sizes, geodemographics, retail modelling, the need to capture urban form patterns and processes in agent-based models, pedestrian modelling, consumer behaviour, microsimulation and 3D visualisation and communication of agent-based models.

Click here to see the full program and to download the presentations.

Work Update

Readers of the blog might have been wondering why I been interested in Second Life (click here to see blog posts on Second Life), and why I been exploring fine scale modelling of the London housing market and what this has to do with GIS and ABM. As part of the CASA seminar series, I was asked to give a talk about some of my work from the last year. The talk was entitled "Modelling Cities: An Approach using Agent-Based Models and GIS' which pulled together these topics. The abstract or the talk is below:

The Agent-based modelling (ABM) paradigm is becoming an increasingly used technique to study cities. It allows us to grow social structures in artificial worlds specifically how a set of micro-specifications are sufficient to generate the macro-phenomena of interest. Until recently many applications of agent-based models exploring urban phenomena have used a regular partition of space (cells) to represent space. While these models have provided valuable insights into urban phenomena especially as they can capture geographic detail, they miss geometric detail. This area is critical to good applications but is barely touched upon in the literature. Geometry (points, lines and polygons), forms the skeleton of cities from streets and buildings, through to parks, rivers, etc. The ability to represent the urban environment as a series of points, lines, and polygons allows for different size features such as houses and roads to be directly incorporated into the modelling process onto which other physical and social attributes can be added. Additionally the inclusion of geometry allows us to make agent-based models more realistic compared to representing the urban environment as a series of discrete regular cells. This presentation introduces ABM, explore how agent-based models coupled loosely with geographic information systems (GIS) can be created through illustrated examples focusing on residential location. These applications directly consider geometry when building these artificial worlds and running the simulations. Furthermore, these models highlight how the inclusion of geometry impacts on simulation results. Problems and challenges with this approach and ABM in general will be identified. To conclude we will argue the need for fine scale and extensive datasets of the built and socio-economic environments to ground such models, along with the need to communicate and visualise agent-based models. To this extent we introduce our detailed housing and built environment database for London, which will be used as a building block for agent-based models associated with London. We then explore how such models might be communicated and shared with others using advances in technology, specifically Web 2.0 and Second Life.

Some people have asked for the slides of the talk, so I have made them available, they can be downloaded from here (28MB). Accompanying these I have also made a movie of the talk which give a sense of dynamics from such models.



Any thoughts or comments most welcome.

New Paper: Key challenges in agent-based modelling for geo-spatial simulation

Just found out we (Christian Castle, Mike Batty and myself) have a new article inpress within Computers, Environment and Urban Systems, entitled "Key challenges in agent-based modelling for geo-spatial simulation" Below is the abstract.

Agent-based modelling (ABM) is becoming the dominant paradigm in social simulation due primarily to a worldview that suggests that complex systems emerge from the bottom-up, are highly decentralised, and are composed of a multitude of heterogeneous objects called agents. These agents act with some purpose and their interaction, usually through time and space, generates emergent order, often at higher levels than those at which such agents operate. ABM however raises as many challenges as it seeks to resolve. It is the purpose of this paper to catalogue these challenges and to illustrate them using three somewhat different agent-based models applied to city systems. The seven challenges we pose involve: the purpose for which the model is built, the extent to which the model is rooted in independent theory, the extent to which the model can be replicated, the ways the model might be verified, calibrated and validated, the way model dynamics are represented in terms of agent interactions, the extent to which the model is operational, and the way the model can be communicated and shared with others. Once catalogued, we then illustrate these challenges with a pedestrian model for emergency evacuation in central London, a hypothetical model of residential segregation model tuned to London data, and an agent-based residential location model, for Greater London. The ambiguities posed by this new style of modelling are drawn out as conclusions, and the relative arbitrariness of such modelling highlighted.

Anyone wishing to give us feedback on the article is most welcome.

Full Reference:

Crooks, A.T., Castle, C. J. E., and Batty, M. (2008), Key Challenges in Agent-Based Modelling for Geo-spatial Simulation, Computers, Environment and Urban Systems, 32(6): 417-430. (pdf)

Update: Agents in Second Life

At CASA we use Second Life as a online urban laboratory -which could be termed collaboratories, to explore issues pertaining to urban planning and public debate in a visually 3D collaborative environment (click here to see some of CASA's previous work from Digital Urban)

One of the aspects I am working on with others at CASA is exploring Second Life's potential for 3D agent-based modelling for social scientists. To this end we have created three agent-based models using the Linden Scripting Language (see Rymaszewski et al., 2007). It is the purpose of these models to act as pedagogic demonstrators and as a “proof-of-concept”, thus we have chosen Conway’s Game of Life, Schelling’s (1971, 1978) Segregation model. These models were chosen as they highlight how classical automata styles of models which have inspired a generation of modellers can be created and explored in Second Life. The third model we present is a prototype pedestrian evacuation model which is more complex than the previous two and highlights at the variety of models that can be potentially created in Second Life. This model relates to the genus of such models of which the social forces model developed and popularised by Helbing and Molnár (1995) is typical.

While being work in progress we thought its worth showing a short movie of our work to date.

The sound track for the movie is 'Just a Memory' from ANDYF.

Potentially this environment demonstrates how experts, model builders and the non specialist can view, interact and discuss agent-based models in a 3D collaborative environment. Any thoughts or comments are most welcome.

References:

Helbing, D. and Molnár, P. (1995), 'Social Force Model for Pedestrian Dynamics', Physical Review E, 51(5): 4282-4286.

Rymaszewski, M., Au, W.J., Wallace, M., Winters, C., Ondrejka, C. and Batstone-Cunningham, B. (2007), Second Life: The Official Guide, John Wiley and Sons, Inc, Hoboken, NJ.

Schelling, T.C. (1971), 'Dynamic Models of Segregation', Journal of Mathematical Sociology, 1(1): 143-186.

Schelling, T.C. (1978), Micromotives and Macrobehavior, WW Norton and Company, New York, NY.

Agent-Based Models of Crowd Behaviuor

Agent-based modelling allows us to model individuals and how these individuals interact to form emergent phenomena. A great example of this is crowds. Recently we (people at CASA) have been exploring ways to carryout pedestrian agent-based models in 3D and I just came across this short presentation by Paul Torrens entitled “Modelling Crowd Behaviour” from the O'Reilly Where 2.0 Conference. It is worth watching the talk (15min) as it shows how GIS and ABM can be coupled together and why studying crowd movement is important.

The talk can be watched here.

If you interested in pedestrian modelling and software the papers by Christian Castle might be of interest:

Castle, C.J.E. (2007), Guidelines for Assessing Pedestrian Evacuation Software Applications, Centre for Advanced Spatial Analysis (University College London): Working Paper 115, London.

Castle, C.J.E. and Longley, P.A. (2008), 'Emergency Pedestrian Evacuation Analysis: A Review and Interpretation of Software Applications', in Sui, D.Z. and Cutter, S.L. (eds.), Geospatial Technologies and Homeland Security: Research Frontiers and Challenges, Springer, Berlin.

Geocomputation 2007: Challenges in Agent-Based Modelling

Last week we attended the Geocomputation 2007 conference at the National Centre for Geocomputation at the National University of Ireland in Maynooth. We thought we would share the talk and the short paper entitled “Key Challenges in Agent-Based Modelling for Geo-Spatial Simulation.” This paper outlines some of the key challenges for ABM specifically relating it to geo-spatial simulation and how we at CASA are attempting to address these issues.

Any thoughts or comments would be more than welcome.

Click here to download the paper and here for the presentation.

Full Reference:

Crooks, A. T., Castle, C. J. E., and Batty, M. (2007), Key Challenges in Agent-Based Modelling for Geo-spatial Simulation, in Demšar, U (ed.), Proceedings of the 9th International Conference on Geocomputation, National Centre for Geocomputation, National University of Ireland, Maynooth, Ireland. (pdf)

ped-net.org

ped-net.org is a new site to help people who are interested in the field of pedestrian and evacuation dynamics. The site provides a comprehensive list of literature and links to models pertaining to pedestrian modelling, forthcoming conferences, a bulletin board and a series of java applets.

If you interested in this sort of thing, its worth having a look at the site: http://www.ped-net.org/

Guidelines for Assessing Pedestrian Evacuation Software Applications

Christian Castle has just finished a comprehensive working paper entitled “Guidelines for Assessing Pedestrian Evacuation Software Applications, ” which might be of interest to readers of this blog. His abstract for this is written below:

“This paper serves to clearly identify and explain criteria to consider when evaluating the suitability of a pedestrian evacuation software application to assess the evacuation process of a building. Guidelines in the form of nine topic areas identify different modelling approaches adopted, as well as features / functionality provided by applications designed specifically for simulating the egress of pedestrians from inside a building. The paper concludes with a synopsis of these guidelines, identifying key questions (by topic area) to found an evaluation”.

Key Words: Pedestrian evacuation, software applications, models, modelling, buildings, egress, simulation, guidelines, evaluation criteria, pedestrian movement and behaviour.

The paper can be downloaded from CASA: click here

In relation to this paper Christian also gave a presentation at CASA entitled "King’s Cross Under -ground Station Pedestrian Evacuation Model" outlining his research specifically how the criteria from the working paper above can be used, types of spaces that can be used to develop models and how agents move in space.


The talk slides can be downloaded by clicking here.