Correcting Clock Skew in Multi-Agent Trajectory Streams

When trajectories from many synthetic agents are joined on time and the results show impossible near-misses or phantom gaps, the cause is per-agent clock skew — each agent stamps its samples with a slightly offset, slightly fast-or-slow clock, so identical real instants carry different timestamps.

Part of Temporal Synchronization for Moving Objects: that stage puts independently generated moving objects onto a shared timeline, and this page isolates the correction that must run before any time-based join — estimating each agent’s constant offset and linear drift against a common reference, then resampling every stream onto one clock so spatiotemporal proximity means what it claims to mean.

Root Cause: A Per-Agent Affine Clock Error

Each agent in a distributed generation run — a separate process, container, or simulated device — timestamps its samples from its own clock. Two error terms accumulate. A constant offset $b_i$ appears when agent $i$’s clock starts at the wrong absolute time (an unsynchronized boot, a time-zone or epoch mismatch, a fixed pipeline latency). A drift or skew $a_i$ appears when the clock runs fast or slow, so the error grows linearly with elapsed time. The relationship between an agent’s local timestamp $t^{\text{local}}_i$ and true reference time $t^{\text{ref}}$ is affine:

$$t^{\text{local}}_i = (1 + a_i)\, t^{\text{ref}} + b_i + \varepsilon_i,$$

where $a_i$ is the fractional rate error (parts per million for a real oscillator, but arbitrarily large in a mis-seeded synthetic run), $b_i$ is the offset in seconds, and $\varepsilon_i$ is small sampling jitter. Inverting it recovers reference time: $\hat{t}^{\text{ref}} = (t^{\text{local}}_i - b_i)/(1 + a_i)$.

The damage is entirely in the join. A spatiotemporal join pairs samples whose timestamps fall within a tolerance window, then reasons about the spatial distance between the paired points. If agent A’s clock leads agent B’s by three seconds, a join at nominal equal time pairs A’s position with where B will be three seconds later — so two agents that were fifty metres apart appear to occupy nearly the same point, manufacturing a collision, or two agents that actually passed close appear never to have met. This is distinct from the design-time alignment covered in aligning multi-agent trajectory timestamps in distributed systems: there the concern is agreeing on a timeline convention up front, whereas here the streams already exist with baked-in per-agent affine error that must be measured from the data and removed. Because drift grows with time, a run that looks aligned at the start silently diverges over a long window, which is why a single offset correction is never enough.

Minimal Reproducer: Detect Skew from a Shared Event

Confirm skew exists by finding an event every agent observes — a shared checkpoint crossing, a common trigger, a rendezvous — and comparing the timestamps each assigned to it. Pin the toolchain so interpolation is deterministic.

Copy
# requirements.txt — pin majors, let patch releases float
numpy==1.26.*
scipy==1.11.*
pandas==2.*

pythonCopy
import numpy as np

def skew_from_shared_events(local_stamps: dict[str, np.ndarray],
                            ref_times: np.ndarray) -> dict[str, float]:
    """local_stamps[agent] = the agent's own timestamps for the SAME ordered events.
    ref_times = the true reference time of each shared event.
    Returns the max residual offset per agent under a zero-correction assumption.
    """
    out = {}
    for agent, ts in local_stamps.items():
        residual = ts - ref_times          # if this is non-constant, there is drift too
        out[agent] = float(np.abs(residual - residual.mean()).max())
    return out

# Two shared checkpoints observed by three agents; reference at t=0 and t=600 s.
ref = np.array([0.0, 600.0])
local = {"A": np.array([2.9, 603.1]),      # ~3 s constant offset, little drift
         "B": np.array([0.1, 612.4]),       # grows to +12 s -> strong drift
         "C": np.array([0.2, 600.3])}       # nearly clean
print(skew_from_shared_events(local, ref))
# {'A': ~0.1, 'B': ~6.1, 'C': ~0.05}  -> B's non-constant residual flags drift, not just offset

A residual that is constant across events is pure offset; a residual that grows with reference time is drift. Any agent whose residual spread exceeds the join tolerance will corrupt spatiotemporal pairing and must be corrected.

Fix: Fit the Affine Model, Then Resample onto a Common Clock

Correction is two moves: fit each agent’s offset and drift by least squares against reference times of shared events, then resample every stream onto one uniform reference grid so all agents share identical timestamps before any join.

Step 1 — Fit offset and drift per agent

With at least two shared events, fit the affine map $t^{\text{local}} = (1+a)\,t^{\text{ref}} + b$ by least squares and invert it to map local time back to reference time. More shared events make the drift estimate robust to jitter.

pythonCopy
import numpy as np

def fit_clock(local_event_ts: np.ndarray, ref_event_ts: np.ndarray) -> tuple[float, float]:
    """Least-squares fit of local = (1+a)*ref + b. Returns (a, b)."""
    if len(ref_event_ts) < 2:
        raise ValueError("need >= 2 shared events to separate drift from offset")
    slope, intercept = np.polyfit(ref_event_ts, local_event_ts, deg=1)
    return float(slope - 1.0), float(intercept)     # a = slope-1, b = intercept

