Multiple Hypothesis Tracking (MHT)

Unlike greedy algorithms that make an irrevocable hard assignment at each time step, MHT propagates multiple data association hypotheses forward in time. When a measurement's origin is ambiguous—such as a radar return falling between two crossing targets—MHT creates separate branches for each plausible assignment. The algorithm defers the final decision until future measurements provide clarifying evidence, allowing the correct hypothesis to be confirmed retrospectively. This prevents premature, irreversible errors that cascade into track loss.

MHT maintains a dynamically expanding hypothesis tree where each branch represents a distinct global interpretation of measurement-to-track assignments. Key management strategies include:

• Clustering: Partitioning the tree into independent sub-problems to limit combinatorial growth
• Pruning: Deleting low-probability branches using techniques like N-scan-back pruning, which resolves ambiguities older than N frames
• Merging: Combining branches that share recent assignment histories to reduce redundancy Without these controls, the hypothesis space grows exponentially with the number of measurements and targets.

Every hypothesis is assigned a log-likelihood ratio (LLR) score that quantifies its probability relative to the null hypothesis (all measurements are false alarms). The score accumulates recursively, incorporating:

• Kinematic consistency: How well a measurement fits the predicted target state under a motion model
• Detection probability (P_D): The likelihood a target produces a measurement
• False alarm density (λ): The expected rate of clutter measurements per unit volume
• New target probability: The likelihood a measurement originates from a previously undetected object This Bayesian framework provides a principled basis for comparing and ranking competing hypotheses.

MHT inherently handles automatic track birth and death as part of the hypothesis evaluation process. A new track hypothesis is initiated when a measurement persistently fails to associate with existing tracks and accumulates sufficient LLR score to exceed a confirmation threshold. Conversely, a track is terminated when its hypothesis branch falls below a deletion threshold, typically due to consecutive missed detections. This integrated approach avoids the need for separate, heuristic track management logic and naturally handles appearing and disappearing targets.

Two primary MHT implementations exist:

• Hypothesis-Oriented MHT (HOMHT): Propagates complete global association hypotheses from scan to scan, evaluating all possible joint assignments. It is conceptually straightforward but computationally intensive.
• Track-Oriented MHT (TOMHT): Maintains individual track hypotheses independently and forms global hypotheses by selecting compatible combinations of tracks. This formulation is more memory-efficient and forms the basis of modern practical implementations, as tracks can be shared across multiple global hypotheses without duplication.

Unconstrained MHT is NP-hard due to the combinatorial explosion of association hypotheses. Practical implementations rely on aggressive complexity reduction:

• Gating: Excluding measurements that fall outside a validation region around the predicted track position
• K-best hypothesis generation: Using Murty's algorithm to generate only the K most probable global hypotheses rather than all possibilities
• Clustering: Decomposing the global problem into independent, spatially separated clusters
• N-scan pruning: Forcing resolution of ambiguities older than N frames, limiting tree depth These techniques make MHT tractable for real-time applications with dozens to hundreds of targets.

The fundamental computational challenge that MHT is designed to solve. Data association determines which sensor measurement originated from which physical object in a cluttered environment. Without correct association, sensor fusion fails catastrophically.

• Hard assignment commits to a single pairing immediately, risking irreversible errors
• Soft assignment (as in JPDA) weights multiple possibilities probabilistically
• Deferred assignment (as in MHT) propagates ambiguity forward until future data resolves it

MHT is the most sophisticated deferred-logic solution to this problem, maintaining a tree of competing association hypotheses across multiple time steps.

A high-level fusion architecture where locally processed state estimates from independent sensor systems are combined into a single global track. This contrasts with MHT, which typically operates on raw measurements.

• Each sensor node runs its own local tracker and transmits compressed track data
• Fusion center combines tracks using algorithms like Covariance Intersection
• Reduces communication bandwidth compared to raw measurement transmission
• Critical challenge: Handling unknown cross-correlation between track estimates from common process noise or prior fusion steps

MHT can be applied at the track-to-track level when local trackers report ambiguous or conflicting object identities.

The essential computational management technique that prevents MHT's hypothesis tree from growing exponentially. Without pruning, the number of hypotheses would quickly become intractable.

• N-scan pruning: Resolves ambiguity older than N time steps by retaining only the most probable branch
• K-best hypotheses: Keeps only the top K hypotheses ranked by cumulative log-likelihood score
• Clustering: Decomposes the global hypothesis space into independent clusters of tracks that share no common measurements
• Track score thresholding: Eliminates hypotheses with scores below a dynamically computed threshold

Effective pruning is what makes MHT computationally feasible for real-time applications.

The rule-based or probabilistic mechanisms that manage the birth and death of track hypotheses within an MHT framework, preventing the tracker from being overwhelmed by false alarms.

• Track initiation: A new tentative track is spawned when an unassociated measurement appears; it must survive a confirmation period (e.g., M-of-N detection logic) before being promoted to a confirmed track
• Track deletion: A confirmed track is terminated when its cumulative probability of existence drops below a threshold due to repeated missed detections
• MHT naturally handles initiation ambiguity by maintaining competing hypotheses for new tracks alongside existing ones
• Clutter density models are critical for correctly scoring initiation hypotheses against the null hypothesis that a measurement is a false alarm