Agent-Based Mobility Simulation for Synthetic Trajectories

Agent-based mobility simulation builds a synthetic city one traveller at a time: each agent carries a daily activity schedule, chooses routes over a real or generated network, steers around obstacles and other agents, and emits a timestamped trajectory that — in aggregate — reproduces the flows, congestion, and dwell patterns of a real population without exposing a single real person. This page is part of Trajectory & Movement Simulation: where Markov chain routing models generate a single plausible path from transition probabilities and physics-based path generation enforces the dynamics of one moving body, agent-based simulation is the layer that runs thousands of those individual movers together under shared schedules and a shared space, so their interactions — queueing, avoidance, congestion — emerge rather than being scripted. The engineering challenge is that “thousands of movers in a shared space” is where naive implementations quadruple in cost, deadlock, or drift out of reproducibility.

The agent-based mobility simulation loop, from population synthesis to trajectory output A population synthesizer generates a set of agents, each given an activity schedule of timed destinations. A simulation tick runs three coupled stages in sequence. First, activity selection reads the schedule and sets the agent's current goal. Second, a routing layer plans a network-constrained path to that goal. Third, a steering-and-collision layer advances the agent along the path while avoiding other agents, using a spatial index to keep neighbor lookups bounded rather than comparing every pair. Moved agents write a timestamped sample to the trajectory sink and their new state feeds back into the next tick, so congestion and queueing emerge from the interaction of many agents rather than being scripted. Population synthesizer agents + schedules Per-tick loop 1 · Activity selection read schedule set current goal 2 · Routing network path plan shortest / stochastic 3 · Steer & avoid advance along path collision avoidance Spatial index bounded neighbor query Trajectory sink timestamped samples next tick — new state
Each tick couples activity selection, routing, and steering; congestion emerges from the shared space.

Problem Framing: When a Population Stops Behaving Like One

A single synthetic trajectory is easy — sample an origin and destination, route the shortest path, add motion. The failure this page addresses appears only at population scale, when the agents share a space and a clock:

Per-step interaction cost against agent count for all-pairs and spatial-hash queries Both axes are logarithmic. The horizontal axis is the number of simulated agents, from five hundred to one hundred and twenty-eight thousand, with density held constant so the simulated area grows with the population. The vertical axis is the wall-clock cost of one interaction step in seconds. The all-pairs curve has slope two: every agent is tested against every other, so doubling the population quadruples the work, and it crosses a dashed budget line for a twenty-hertz simulation in the low thousands of agents. The spatial-hash curve has slope one: each agent tests only the agents in its own and its eight neighbouring cells, and because the density is fixed that number does not grow with the population, so the cost per agent is constant and the total is linear. It stays under budget across the entire range. The crossing points are marked with the maximum affordable population under each approach. The note underneath adds the qualification that matters: the linear result depends on density being constant, and a simulation that concentrates agents — a stadium exit, a platform at a train arrival — pushes many agents into one cell and recovers the quadratic behaviour locally, which is what a hierarchical structure exists to fix. Constant density is doing more work in that claim than the data structure 501 2k 8k 32k 126k 0.00001 0.0001 0.001 0.01 0.1 1 10 100 agents (log scale, density held constant) cost per simulation step (s, log scale) 20 Hz step budget all-pairs runs out at ≈2,000 agents spatial hash runs out at ≈64,000 agents all-pairs interaction spatial-hash neighbourhood Interaction radius 6 m at 0.004 agents/m², 40 ns per pair test. The linear result depends on density staying constant — a stadium exit or a platform at a train arrival pushes many agents into one cell and recovers quadratic behaviour locally, which is what a hierarchical structure exists to fix.
The linear result depends on density staying constant — a stadium exit recovers quadratic behaviour locally.
  • The quadratic wall. A naive collision check compares every agent against every other agent each tick. At ten thousand agents that is a hundred million distance computations per step, and the simulation slows from real-time to a slideshow. The cost grows as the square of population while the useful interactions grow only linearly.
  • Deadlock and jitter. Agents in a corridor freeze facing each other, or oscillate left-right forever, because the avoidance rule has no tie-breaker and no notion of intent. The trajectories look plausible in isolation and absurd in aggregate.
  • Schedule incoherence. Agents arrive at a workplace at 3 a.m. or make a forty-minute trip in the two-minute gap between activities, because the activity generator and the router were never reconciled against a shared wall clock. The resulting flows have peaks in the wrong places.
  • Non-reproducible populations. Iterate agents from a Python dict, or seed each agent from wall-clock time, and two runs of the “same” scenario produce different populations and different congestion. Any regression test on flow volumes becomes noise.

