Multi-target tracking, sensor fusion and estimation

I. Introduction

At every scan a sensor delivers a set of detections and the tracker must decide which detection belongs to which track. That decision is the measurement-to-track association problem, and it comes before filtering rather than after it: an estimator fed the wrong measurement does not produce a noisy answer, it produces a confident wrong one, and no amount of filter tuning recovers it.

Global nearest neighbour answers the question in the simplest way that is still principled. It poses one assignment problem per scan over the gated track–measurement pairs, solves that problem exactly, and commits to the answer. A single interpretation of the scan survives, so what passes forward is one mean and one covariance per track.

This method is the baseline of the report and the other three define themselves against it. Joint probabilistic data association declines to choose and forms a weighted average; multiple hypothesis tracking keeps the alternatives and decides several scans later; the multi-scan assignment method solves for target positions across sensors before any tracker sees a bearing. Each costs more than this one. What follows states the problem precisely, gives the algorithm that solves it, and names the price the commitment exacts.

II. Problem formulation

A. What is given, what is returned

The tracker holds T tracks, each carrying a Gaussian estimate of position and velocity. A scan brings m detections. Association must return a pairing in which every track receives at most one detection and every detection is given to at most one track: a permutation on the gated subset, with unmatched entries permitted on both sides.

B. The hypothesis space

One permutation, and that is the whole of it. Where the other three methods carry a structure — a distribution over joint events, a tree of histories, a set of cross-sensor tuples — this one carries a single answer, and the brevity of this subsection is the honest measure of the difference.

Two consequences follow and both are structural. Unmatched detections are the candidates for new tracks, so births are settled by the same step that settles associations rather than by a rule bolted on beside it. And because exactly one pairing survives the scan, nothing else about the scan is retained: the memory is one covariance per track and the state does not grow with clutter density.

C. The score

The criterion is likelihood, not proximity. For track i and measurement j the innovation and its covariance are

and the squared Mahalanobis distance d²_ij = ν^T S⁻¹ ν is what the gate tests. The cost that is actually assigned is not that distance but

and the log-determinant term is the part that is easy to omit and expensive to omit. Without it the score is a distance rather than a likelihood ratio, and a track with a large covariance wins every contest it enters simply by being uncertain — precisely the tracks that should be losing them. With it, the cost is (up to constants) the negative log-likelihood of the pairing. Appendix C derives the ratio in the form all four methods share.

III. The algorithm

A. Gating

A pair is admissible when d² falls under a χ² threshold γ, or when its score exceeds what the track would earn by going undetected. The second limb matters more than it looks: it admits a pair the distance test would reject whenever taking it is still better than coasting, which is what keeps the assignment from being decided by the gate rather than by the cost.

B. The assignment

Over the admissible pairs the problem is

Two properties of (3) do the work. It is global: total cost is minimised over all pairs at once, rather than each track greedily taking its own nearest measurement, which is a different and worse algorithm frequently confused with this one. And it is exact: the constraint matrix is totally unimodular, so the linear relaxation has integral optima and the optimum is reached in polynomial time — by the Hungarian method [11], or by auction [7], which is what is used here.

C. The update

The awarded pair drives an ordinary Kalman update, x̂ ← x̂ + Kν with K = P H^T S⁻¹. A track that was awarded nothing coasts on its prediction with its covariance inflated, which widens its gate for the next scan.

D. Track maintenance

Detections the assignment left unclaimed are candidates for birth, capped per scan and refused where they fall within the minimum separation of a live track. Confirmation requires three things at once and not one: the sequential test of Appendix C must pass, the track must have been corroborated from a second viewpoint in the same cycle, and its 2σ major axis must be inside the confirmation limit. Deletion is the sequential test alone. Table A1 carries every value.

One of those values is opposite here to its value in the deferred-decision methods. A missed detection inflates the covariance tenfold, because a single-hypothesis tracker that misses has nothing to fall back on and must widen its own gate or never reacquire. A method carrying an alternative branch already covers the miss, and widening its gate would only let ghost branches acquire clutter.

IV. Advantages and cost

It is the cheapest by a wide margin — 1.5 ms per step against 2.5 for JPDA and MHT and 68 for n-SDA. On an embedded budget that is often the whole argument.

It is exact, not greedy. The distinction matters: a greedy nearest neighbour makes a locally sensible choice that can be globally absurd, and the two are frequently conflated in the literature.

Its state is bounded and does not grow. One mean and one covariance per track regardless of clutter density, which makes both memory and latency predictable — a property MHT explicitly does not have.

It is deterministic, and verified against a reference implementation by regression on identical inputs, which makes it the natural baseline for the other three.

Cost. The assignment is O(n³) in the number of gated pairs, the update is O(1) per track, and the state is O(T). Measured solo at three sensors: 1.5 ms per step.

V. Limitations

The commitment is irrevocable. Nothing in the algorithm can revisit a scan, so an association that later evidence contradicts is simply carried forward.

Against the permutation ghost of Appendix A this is not a weakness that shows up as hesitancy but as confidence. The ghost is a genuine crossing, so the filter that tracks it converges normally and reports a small covariance. Measured at two sensors, the truth lies inside a track’s own 2σ contour far below the ~86% a calibrated two-dimensional filter would give: it reports a precision it does not have. Any copy quoting an error bar from the two-sensor case is quoting a number the filter cannot support.

At crossings the identity churns. GNN records substantially more identity switches than the multi-hypothesis methods on the same scenario, because a crossing is exactly the situation in which the best assignment this scan is not the best assignment overall.

VI. Validation

This method is a direct translation of a reference implementation and is verified against it by regression: identical inputs produce identical association decisions and identical filter states, bit for bit. That is the strongest validation claim made anywhere in this report, and it is available only because the algorithm is deterministic.

What the claim does not cover is the bearing-only front end. The reference measures position; the gate and the birth rule used here are this design’s own and are measurement-validated rather than regression-verified. Every accuracy figure quoted is a five-seed median, tuned on one seed set and reported on a disjoint one, because the same configuration has been measured spanning more than a factor of thirty across seeds — a single-seed figure measures one draw and not the method.