In this paper we develop a new general Viterbi algorithm for multitarget
tracking. A standard Multiple Hypothesis Tracking (MHT) formulation, based on
Maximum A Posterior (MAP) estimation, is considered for optimally associating
measurement data over time to form estimates of the multiple tracks. For
estimating
K tracks, a trellis diagram of the measurements 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. A new
K-track, List-Viterbi algorithm is then employed to effectively prune the
number of evaluated hypotheses to a manageable level. Further hypothesis
reduction is implemented through path merging and trellis truncation.
The resulting
Viterbi MHT algorithm is sequential. It is
very flexible in that it can handle missed detections, false alarms and
number-of-track estimation. It provides an ordered list of best track sets,
which can be useful in subsequent data fusion. Compared to MHT algorithms
which prune candidate track sets using ``gating volumes'', the new Viterbi MHT
is less prone to loosing tracks.
This research was supported by ONR under Grant N00014-98-1-0892.
