Multi-target tracking, sensor fusion and estimation

I. Introduction

Both methods so far settle the scan within the scan. One picks the best assignment and lives with it; the other refuses to pick and averages. Each is making the same concession, that the scan must be resolved using only the evidence the scan contains.

Multiple hypothesis tracking [1] declines that concession. When the evidence does not separate two interpretations, it keeps both, and it keeps them until later measurements do separate them. A track is no longer a state estimate but a history of associations; the histories form a tree; and the decision that GNN takes now is taken N scans later, by which time the targets have moved and the ambiguity has usually resolved itself.

Against the permutation ghost of Appendix A this is decisive, and it is decisive for a reason no amount of better scoring could supply: at the scan the ghost is born, its history and the true history have equal scores. Nothing can separate them then. Something can separate them three scans later. What the method costs is branches, and branches are memory and time, so most of what follows is about bounding them.

II. Problem formulation

A. What is given, what is returned

The inputs are again gated track–measurement pairs. What is returned is not an assignment but a set of surviving branches, together with the subset of them that forms the most probable mutually consistent interpretation of everything seen so far. Only the branches older than the decision window have been committed to; the rest are still hypotheses.

B. The hypothesis space

A candidate track is a sequence of associations over the last N scans. The sequences sharing a prefix form a tree, one tree per track, and a global hypothesis is a set of branches drawn from those trees that is mutually consistent, meaning no measurement is claimed by two of them.

There are two ways to organise the search, and which one is chosen decides everything downstream. The original formulation enumerates the global hypotheses and recovers a track’s probability by summing those that contain it. The track-oriented formulation scores each candidate track on its own and then assembles the best consistent set. The second gives up the first’s global hypothesis probabilities, and in exchange its scores are independent across tracks — which is exactly the separability a discrete optimisation needs, and the reason this is the formulation used here.

C. The score

Each branch carries a log-likelihood ratio: the likelihood that this sequence of measurements came from a target, against the likelihood that it is false alarms. It accumulates one term per scan,

with L_k = L_k−1 + ΔL. The terms add because the innovations of a track are white, so their joint density is the product of the marginals. Appendix C derives both increments and explains why the ratio is dimensionless, which is what lets branches carrying different numbers of detections be compared at all.

III. The algorithm

A. How the tree is built

Each scan every live node produces children of three kinds. A match node for every measurement inside its gate, one per gated pair. A miss node, for the possibility that the target was there and went undetected. An init node for every measurement, for the possibility that it came from a target not yet tracked.

The miss node is grown for every track, not only for tracks whose gate came up empty, and the distinction is not academic. If only empty-gate tracks coast, a track that loses a contested measurement to a neighbour has no surviving child at all and its entire subtree dies at the next pruning — precisely at a crossing, which is the situation branching exists for. Growing it unconditionally is the Kurien–Reid track-oriented formulation [14] and it costs a factor of (1 + gated pairs) per node per scan. The live branch count in Table I is that population, and watching it move with target density is watching the method’s cost directly.

B. Global hypothesis formation

Branch generation produces not the one cheapest assignment but the k cheapest, in order, by Murty’s algorithm [3]. The best consistent set is then the maximum-weight independent set

over the graph whose vertices are branches and whose edges join branches sharing a measurement. MWIS is NP-hard in general; the graphs here are small and sparse because gating has already removed almost every possible conflict, and they are decomposed into connected components first for the same reason JPDA clusters. Taking the K best sets rather than the single best is what gives each branch a probability, which the pruning below needs.

C. The ghost argument, made precise

At the scan a permutation ghost is born, its branch and the true branch have equal scores, so nothing can separate them — and this method does not try. By scan three the targets have moved, the ghost’s predicted position no longer matches any measurement, (2) fires instead of (1), and its score falls. The decision window is the algorithm’s statement of how long it is prepared to wait for that to happen, and its correct value is a property of how fast the geometry changes rather than of the tracker.

D. Track maintenance