These are not bugs in any one agent; they are properties of the interaction between agents, the schedule, and the network. Getting them right needs the same explicitness the rest of the stack demands — a seeded RNG, a bounded neighbour query, a reconciled clock — plus a collision model that resolves rather than merely detects. The dedicated drill-down on preventing agent collisions in crowd simulation treats the resolution rule in depth; this page builds the loop it plugs into.

Prerequisites & Toolchain

Agent-based mobility sits on the geospatial core plus a graph library for the network and a spatial index for neighbour queries. Pin majors so routing weights and geometry predicates stay stable:

python >= 3.10
numpy == 1.26.*
scipy == 1.11.*         # cKDTree for bounded neighbor queries
geopandas == 0.14.*
shapely == 2.*          # GEOS 3.11+ geometry, snapping
pyproj == 3.*
networkx                # network graph + shortest-path routing (major pin)

Two environment decisions dominate correctness. First, simulate in a metric CRS. Steering forces, speeds, agent radii, and collision distances are all lengths; computing them in EPSG:4326 degrees makes every threshold latitude-dependent and the physics wrong. Reproject the network and all agent state to a metric or equal-area CRS (a UTM zone regionally, EPSG:6933 globally) before the loop runs, the same rule the physics-based path generation stage relies on. Second, fix a single simulation timestep and a single master clock. Every agent advances by the same Δt, and every timestamp derives from tick * dt added to a scenario start time — never from datetime.now() — so the output can be reconciled by the temporal synchronization for moving objects stage without clock-skew artifacts.

Core Concept: Schedules, Steering, and the Shared Space

An agent-based mobility model is three coupled subsystems, and the realism of the output depends on all three being consistent with each other.

Four calibration targets for an agent model, in the order they constrain it Four targets, calibrated in sequence, because each one leaves the previous one unchanged and none of them can be fitted before the one above it. First, trip counts: the total number of journeys per period identifies the agent population and its activity rate, needs only aggregate counts, and has to come first because every later target is conditional on how many agents exist. Second, origin-destination flows: the matrix of journeys between zones identifies the destination-choice model, needs a survey or an aggregate flow matrix, and has to follow the counts because a flow matrix is only meaningful given a total. Third, the temporal profile: the distribution of departure times identifies the activity scheduler, needs time-stamped counts, and has to follow the flows because departure timing is conditional on the trip that is being made. Fourth, interaction statistics: queue lengths, delay under load and observed density identify the interaction parameters — following distance, reaction time, conflict-resolution aggressiveness — need observations under congestion specifically, and must come last because they are only identifiable once the demand that produces congestion is already right. A closing note records the failure that comes from reordering: interaction parameters fitted before the demand is calibrated will absorb the demand error, producing a model that reproduces observed delay with the wrong agents doing the wrong things. Each target is only identifiable once the one above it is right Target identifies needs why it cannot move earlier trip counts population and activity rate aggregate counts per period everything later is conditional on it OD flows the destination-choice model a survey or flow matrix a flow matrix needs a total temporal profile the activity scheduler time-stamped counts timing is conditional on the trip interaction statistics following distance, reaction, aggression observations under congestion identifiable only once demand is right Reorder it and the interaction parameters absorb the demand error: the model reproduces observed delay with the wrong number of agents doing the wrong things, which validates beautifully and generalises to nothing. The tell is an interaction parameter that has been fitted far outside its physically plausible range.
Each target is only identifiable once the one above it is right; reorder it and the interaction parameters absorb the demand error.

Activity scheduling gives each agent a reason to move. Rather than random origin-destination pairs, each synthetic agent carries a day plan — home, commute, work, errand, return — with timed transitions drawn from an activity distribution conditioned on agent type. This is what puts the morning peak in the right place: a population of scheduled agents produces temporal flow structure that random trips never do. The schedule is a sequence of (activity, location, earliest_start, duration) tuples, and the simulation’s job is to route the agent between consecutive locations so it arrives plausibly on time.

Steering behaviours move the agent along its planned route as a continuous body rather than teleporting it node to node. The classic decomposition — seek the next waypoint, arrive by decelerating into it, separate from close neighbours, avoid obstacles — sums a set of steering forces into an acceleration, which integrates into velocity and position under speed and acceleration caps. Because the forces are continuous, the emergent motion is smooth and the trajectory is differentiable, which matters when the output later has GPS noise added by the noise injection and stochastic drift stage: you want the clean path to be physically plausible before noise, not after.

