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.
Each tick couples activity selection, routing, and steering; congestion emerges from the shared space.
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:
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.
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:
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.
An agent-based mobility model is three coupled subsystems, and the realism of the output depends on all three being consistent with each other.
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.
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
@dataclassclassAgent:
aid:int
pos: np.ndarray # (x, y) in metres
vel: np.ndarray
schedule:list# [(activity, xy, earliest_start_s, duration_s), ...]
goal_idx:int=0defsynthesize_population(n:int, homes: np.ndarray, seed:int)->list[Agent]:
rng = np.random.default_rng(seed)# PCG64; reproducible population
agents =[]for aid inrange(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
defplan_route(graph: nx.Graph, src_node:int, dst_node:int)->list[int]:# weight="travel_time" precomputed on each edge from length / free-flow speedreturn 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
defstep_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 inenumerate(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.
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.
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
defgate_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"deftest_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.
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.
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.
