Introduction

Multitarget tracking is an important and challenging problem in radar signal processing [1] which has received intense attention for well over two decades now. Starting from a time evolving set of noisy measurements from detected targets and false alarms, the problem is to associate the detections over time to form multiple target tracks. Some early work focussed on associating time evolving target measurement data, that includes both real detections and false alarms, to one or more target tracks using a likelihood function formulation. Smith and Buechler [2] selected the single track that maximized a likelihood cost - an approach which Morefield [3] extended to maximum likelihood (ML) estimation of multiple tracks. Realizing the need to incorporate prior detection and false alarm probabilities, Singer et al. [4] and Reid [5] developed, respectively, single track and multitrack Bayesian estimators. Both ML and Bayesian multitrack estimators require evaluation of the cost of every possible (candidate) set of tracks through the measurements. The number of candidate track sets increases exponentially with time since at a given time each candidate track can extend to any of the next measurements. To reduce this computation burden, proposed methods typically only evaluate ``feasible tracks'' in ``gating volumes'', i.e. only measurements which are in some sense close to a predicted measurement are considered when extending a candidate track to the next measurement time. A result of this approach is that the track which is optimum over the entire processing interval may not be found, and in particular in sequential track estimation valid tracks can be dropped after track-to-measurement association fails for several measurement times.

In [6], an alternative approach to computation reduction is proposed. Therein, a K-path extension of the Viterbi algorithm [7] is used to find the best K nonintersecting tracks according to a deterministic energy cost function. A trellis diagram is defined where at each stage (measurement time) states represents all combinations of measurements taken K at a time. Paths through the trellis represent K track sets. The K-path Viterbi algorithm is used to prune the number of paths through the trellis that must be considered, thereby reducing computation. Globally optimum solutions are computed, thus avoiding the problems associated with feasible tracks and gating volumes. Use of this K-path extension of the Viterbi algorithm is predicated on a ``finite state machine structure'' or ``Markov condition'' in the cost function, which is satisfied with the particular deterministic energy cost function used in [6]. However, an ML or Bayesian cost function will not satisfy this requirement since track measurements are correlated throughout the history of a track. (One way to think of this is that, in implementing an ML or Bayesian multitrack estimator, Kalman filters are used in the cost computation to generate measurement innovations. These Kalman filters are recursive and thus have infinite memory.) As a result direct use of K-path Viterbi for multitarget tracking is limited.

For the data communication application, another modification of the Viterbi algorithm, termed list Viterbi [8], has been proposed. This algorithm provides, at each stage through the trellis, a list of best paths through the trellis diagram. In [9], a novel K-track, L list Viterbi algorithm approach was proposed for multitarget tracking. By pruning the trellis to a list of best K-tracks instead of to a single best K-track, this approach overcomes the shortcomings of K-path Viterbi tracking [6] while controlling computation without resorting to the use of gating volumes. It also provides a ranked list of K-track estimates which may, according to the optimality criterion, have very similar costs but represent dissimilar trajectories. Such a list can be valuable for post processing classification and/or data fusion.

The algorithm described in [9]: is based on a Maximum Likelihood (ML) cost function; assumes the number of tracks, K, is known; and requires that the probability of target detection is unity. In this paper we employ a more effective Bayesian cost, describe an algorithm for joint estimation of K and the tracks, and account for missed detections.

Below we first introduce the K target tracking problem. We then develop a Bayesian cost function for estimating K and the tracks, and then marginalize over the tracks to derive an alternative estimator of K alone. The trellis diagram representation of the problem is then constructed, and followed by description of the K-path L-list Viterbi algorithm for Bayesian multiple track estimation. Finally, we illustrate this algorithm with several numerical examples.