Multi-target tracking, sensor fusion and estimation

I. Introduction

The three methods so far differ in how much they defer, but not in what they are doing: each takes the tracks it holds and decides which measurements belong to them. This one does not associate measurements to tracks at all.

Instead it takes m consecutive scans from each of S sensors and solves a single multidimensional assignment [4] whose decision variables are tuples of measurements — one from each sensor — scored by how well that tuple triangulates to a single point. What leaves the front end is a set of position fixes, and only those fixes reach a tracker. The tracker is then the ordinary one of the first article, receiving positions instead of bearings, which is a far easier problem because a position has no ambiguity left to resolve.

The reason to invert the pipeline is that the ambiguity defeating the other three is geometric, and this dissolves it geometrically and before any filter runs. A permutation ghost is consistent with one scan from each sensor but not with m of them, because the ghost implied by the first scan is not the ghost implied by the second. Note that sequential decision is not what the abbreviation denotes and nothing here defers a decision sequentially: the decision is made once, in a batch, on more data than any single scan contains.

II. Problem formulation

A. What is given, what is returned

The input is a window of m scans from each of S sensors, held together rather than processed in sequence. The output is a set of position estimates with covariances, and no association information whatever — the front end and the tracker are separate programs joined only by a set of points. Everything to the left of that join works in measurement space and knows nothing about tracks; everything to the right is the tracker of the first article, unmodified.

The window is two looks per sensor. Deeper windows were measured and do not pay for themselves at this target density.

B. The hypothesis space

A candidate is an S-tuple (i₁, …, i_S) picking one measurement from each sensor, extended across the m scans in the window. The space is the set of such tuples that survive gating, and a solution is a set of tuples using each measurement index at most once per sensor.

This is the one hypothesis space here that is indexed by measurements rather than by tracks, and the consequence runs through the whole method: a candidate has an identity independent of any track, so two candidates with the same index tuple are the same candidate and must be treated as one.

C. The tuple cost

A tuple’s cost is the residual of the least-squares triangulation of its bearings to a single point:

evaluated at the optimum, plus a penalty for leaving a measurement unassigned. A tuple of bearings that really do come from one target meets at a point and has a small residual; a permutation ghost’s tuple does not, once more than one scan is in the window. This is the same likelihood-ratio reasoning as Appendix C applied to a batch rather than to a scan: the residual is the negative log-likelihood of the tuple and the unassigned penalty is the density of the alternative explanation.

III. The algorithm

A. The assignment problem

Over the gated tuples the problem is

which for S ≥ 3 is NP-hard — unlike the two-dimensional case of the first article, whose constraint matrix is totally unimodular and which is therefore solvable exactly. The whole of the rest of this section is the consequence of that one change of dimension.

B. Lagrangian relaxation

Dualise all but two of the constraint sets with multipliers u. What remains decomposes into a two-dimensional assignment that can be solved exactly:

L(u) is a lower bound for every u, so the bound is tightened by maximising over u. The subgradient of L at u is the constraint violation — how many times each index was used, less one — and the multipliers move along it with an accelerated step whose length adapts to the gap between the current subproblem value and the best bound so far.

C. Three details that are load-bearing

The multipliers must be projected. The dualised constraints are inequalities: an index used at most once, an unclaimed measurement being an implicit false alarm rather than an error. With the sign convention above that requires u ≤ 0, and the projection is applied after every step. Without it the multipliers of unclaimed indices drift positive, L(u) stops being a lower bound, and the termination test fires on a duality gap that is not real.

The incumbent is the best solution seen, not the last. The primal trajectory is not monotone and the final iterate is frequently worse than one encountered earlier.

The gap is a certificate. It states how far from optimal the returned answer can possibly be, which is what separates this from a heuristic: a heuristic gives an answer, this gives an answer and a bound on its error. The iteration stops when the relative gap falls below one per cent or after a fixed number of passes.

D. Gating the tuples

The number of possible tuples is the product of the measurement counts, so gating is not an optimisation here but a precondition. Pairs are formed first and tested against a χ² threshold on the triangulation residual; surviving pairs are extended one sensor at a time against a tighter one; pairs whose subtended angle is too shallow are rejected outright, because a shallow crossing localises nothing along the line of sight. The candidate count is capped. Table A1 carries all four values.

E. Track maintenance

There is none of its own, and that is the point of the architecture. Downstream of the front end the objects are positions with covariances and no association ambiguity, so birth, confirmation and deletion are exactly those of the first article, operating on an easier problem than any of the other three methods face.

One rule differs from MHT and for the opposite reason. Candidates with identical index tuples over the window must be merged, because here a tuple is the candidate’s identity rather than a summary of its history: two identical tuples are one candidate, and carrying both puts two identical rows in the cost matrix, which the assignment rejects as ill-posed.

IV. Advantages and cost

It is the most accurate method here by a wide margin once three sensors exist — 5 m at three and 2 m at four, against 41 and 36 for MHT. The permutation ghost never reaches the filter, so the filter never has to be robust to it.

It is genuinely multi-sensor. The other three fuse sensors by processing their measurements in sequence; this one poses a single problem across all of them, which is what the S-dimensional assignment is for.

The output is well-posed. Downstream of the front end there are positions with covariances and no association ambiguity at all, so the tracking problem that remains is the easy one.

The answer comes with a bound. Alone among the four it reports how far from optimal its own association can be, rather than asserting that it is right.

Cost. NP-hard for S ≥ 3, relaxed into exactly solvable two-dimensional subproblems. Measured solo at three sensors: 68 ms per step.

V. Limitations

Latency. No fix exists until m scans have been collected. For m = 2 at 10 Hz that is 200 ms of built-in delay, and it is not recoverable.

Cost. 68 ms per step against 1.5 for GNN — some 45× — which is what an NP-hard problem costs even relaxed. This is the method that presses hardest against the time budget.

Synchronisation. Tuples pair measurements across sensors, so the sensors must be time-aligned to a fraction of a scan.

Two sensors is still two sensors (161 m). With S = 2 the assignment is two-dimensional again and the extra scans in the window are the only thing distinguishing a ghost — which, for targets on similar courses, they may not.

VI. Validation

As with JPDA, no reference implementation of this method exists and it is measurement-validated only, characterised by the medians in Table III over seed sets disjoint from those used to tune it.

The distinction to keep is that the reference does contain a sequential-decision tracker, that tracker is verified against the reference by regression, and it is not what is described here. The multidimensional solver underneath this method is the part with a definite answer: its subproblem solutions are checked against exact enumeration on problems small enough to enumerate, and its returned bound is checked to be a bound — never above the cost of the solution it is issued with.