Data association (JPDA, MHT) and tracking

"The filter was flawless. It just spent three frames confidently tracking a guardrail it had mistaken for a motorcycle."

A Chastened AI Agent

This section assumes the Kalman prediction and update steps, the innovation \(\nu = z - H\hat{x}\), and the innovation covariance \(S = HPH^\top + R\) from Chapter 9, plus the Mahalanobis-distance and chi-square ideas from the probability primer in Chapter 4. The measurement sources we associate (radar detections, lidar clusters) come from Chapter 44 and Chapter 42.

The problem: measurements are unlabeled, and the world is messy

In single-target tracking the correspondence is trivial: one target, one measurement, feed it in. Multi-target tracking removes that luxury. At each scan the sensor produces a set of measurements corrupted by three realities. Clutter and false alarms: reflections, ground returns, and thermal noise produce detections with no real target behind them, typically modeled as a Poisson process with spatial density \(\lambda\). Missed detections: a real target is seen with probability of detection \(P_D < 1\), so some scans contain no measurement for a target that plainly exists. Unknown, time-varying cardinality: targets appear (track birth) and leave (track death), so even the number of things to track is a hidden variable.

The association question is therefore combinatorial: over \(n\) tracks and \(m\) measurements there are exponentially many ways to match them, and each way must also account for the "this measurement is clutter" and "this track was missed" possibilities. Every association method is a different answer to how much of that combinatorial explosion you evaluate before committing.

Gating: shrink the problem before you solve it

No method should consider every measurement for every track. A validation gate discards pairings that are statistically impossible. For track \(t\) with predicted measurement \(\hat{z}_t\) and innovation covariance \(S_t\), measurement \(z_j\) is gated in only if its squared Mahalanobis distance falls under a threshold:

Because \(d^2\) is chi-square distributed with degrees of freedom equal to the measurement dimension, you pick \(\gamma\) from the chi-square inverse CDF for a chosen gate probability (for example \(\gamma \approx 9.21\) for a 2D measurement at 99%). Gating is what makes real-time tracking tractable: it turns a dense \(n \times m\) problem into a sparse one, and it is the shared front end of every method below.

Global nearest neighbour: one clean assignment per scan

The simplest workable scheme scores every gated track-measurement pair and picks the single assignment that minimizes total cost. Using the negative log-likelihood of the innovation as the cost, \(c_{tj} = \tfrac{1}{2}d^2_{tj} + \tfrac{1}{2}\ln|2\pi S_t|\), the best one-to-one matching is the classic linear assignment problem, solved exactly in \(O(n^3)\) by the Hungarian (Kuhn-Munkres) algorithm. This is global nearest neighbour (GNN): unlike greedy per-track nearest neighbour, it resolves conflicts jointly so two tracks never grab the same measurement. GNN is fast, deterministic, and correct when targets are well separated. Its failure mode is exactly the crossing-targets case: when two gates overlap, one hard mistake swaps two tracks' identities and both filters diverge.

import numpy as np
from scipy.optimize import linear_sum_assignment
from scipy.stats import chi2

def gnn_associate(tracks, meas, gate_prob=0.99):
    """tracks: list of (z_hat[2], S[2,2]); meas: array (m, 2).
    Returns list of (track_idx, meas_idx) accepted assignments."""
    n, m = len(tracks), len(meas)
    gate = chi2.ppf(gate_prob, df=2)
    BIG = 1e6
    cost = np.full((n, m), BIG)
    for t, (z_hat, S) in enumerate(tracks):
        Sinv = np.linalg.inv(S)
        for j in range(m):
            nu = meas[j] - z_hat
            d2 = float(nu @ Sinv @ nu)
            if d2 <= gate:                                   # validation gate
                cost[t, j] = 0.5 * d2 + 0.5 * np.log(np.linalg.det(2 * np.pi * S))
    rows, cols = linear_sum_assignment(cost)                 # Hungarian, O(n^3)
    return [(t, j) for t, j in zip(rows, cols) if cost[t, j] < BIG]

tracks = [(np.array([0.0, 0.0]), np.eye(2)),
          (np.array([5.0, 0.0]), np.eye(2))]
meas = np.array([[0.2, -0.1], [4.8, 0.3], [9.0, 9.0]])       # last one is clutter
print(gnn_associate(tracks, meas))                            # -> [(0, 0), (1, 1)]

The gnn_associate function above is the entire hard-decision associator in roughly twenty lines, and in production it is often enough. The interesting engineering starts when GNN's single-best commitment is too brittle.

JPDA: never commit, average instead

Joint Probabilistic Data Association keeps one track per target but refuses to pick a winner. For each target it enumerates the feasible joint association events (respecting that a measurement comes from at most one target), computes each event's probability from the innovation likelihoods, the clutter density \(\lambda\), and \(P_D\), then marginalizes to a per-pairing probability \(\beta_{tj}\), the chance that measurement \(j\) belongs to track \(t\). The filter update uses a probability-weighted combined innovation:

with an extra "spread of the means" term added to the covariance to account for the association uncertainty. Because it blends rather than commits, JPDA does not suffer the catastrophic identity swap that fells GNN when targets pass close together; the ambiguity is absorbed as inflated, honest uncertainty. Its cost is that the target count is assumed fixed and known, and that blending can pull a track toward a nearby clutter point or coalesce two tracks that get too close. Modern variants (JIPDA, which adds a track-existence probability) restore birth and death handling.

MHT: defer the decision until evidence arrives

Multiple Hypothesis Tracking takes the opposite stance from JPDA's averaging: it keeps the alternatives separate and postpones the hard decision. At each scan MHT expands a tree of global hypotheses, each a consistent history of assignments (including "measurement was clutter" and "target was born" branches), and scores each hypothesis by its accumulated likelihood. A momentarily ambiguous pairing spawns two child hypotheses; a few scans later the motion evidence makes one history far more likely, and the tree is pruned back. This deferred-decision logic is the strongest classical associator in heavy clutter, because it lets future data correct present ambiguity, which neither GNN nor JPDA can do. The price is the hypothesis explosion: the tree grows combinatorially, so practical MHT lives or dies on aggressive pruning (keep the top-\(k\) hypotheses), gating, \(N\)-scan pruning (commit to decisions older than \(N\) frames), and clustering independent target groups. Track-oriented MHT with Murty's algorithm for the \(k\)-best assignments is the standard modern formulation.

Track lifecycle: birth, confirmation, death

No associator is complete without logic for when a track begins and ends, because cardinality is unknown. The workhorse is M-of-N logic: a tentative track is initiated from an unassigned measurement, promoted to confirmed only after it is updated in \(M\) of the last \(N\) scans (say 3 of 5), and deleted after a run of consecutive misses. This simple hysteresis is what suppresses clutter-born tracks (which fail to persist) while letting real targets survive occasional missed detections. Confirmation counting, gate probability, and deletion thresholds are the three knobs that trade false tracks against track continuity, and tuning them for the deployment clutter rate matters more than the choice of associator for most systems.

What's Next

In Section 49.5, we lift fusion from recursive filtering to the factor-graph estimator of Chapter 11, using GTSAM to fuse multiple sensors as a single optimization over the whole trajectory. Data association reappears there as a graph question: which factor connects which variable, and what happens when that link is wrong.