Multi-target tracking, sensor fusion and estimation

I. Introduction

The four preceding articles are all concerned with the same difficulty: deciding which measurement belongs to which target. Suppose that difficulty away. Suppose one target, no clutter, and every bearing correctly attributed. There is still a limit on how well the target can be located, and it is set by nothing but where the sensors stand.

This article is about that limit. It asks two questions and keeps them separate. What accuracy does a given constellation of sensors permit, for any unbiased estimator whatever? And how much of that permitted accuracy does a particular estimator actually deliver? The first is answered by the Cramér–Rao bound, which depends on the geometry and the angular noise and on nothing else. The second is answered by measurement, against two estimators that make different compromises.

Between them sits a dimensionless figure of merit, obtained by dividing the bound by the noise and an effective range so that only the geometry remains. It is the direct analogue of the dilution of precision used in satellite navigation [8], and it transfers between scenarios in the way an absolute error in metres does not. This is therefore an instrument rather than a method: there is no association to get wrong, no filter to diverge and no random seed — every quantity below is a closed-form function of where the sensors are.

II. What the figure computes

One target sits at the origin and its sensors stand around it, given as coordinates relative to the target and multiplied by a scale — so CAM1 [1, 2, 3.5] at scale 1000 is a sensor one kilometre east, two north and three and a half up. Nothing is simulated and no random numbers are drawn. The three bodies in Fig. 2 are covariances, not samples: the snapshot bound, the converged EKF and the batch Gauss–Newton solution, each an exact function of the geometry.

All three are normalised by σ · r_eff. The covariance of a bearing-only estimate scales exactly with the measurement noise, so the absolute noise level cancels and what remains is a property of the constellation and the estimator alone. The angular noise therefore changes every absolute figure in Table II and changes none of the shapes, which is the point: the ratio is the transferable fact and the metres are not.

III. The bound

A sensor at p observing a target at x in three dimensions returns an azimuth and an elevation. Linearising both about x gives a 2×3 Jacobian H whose rows are orthogonal to each other and to the line of sight; with isotropic angular noise, σ_az = σ_el = σ, the information that sensor contributes collapses to a projector:

with u the unit line of sight and r the range. The projector annihilates u exactly: one sensor leaves the along-sight direction completely unconstrained, which is the formal content of the sentence “a bearing has no range”. Summing over sensors and inverting bounds any unbiased estimator:

J is singular when every line of sight lies in one plane through the target, or when two sensors are collinear with it. Table II reports its rank for that reason, and a rank below three means the bound is infinite in some direction rather than merely large.

IV. The figure of merit

The trace of J⁻¹ is a position variance in square metres, and it mixes two things a reader wants separated: how noisy the sensors are, and how well they are placed. Factoring out the noise and a range leaves a pure geometry number. The range used is the root-mean-square of the inverse ranges, because that is the combination (1) actually weights by:

so that σ_pos = σ · r_eff · BDOP exactly, with BDOP dimensionless and independent of the noise. This is the same construction as GDOP in satellite navigation, where the range noise and the satellite geometry are separated in precisely this way. The difference is that a pseudorange constrains the direction along the line of sight and a bearing constrains the two directions across it, so the projector in (1) is the complement of the one in the GNSS derivation.

Two closed forms are worth carrying. For N sensors evenly spaced on a level ring around the target, BDOP = √(5/N), which Table II reports as best level ring of the same N so that a constellation can be read against the best arrangement of that many sensors rather than against perfection. For a pair subtending an angle θ at the target, BDOP = √(2/sin²θ + ½), minimised at θ = 90° and divergent as the pair becomes collinear with the target. Evaluating both at their optima gives the fact that governs how the whole report should be read: a right-angled pair is only 1.29× worse than an ideal three. Geometry is rarely the binding constraint in bearing-only tracking. Association is.

V. The two estimators

The bound is what a perfect estimator would achieve. The two in Fig. 2 are real ones, and they differ in exactly one assumption.

Gauss–Newton is a batch solution. It assumes the motion model is exactly right — constant velocity, no manoeuvre — and solves all scans at once for the state at the epoch of interest. Propagating each scan’s information back through the transition matrix Φ_k and summing gives the normal equations, whose inverse is the covariance:

With the model exactly true this attains the Cramér–Rao bound for the batch, which is why the Gauss–Newton body in Fig. 2 is the smaller of the two and why its ratio in Table II can fall below one: it is being compared against the single-epoch bound, and it has many epochs.

The EKF is recursive and carries process noise. It cannot assume the target will not manoeuvre, so each prediction inflates the covariance before the next measurement deflates it:

written in information form because that is the form in which the update is a sum and the numerics are well behaved. Q is the continuous white-noise acceleration model with intensity σ_a. Iterating (5) is a Riccati recursion; it converges to a steady state that does not depend on where it started, and that steady state is what Fig. 2 draws and Table II reports.