def local_to_ref(local_ts: np.ndarray, a: float, b: float) -> np.ndarray:
    """Invert the affine clock: recover reference time from local timestamps."""
    return (local_ts - b) / (1.0 + a)

Step 2 — Resample every stream onto the common reference grid

Convert each agent’s timestamps to reference time, then interpolate positions onto one shared, uniformly spaced grid. Interpolate in a metric CRS so the intermediate positions are geometrically sound, and only within each agent’s observed interval — never extrapolate a position beyond where the agent actually reported.

pythonCopy
import numpy as np

def resample_to_common_clock(streams: dict, clocks: dict, grid: np.ndarray) -> dict:
    """streams[agent] = (local_ts (N,), xy (N,2) metric). clocks[agent] = (a, b).
    grid = uniform reference timestamps shared by all agents.
    Returns positions for every agent on `grid`, NaN outside the agent's coverage.
    """
    out = {}
    for agent, (local_ts, xy) in streams.items():
        a, b = clocks[agent]
        ref_ts = local_to_ref(local_ts, a, b)
        order = np.argsort(ref_ts)                  # ensure monotonic for interp
        ref_ts, xy = ref_ts[order], xy[order]
        lo, hi = ref_ts[0], ref_ts[-1]
        x = np.interp(grid, ref_ts, xy[:, 0])
        y = np.interp(grid, ref_ts, xy[:, 1])
        mask = (grid < lo) | (grid > hi)            # do not extrapolate
        x[mask] = np.nan; y[mask] = np.nan
        out[agent] = np.column_stack([x, y])
    return out

Only after this resampling is a spatiotemporal join valid: every agent’s row at grid index $k$ refers to the same reference instant, so a proximity query returns genuine simultaneity. This is the temporal counterpart to the spatial degradation in adding realistic GPS noise to synthetic vehicle trajectories — correct the clock first, then any position noise you add is attributed to the right instant. Downstream consumers such as agent-based mobility simulation depend on this alignment to reason about interactions between agents.

Verification Step: Gate Alignment at Shared Events

Assert that after correction the residual at held-out shared events is within tolerance and that a known-simultaneous pair actually resolves as simultaneous.

pythonCopy
import numpy as np

def test_clock_correction_aligns_streams(clocks, holdout_local, holdout_ref, *, tol_s=0.25):
    # 1. Held-out shared events must map back to reference within tolerance.
    for agent, local_ts in holdout_local.items():
        a, b = clocks[agent]
        recovered = local_to_ref(local_ts, a, b)
        err = np.abs(recovered - holdout_ref).max()
        assert err <= tol_s, f"{agent}: residual {err:.3f}s exceeds {tol_s}s after correction"

def test_no_phantom_simultaneity(resampled, grid, truth_gap_m, *, k, tol_m=5.0):
    # 2. At grid index k, two agents known to be truth_gap_m apart must not collapse.
    a_xy, b_xy = resampled["A"][k], resampled["B"][k]
    if np.isnan(a_xy).any() or np.isnan(b_xy).any():
        return  # outside coverage; nothing to assert
    d = np.linalg.norm(a_xy - b_xy)
    assert abs(d - truth_gap_m) <= tol_m, f"skew reintroduced: {d:.1f}m vs truth {truth_gap_m}m"

The held-out residual gate is the load-bearing one: fitting on all shared events and testing on the same events would pass a model that merely memorized them, so reserve at least one event for verification. The phantom-simultaneity check guards the actual downstream consequence — a join that manufactures or erases a near-miss.

Edge Cases & Gotchas

Only one shared event cannot separate offset from drift. With a single common observation you can estimate a constant offset but the drift term is unidentifiable — infinitely many $(a, b)$ pairs fit one point. The fit must raise rather than silently return drift zero, because assuming zero drift on a fast-running clock leaves a linearly growing error that a start-of-run check will not catch. Require at least two well-separated shared events, and prefer several spanning the full window.

Never extrapolate positions past an agent’s coverage. Resampling onto a common grid tempts you to fill an agent’s rows before its first or after its last real sample, but interpolation there is invention: the agent reported no position, so the honest value is NaN. Extrapolating a moving object’s location produces confident-looking coordinates that never existed and will trigger false joins. Mask everything outside each agent’s observed reference interval.

Leap seconds and epoch boundaries in the reference clock. If the reference timeline is wall-clock UTC, a leap second inserted mid-run adds a one-second step that the affine model will misattribute to offset or drift, warping the whole fit. Use a monotonic reference such as TAI or elapsed seconds from a fixed epoch for the correction, and only convert to civil time for display. The same caution applies at day boundaries where a naive string-parsed timestamp can wrap.

Frequently Asked Questions

Related

• Temporal Synchronization for Moving Objects — the timeline-alignment stage this page implements, from clock modeling through resampling and gates.
• Aligning Multi-Agent Trajectory Timestamps in Distributed Systems — the design-time convention for agreeing on a timeline that this data-driven correction complements.
• Agent-Based Mobility Simulation — the downstream consumer that reasons about agent interactions and depends on a common clock to be correct.
• Adding Realistic GPS Noise to Synthetic Vehicle Trajectories — the spatial-noise stage to run after clock correction so error is anchored to the right instant.