A track is confirmed when its running maximum score passes an upper threshold and deleted when its score falls below a lower one. These are the bounds of Wald’s sequential probability ratio test [10], so they follow from the tolerable false-track rate α and missed-track rate β rather than from tuning: at α = 10⁻⁶ and β = 10⁻³ the thresholds are ln((1−β)/α) = +13.8 and ln(β/(1−α)) = −6.9.

Two quantities are carried and not one: the current score and the running maximum it has ever reached. A track that has not been confirmed dies on the absolute floor, while a confirmed one dies when it falls a fixed distance below its own maximum. A well-established track is therefore allowed a bad patch that would kill a freshly confirmed one, which is the whole purpose of carrying the second quantity. Appendix C states the tests and Table A1 the values.

E. Bounding the tree

Three prunings run, doing three different jobs. Leaf pruning keeps only the k best-scoring nodes claiming any one measurement, bounding the fan-out of a single popular measurement without looking at the tree as a whole. N-scan pruning is the commitment itself — once the window has passed a node, the best surviving branch below it is kept and its siblings discarded, and that decision stops being a hypothesis. Probability pruning drops branches whose share of the total hypothesis weight falls below a floor; where the first two prune by score, this prunes by the global picture, and a branch can be locally plausible while appearing in no hypothesis worth keeping.

A fourth is available and is deliberately not used. Merging collapses branches whose last N observations agree, on the argument that two histories differing only before the window can have no consequence the window is still able to decide. That argument holds when association is one-to-one, because sharing a recent history then means sharing the actual measurements. Under a hypothesis tree it does not: a node exists for every gated pair, so two distinct tracks can hold the same measurement at the same scan, and merging would fuse two tracks that are not the same track. It is measured worse here and is left off. The multi-scan assignment method takes the opposite view for an equally structural reason, given in its own article.

Above all of them sit hard caps on branches per track, branches in total and concurrent tracks. Those are not housekeeping and they are counted as cost rather than as machinery; the next section says why.

IV. Advantages and cost

It can be wrong and recover. Alone among the four, a bad association is a branch rather than a fact, and the branch dies when contradicted.

It resolves the permutation ghost by time rather than by geometry, which means it needs no extra sensor and no batch latency — only N more scans of the ones it already has.

Identity is stable. On the same scenario at two sensors MHT records a small fraction of GNN’s identity switches, because a crossing is the situation branching was invented for.

Best accuracy at three sensors of the three online methods (41 m against 68 and 99) at the same 2.5 ms as JPDA.

Cost, and the caps that make it a number. Murty k-best is O(k) assignments and MWIS is NP-hard but small on gated graphs. Measured solo at three sensors: 2.5 ms per step. That figure exists only because the branch population is capped: a hypothesis tree has no natural bound, so the caps in Table A1 are what convert an unbounded structure into a worst-case execution time and a memory footprint decided in advance. They are also the two knobs that trade accuracy for determinism.

V. Limitations

Branch explosion. The tree grows with target density, with clutter and with N, and the caps that contain it are hand-set limits whose right value depends on the scenario. Neither memory nor latency is bounded by anything intrinsic to the algorithm.

The N-scan window is a latency. A decision is only as good as the data behind it, and the data behind it is N scans old.

At two sensors it does not help (150 m). Deferring a decision is only useful if waiting produces information, and with two co-planar sensors observing targets on similar courses the ghost can persist for as long as the geometry does.

VI. Validation

The two halves of this method carry different claims and collapsing them would overstate what has been checked.

The hypothesis-tree core — node expansion, scoring, the prunings and the store that holds them — is a direct translation of a reference implementation and is verified against it by regression: identical inputs produce identical trees and identical filter states.

The k-best variant described here is not that translation. The reference’s own multiple-hypothesis routine is randomised, so no regression against it is possible; a deterministic variant returning the provably K best consistent sets was formulated instead, and it is measurement-validated. What is checked directly is that the sets it returns are ranked correctly, against exhaustive enumeration on graphs small enough to enumerate.