The shared space is where interaction happens and where cost explodes. Every agent’s separate and avoid forces depend on its current neighbours, and finding those neighbours naively is the quadratic wall. The fix is a spatial index — a k-d tree or uniform grid rebuilt each tick — that answers “who is within radius r of this agent” in roughly logarithmic time, turning the per-tick cost from O(n²) to O(n log n). Routing over the network is the third leg: agents plan paths over a graph (shortest-path, or a stochastic variant that spreads load), and the routing choice is where you decide whether congestion is modelled as a static edge weight or fed back dynamically from current agent density. A first-order routing model — choosing the next edge from transition probabilities rather than a global plan — connects this layer directly to the Markov chain routing models technique.

Step-by-Step Implementation

The simulation runs as a tick loop over a synthesized population. Each block assumes the pinned toolchain and a metric CRS.

Step 1 — Synthesize the population deterministically. Build agents from an explicit integer seed so the same scenario always yields the same population. Each agent gets a type, a home location, and a schedule.

python
import numpy as np
from dataclasses import dataclass, field

@dataclass
class Agent:
    aid: int
    pos: np.ndarray            # (x, y) in metres
    vel: np.ndarray
    schedule: list             # [(activity, xy, earliest_start_s, duration_s), ...]
    goal_idx: int = 0

def synthesize_population(n: int, homes: np.ndarray, seed: int) -> list[Agent]:
    rng = np.random.default_rng(seed)              # PCG64; reproducible population
    agents = []
    for aid in range(n):
        home = homes[rng.integers(len(homes))]
        # a minimal home -> work -> home schedule with jittered timings
        work = home + rng.normal(0, 3000, size=2)  # metres
        start = 7 * 3600 + rng.normal(0, 1800)     # ~07:00 with 30-min spread
        sched = [("work", work, start, 8 * 3600),
                 ("home", home, start + 8 * 3600, 0)]
        agents.append(Agent(aid, home.astype(float), np.zeros(2), sched))
    return agents

Step 2 — Plan a network route per active goal. When an agent’s current activity window opens, route it over the network graph to the goal. Cache the path so the plan is computed once per goal, not per tick.

python
import networkx as nx

def plan_route(graph: nx.Graph, src_node: int, dst_node: int) -> list[int]:
    # weight="travel_time" precomputed on each edge from length / free-flow speed
    return nx.shortest_path(graph, src_node, dst_node, weight="travel_time")

Step 3 — Compute steering forces against bounded neighbours. Build a k-d tree once per tick, query each agent’s neighbours within an interaction radius, and sum seek, separation, and avoidance into an acceleration.

python
from scipy.spatial import cKDTree

def step_forces(agents, waypoints, radius=8.0, max_acc=1.5):
    pos = np.array([a.pos for a in agents])
    tree = cKDTree(pos)                             # rebuilt each tick: O(n log n)
    acc = np.zeros_like(pos)
    for i, a in enumerate(agents):
        seek = waypoints[i] - a.pos                 # toward next waypoint
        seek /= (np.linalg.norm(seek) + 1e-9)
        # neighbours within interaction radius, excluding self
        idx = tree.query_ball_point(a.pos, radius)
        sep = np.zeros(2)
        for j in idx:
            if j == i:
                continue
            offset = a.pos - pos[j]
            d = np.linalg.norm(offset) + 1e-9
            sep += offset / d**2                    # inverse-square separation
        force = seek + 1.5 * sep
        norm = np.linalg.norm(force)
        acc[i] = force / norm * max_acc if norm > max_acc else force
    return acc

Step 4 — Integrate motion under caps and emit samples. Advance velocity and position by the fixed Δt, clamp to a maximum speed, and write a timestamped sample keyed on tick * dt.

python
def integrate(agents, acc, dt, t0_s, tick, max_speed=1.4, sink=None):
    ts = t0_s + tick * dt                           # master clock, never wall-clock
    for i, a in enumerate(agents):
        a.vel = a.vel + acc[i] * dt
        speed = np.linalg.norm(a.vel)
        if speed > max_speed:
            a.vel *= max_speed / speed              # pedestrian speed cap
        a.pos = a.pos + a.vel * dt
        if sink is not None:
            sink.append((a.aid, ts, float(a.pos[0]), float(a.pos[1])))

Collision resolution — as opposed to the soft separation force above — is the point where corridors deadlock without a tie-breaker; the preventing agent collisions in crowd simulation drill-down covers velocity-obstacle resolution and the asymmetry rule that breaks oscillation.

Validation & Testing

A population simulation is trustworthy only when a gate proves agents stay separated, stay on the network, keep to plausible speeds, and reproduce across runs.

python
import numpy as np

