Numerous approaches to hypothesis pruning and merging have been developed to reduce the computational burden of MHT and Bayesian trackers. One basic approach to pruning is measurement gating, which has been proposed in both MHT (e.g. [2], [3]) and Bayesian (e.g. [4], [5]) algorithms, and is commonly employed in practice. Another approach to pruning is based on evaluating the likelihoods of the extended tracks (e.g. see [3] for MHT and [5] for Bayesian). Alternatively, for a single track, Singer et al. [4] suggest merging all tracks which share measurements for the past N times. As noted by Bar-Shalom [1], the Probabilistic Data Association Filter (PDAF) [6], an approximate Bayesian tracker, is related to the N=0 case. Joint PDAF (JPDAF) [7], which extends PDAF to multitarget tracking, time recursively extends multiple existing tracks which share measurements in their pruning gates. These practical but suboptimal pruning and merging approaches can generate diverged tracks during target maneuvers or after a few missed detections.
MHT is a discrete paramenter estimation problem, where the measurement-to-track associations are the discrete parameters. Pruning and merging techniques have been proposed for two similar discrete parameter estimation problems: digital communications where the Viterbi algorithm [8] and its extensions (e.g. [9]) are used to prune hypothesized discrete symbol sequences; and abruptly changing systems such as maneuvering target tracks, where a discretized multiple mode model is employed and a variety of approaches have been proposed for pruning or merging hypothesized discrete switching sequences (e.g. Generalized Pseudo Bayesian (GPB) merging [10]; Detection-Estimation Approximation (DEA) pruning/merging [11]; random populations pruning [12]; Interacting Multiple Modes (IMM) merging [13]; and Viterbi algorithm pruning [14]; [15]).
The Viterbi algorithm has also been used to prune hypotheses for several approaches to the target tracking in clutter problem. For time-recursive measurement-to-track association, the Viterbi Data Association (VDA) algorithm [16], an extension of an earlier Viterbi based algorithm [17], is a single track algorithm in which measurement gating is incorporated for an over-the-horizon radar application. A K-track Viterbi algorithm has been proposed for MHT [18], but this is only optimum with respect to a simple nonprobabilistic cost function (i.e. the energy required to get from one measurement to the next). A more efficient computational algorithm for the same cost was suggested in [19]. As a hypothesis pruner, the Viterbi algorithm assures the optimum hypothesis is kept only if all hypothesis costs satisfy a ``finite state machine'' or ``Markov'' condition [8]. Although this condition is satisfied for the simple nonprobabilistic energy cost used in [18], it is not for the maximum likelihood and MAP costs which are standard for MHT. For MAP based MHT, the single track Viterbi algorithms [16], [17] implement suboptimum sequential pruning, and are prone to loosing tracks for high clutter and missed detection scenarios, especially when extended to the multitrack problem.
In this paper we propose a new general Viterbi algorithm for multitarget tracking. For estimating K tracks, the trellis diagram of the measurements described in [18] is used to depict all track set hypotheses as trellis paths. MAP path costs are computed using Kalman filters and a priori track set probabilities. Because the hypothesis costs do not satisfy the Markov condition required for Viterbi algorithm pruning optimality, a new K track, list Viterbi algorithm is employed to effectively prune the number of evaluated hypotheses to a manageable level. Further hypothesis reduction is implemented through merging (as in [4]) and trellis truncation [8]. We term the resulting algorithm the Viterbi MHT algorithm. It is designed to avoid dropping tracks or track sets.