LL Logo




Trellis Structure Approach for Multitarget Tracking

Richard Perry, Anand Vaddiraju, and Kevin Buckley
Villanova University
800 Lancaster Pike
Villanova, PA 19085
tel: (610) 519-5658
email: buckley@ece.vill.edu

Abstract In this paper we address sequential multitarget tracking for radar applications. Specifically, we consider location measurement data association for multiple track formation, focusing on missed detection and false alarm problems, track initiation and termination, and number-of-track estimation (i.e., model order selection). The algorithmic approach we propose is sequential and very flexible in that it can handle the issues listed above, while employing various performance cost functions and managing computation cost by pruning based on track feasibility. The output of the algorithm can be either a single set of best K tracks (where K is estimated), or a list of L best sets of K tracks. The latter being useful, for example, in data fusion where information from other platforms can be used to select one set from the list.

The approach is based on a trellis diagram which depicts the possible progressions of sequences of location measurements over time. Each stage of the trellis corresponds to a measurement time. At a given stage, for each candidate K, each state corresponds to a set of K measurements. The algorithm determines a list of feasible K-tracks as a list of paths through the trellis. For this paper, paths are evaluated according to a maximum likelihood cost function, where the incremental costs in progressing from stage to stage are computed as branch costs from states to states, so that branch costs are derived from track innovation processes generated by Kalman filters. Because of the nature of the relationship between measurements and innovations, the Viterbi algorithm can not be used to prune (eliminate from consideration) trellis paths. This is because neither the track innovation nor state processes are Markov. However, a generalization of the Viterbi algorithm termed the list Viterbi algorithm can be used to prune, at each stage and state, all but a subset of tracks called the feasibility tracks.

This research was supported by ONR under Grant #N00014-98-1-0892.

Presentation (pdf format)



LL Logo Disclaimer

Direct comments and questions to: webmaster@ll.mit.edu

MIT Lincoln Laboratory. All rights reserved.