VI. Advantages

The absolute noise level cancels, so the result transfers. Because (3) is exact, a BDOP measured for one constellation holds for the same geometry at any sensor accuracy. A siting decision can therefore be made before the sensor is chosen, and a sensor decision after the siting is fixed, without either invalidating the other.

The bound is a floor, not a model, so it cannot be argued with. No estimator, however elaborate, does better than (2) for the geometry it is given. That makes the bound the right first calculation on any proposed constellation: if it is inadequate, no amount of filter design will rescue it.

The gap between the two estimators is adjustable, and its endpoint is an identity. Set σ_a to zero and the two coincide exactly: with no process noise Q vanishes, (5) accumulates information without ever discarding any, and the recursion reproduces (4) term for term. Every metre of the gap is therefore attributable to a stated assumption about how hard the target may manoeuvre, and it moves continuously between the two as that assumption is relaxed.

The batch is the right choice for a siting study; the recursion is the right choice for a tracker. The batch answers “how well could this geometry do over an observation”. The recursion answers “how well is this estimate doing now, on a target that may not obey the model”. They are different questions and the ratio between them, reported as cost of being recursive, is the price of the second answer.

VII. Limitations

It bounds one epoch of one target, and nothing about association. The bound assumes the measurements assigned to the target are the target’s. Everything the other four articles are about — which bearing belongs to which target — sits outside it, which is why a geometry can be almost adequate while the tracker built on it is not (Appendix A).

It bounds unbiased estimators only. A bearing-only estimator linearised about a poor initial guess can be biased along the line of sight, and a bound on variance says nothing about how far the mean has moved. The bound and a biased estimate can both be small and still disagree.

The recursion has to be given somewhere to start, and the batch has to be given a model. The EKF’s steady state is start-independent, but its transient is not, and Table II reports a settling time in scans for that reason: a constellation that settles in thirty scans and one that settles in three hundred are different propositions even when their converged covariances match. The batch has no transient and instead has an assumption — exact constant velocity — which a manoeuvring target simply violates.

Rank is a cliff, not a slope. When every line of sight becomes coplanar with the target the bound is infinite in one direction, and the transition is abrupt rather than gradual. Reading BDOP alone will not warn of it; the rank in Table II will.

A sensor at the zenith contributes half of what it appears to. Its azimuth is undefined directly overhead, so it supplies one row of information instead of two. Such sensors are drawn in the warning colour and counted separately as skipped, because a report of three sensors that is using two is worse than no report.

VIII. Reading the figure

Both estimators are drawn as translucent bodies, and the selected one is solid with its three principal-plane rings. Area is what makes a colour legible at this size: an outline, however distinct its hue, disappears against a second outline crossing it.

The outline of an ellipsoid under orthographic projection is exactly an ellipse, computable in closed form — with A the matrix of semi-axes and R the 2×3 projection, the silhouette is the ellipse of shape matrix (RA)(RA)^T. That is why the projection is orthographic and why the bodies are exact rather than meshed. The three world axes are drawn through the origin rather than as a corner gizmo, because the ellipsoids and the sensors share those axes and the tilt of a body is only readable against the axis it is tilted from.

Neither body is drawn at the scale of the constellation. The constellation is kilometres across and the covariances are tens of metres, a ratio of some hundreds; at a common scale the ellipsoids would be a dot. The magnification is stated on the figure, and it is the one thing in it that is not to scale.

IX. Numerics and validation

Convergence is measured, not asserted. A quiet covariance trace is not evidence of a steady state for a moving target, because the geometry itself is changing and a trace can be momentarily flat while the recursion is still travelling. The recursion is therefore run twice from priors two orders of magnitude apart, and it is called converged when the two agree. Start-independence is the property that matters and it is the one tested.

Two numerical details are load-bearing. The 3×3 eigen-decomposition that turns a covariance into semi-axes is Jacobi rather than a closed-form cubic. And the 2×2 discriminant of the silhouette is evaluated as hypot((s₁₁−s₂₂)/2, s₁₂) rather than as tr²/4 − det: the two are algebraically identical and numerically are not, because the second subtracts nearly equal numbers exactly when the eigenvalues are close — that is, when the geometry is good. On a sphere of radius 7 the cancelling form returns 7.000000048 and 6.999999952 for what must be a circle.

Validation. The measurement geometry is a reference implementation’s validated three-dimensional bearing model. The covariance recursions of §V are original and are measurement-validated: by the closed forms of §IV, which they must reproduce exactly for a level ring and for a pair; by the σ_a = 0 identity of §VI, which they must satisfy to within numerical precision; and by equivariance, since rotating the whole constellation about the vertical must rotate the covariance and change nothing else.