Multihypothesis Viterbi Data Association: Algorithm Development and Assessment

Two algorithms for tracking in clutter, based on the Viterbi algorithm are presented: single-target Viterbi data association (ST-VDA) and multihypothesis VDA (MH-VDA). MH-VDA is designed specifically for multiple-target tracking (MTT), although ST-VDA still achieves good performance on MTT problems. The basic philosophy of both methods is to set up an optimisation problem for the sequence of measurement-to-target associations rather than directly seeking the target state estimates. The joint optimisation problem for the data association sequence is decomposed into a sequence of scalar optimisation problems by means of an approximate forward dynamic programming recursion to which the Viterbi algorithm is applicable. Once the data association problem is solved, the target state estimates can be retrieved by backtracking. The operation of the algorithms is easily visualised as a search on a trellis for the optimal path. For ST-VDA, nodes in the trellis correspond to measurements. For MH-VDA, nodes correspond to multitarget data association hypotheses. Conventional measurement gating is extended to work within this context. Results from simulations that compare the performance of ST-VDA and MH-VDA with four, standard, zero-scan-back tracking approaches are given. The performance assessment includes metrics for track loss and track swaps in a multiple crossing target context. The Viterbi data association (VDA) algorithms are shown to outperform the alternative algorithms. In particular the ST-VDA is found to have the best track swap performance, while MH-VDA has the lowest track loss figure. Average state estimation errors for both VDA algorithms are only about 10% larger than a Kalman filter with known data associations. While both variants of VDA are essentially batch processing approaches, the simulation results indicate that the algorithms can be implemented with a fixed processing lag of only a few scans without significant loss in performance.