def gate_population(samples, agents_radius=0.3, max_speed=1.6, dt=1.0):
    arr = np.array([(s[1], s[2], s[3]) for s in samples])  # (t, x, y)
    # 1. No two agents occupy the same point beyond their combined radius.
    #    (grouped per timestamp in practice; sketch shows the assertion.)
    # 2. No agent exceeds the physical speed cap between consecutive samples.
    #    reconstruct per-agent series, diff positions, divide by dt.
    #    assert (step_speed <= max_speed + 1e-6).all()
    # 3. Every sample timestamp is a clean multiple of dt from t0.
    assert np.allclose((arr[:, 0] % dt), 0.0), "timestamps drifted off the master clock"

def test_population_is_reproducible(build_and_run):
    a = build_and_run(seed=42)
    b = build_and_run(seed=42)
    assert a == b, "population or trajectories not reproducible under fixed seed"

The reproducibility test is the load-bearing one: because congestion is emergent, any nondeterminism — a set iteration order, an unseeded tie-break — compounds over ticks into a completely different flow field. Beyond per-agent physics, gate on aggregate realism: the temporal flow profile (trips per hour) and the spatial density field should match the target within tolerance, the kind of distributional check the realism metrics and evaluation stage formalizes. Wire every assertion as a build-failing check through the CI/CD integration for spatial data pipeline so a deadlocked or teleporting population never ships as an artifact.

Performance & Scale Considerations

  • Spatial index over pairwise checks. Rebuilding a k-d tree or uniform grid each tick and querying within the interaction radius turns the per-tick cost from O(n²) to roughly O(n log n). For dense uniform crowds a fixed grid with cell size equal to the interaction radius beats the tree, because each query touches only nine cells.
  • Vectorize the force sum. The per-agent Python loop above is clear but slow; at city scale, batch the neighbour offsets and compute separation forces with NumPy over ragged arrays or a fixed-k neighbour matrix, keeping the hot path in compiled code.
  • Spatial partitioning for parallelism. Shard the extent into tiles and simulate each on its own worker, exchanging only the agents near tile seams each tick. Derive each tile’s RNG stream from its integer coordinates and the scenario seed so tiles stay reproducible regardless of execution order, which is what lets the async execution for large grids model apply to a moving population.
  • Stream trajectories, do not accumulate. Append each tick’s samples to a partitioned Parquet or Arrow sink and release them rather than holding every agent’s full history in memory; peak heap then stays flat as the simulated day lengthens.
  • Timestep is the accuracy-cost dial. A smaller Δt makes collision avoidance smoother and reduces tunnelling through obstacles but multiplies tick count linearly. Choose the largest Δt at which agents still cannot pass through each other within one step, given the speed cap and agent radius.

Failure Modes & Troubleshooting

Frequently Asked Questions

Why does my simulation slow to a crawl as I add agents?
A naive collision or separation check compares every agent against every other one, so cost grows as the square of population — ten thousand agents is a hundred million distance computations per tick. Replace the pairwise scan with a spatial index: rebuild a k-d tree or uniform grid each tick and query only neighbours within the interaction radius. That drops the per-tick cost to roughly O(n log n) and restores near-real-time performance.
My agents freeze facing each other or oscillate side to side. How do I fix it?
Deadlock and jitter come from a symmetric avoidance rule with no tie-breaker: two agents apply equal and opposite forces and cancel, or overcorrect each tick. Add an asymmetry — a consistent pass-on-one-side bias keyed on agent id, or a velocity-obstacle resolution that accounts for each agent's intended velocity rather than just position. Reserving a small forward bias toward the goal also stops agents from stalling when separation forces balance the seek force.
Agents arrive at destinations at impossible times. What went wrong?
Schedule incoherence happens when the activity generator and the router are not reconciled against one shared clock. Derive every timestamp from a single master clock as tick times the fixed timestep plus a scenario start, never from wall-clock time, and check that each activity's travel time fits the gap before its next earliest-start. If a route cannot be completed in the scheduled window, either widen the window or drop the activity, but do not let the agent teleport.
Two runs of the same scenario produce different congestion. Why?
Because congestion is emergent, any nondeterminism compounds over ticks into a different flow field. The usual culprits are seeding agents from wall-clock time, iterating agents from an unordered container, or an unseeded tie-break in collision resolution. Seed the population from an explicit integer, iterate a stable ordered list, make every tie-break deterministic, and add a CI test that runs the scenario twice and asserts identical output.
How do I choose the simulation timestep?
The timestep trades accuracy against cost. Too large and fast agents tunnel through each other or through obstacles between ticks; too small and the tick count — and runtime — balloons. Pick the largest timestep at which an agent moving at the speed cap advances less than the combined agent radius in one step, so collisions are always caught. If avoidance still looks coarse at that value, refine only the steering substep rather than the whole loop.