Agent-to-Agent Interactions in Agent-Based Models
Understanding and leveraging the interaction graph
Fred is a data scientist at Arup working on machine learning and city modelling
In this post, we take a look at agent-to-agent interactions in agent-based models. We explain what we mean by agent-to-agent interaction, and introduce agent-to-agent interaction graphs. These graphs reveal social network-like structures in our simulations, helping us tackle challenges such as delay attribution modelling, and better ways to subset our simulations.
Agent-to-agent interactions
Our simulations model many realistic agent interactions. We can simulate the interaction of agents with their environment, such as agents leaving their houses, traversing the transport network, waiting for services or entering vehicles. Through these actions, we traditionally simulate travel congestion or journey times. But we can also simulate agent-to-agent interaction.
In Figure 1, we have a simplistic illustration of what agent-to-agent interactions mean. We know that agents might share the same facilities, for example living together in the same home or working at the same office. And we can consider more discretionary, temporally dependent interactions, like being in a shop at the same time:
In addition to sharing facilities (like homes, workplaces and shops), agents share spaces for travelling. In this article, we will focus on two types of agent-agent travelling interactions; (i) agents waiting together at an interchange, like a bus stop, and (ii) agents travelling together in the same transit vehicle. However, these same ideas are extendible to all kinds of potential connections, from using the same taxi driver to passing in the street.
Figure 2 shows how these interactions emerge from agent activity plans — the three example agents in Figure 2 do not live or work together — but all potentially meet as they go about their day. Agents A and B both wait at the same bus stop and agents B and C are both on the same bus for part of their journeys.
Interaction Networks/Graphs
Above we have described the type of agent-to-agent interactions we can simulate. When we scale our models to simulate millions of agents using the same transport networks, this leads to a large number of interactions. Much like the social concept of six degrees of separation — but for transport — we find that people from far apart can be linked together based on their transportation and activity choices.
We can build very large graphs to represent the interactions of millions of agents in our models. These are not dissimilar to big social networks, like Twitter or GoT. But first, we’ll start small…
Introducing Agent A
First, let’s consider the outputs of a small fictional simulation of London. In particular, we consider Agent A:
Agent A is an important agent in this mini-simulation — it interacts with more agents than any other agent. Analysis of attributes and logs reveals that Agent A represents a retired woman, with a driving license (but no car), who makes a single trip to the shops and back at around mid-day by bus. Her bus trip (from Canning Town to Stratford) is about 30 minutes each way. While on her trip, she shares the bus with 10 other people. Five on the outbound trip and five on the return trip.
The agents who shared a bus with Agent A also experienced interactions with other new agents and those agents that interacted with other new agents and so on. The first interactions with Agent A were on the same two buses, but as the network extends, interactions of other agents can occur on new journey stages. The representation of all these interactions looks like this:
In our toy simulation, Agent A’s extended network now reaches 25 unique agents. This network is made up of agents with up to three degrees of separation from Agent A (so two intermediate agent interactions). The agents in this network become quite diverse, with varying plans and demographics.
When we look at the home and or destination locations of Agent A’s network in Figures 6 or 7, we can see the interaction network is pretty big — extending to the east, north and west.
Our simulations have loads of these interaction graphs, revealing micro interactions and patterns. Figure 8 shows a few sample examples of the differences in agent-connections, based on different interaction scenarios. Examples (iii) and (v) are fully connected — every agent has a link with every other agent. Example (iv) has two groups, one on train and one on bus, linked by a single agent who used both. As in (ii) agents with similar income levels are often clustered together.
Network Metadata
In these networks, each node contains details about the agent, and the edges can carry information about the interaction. The type of interaction can be included on links, for example, the mode, location or situation. We can also consider the time of the interaction and the status of the service, like the level of crowding on a bus or if there was seating available on a train.
We can extend the types of interaction to new mechanisms and agents. Agents can meet on the street or in vehicles. Interactions can be physical, like sharing transit stations or queuing for a bus, or statistical, like the potential for physical or even eye contact.
Applications
When we scale simulations to be more representative of reality we can put these interaction networks to use. Before dipping into the most obvious application (disease transmission modelling), we first suggest their use for social analysis, delay attribution and simulation subsetting. We describe each of these in more detail below.
Social Analysis
When we originally built these networks, we were considering the way people are connected — or sometimes not connected. Figure 9, for example, shows the home location of London rail passengers and the links between them, based on shared rail journeys. The largest fully connected subgraph for this network has 10,000 agents and the smallest just 7.
Furthermore, some people don’t participate in these networks at all, either through geography or choices.
Delay Attribution
UK train operating companies are generally very keen to attribute (to others) delays that occur on their (shared) infrastructure. But in a complex system like a big busy rail network, the original cause of a delay can traverse across a network in unexpected ways. A one-minute delay for a single train in the morning may cascade through a number of interactions and result in a severely delayed commuter train somewhere else on the network in the evening.
Interaction graphs offer a comprehensive methodology for revealing these causations if the right interactions can be measured. More generally these graphs offer a methodology for investigating and debugging issues in complex scenarios like our simulations. This makes more feasible careful and efficient micro-interventions for big problems like congestion or crowding.
Model Subsetting
Sometimes we want to subset a simulation to a smaller area. We do this often when building models to save on compute costs and time. A traditional approach to this is to define a geographic (and/or temporal) buffer and then remove agents and network links outside this boundary. But this approach is flawed for two reasons:
i) Some agents and some network may exist within the buffer but not influence the scenario you are interested in. (For example: an agent that doesn’t leave the area)
ii) Some agents and some network links may exist outside (perhaps very far outside) the buffer but still influence the scenario you are interested in. (For example: an agent that travels through the area.)
Defining interactions of interest and appropriate buffer distances through an interaction graph provides a more rigorous methodology of subsetting. Important interactions from geographically or temporally distant agents and networks can be identified and maintained. Types of interaction and distance through the graph can be used to tweak the trade-off between quality and compute.
Disease Transmission Modelling
We are not disease or health specialists but we note the likely importance of travel as a mechanism for transmission of infectious diseases. Measured interactions do not have to be just social or work related, they can also occur while travelling. Transport ABMs offer two big avenues for potentially better modelling of disease transmission:
i) Detailed Transport Mechanisms — detailed modelling of physical interactions while travelling, for example, risk of transmission based on the types of transport, the crowding level, durations, sitting or standing and waiting times.
ii) Detailed Modelling of Travelling Agents — detailed modelling of interactions between representative agents, modelling the heterogeneity of risk to different populations more accurately.
Combining the spatial and temporal precision of transport ABMs with interaction graphs could be a powerful new tool against disease. ABMs allow the more careful consideration of potential interventions, such as schedule reductions and closures. They also make feasible micro-interventions - revealing groups, areas or times of day where risk is highest and where interventions should be prioritised.
Work is already ongoing to this end. In particular, we direct those interested to the fantastic Episim project and working paper.
