Trellis Diagram Formulation

Consider the trellis diagram in Figure 4 which depicts the possible progressions of sequences of location measurements over time for K=1. Each stage of the trellis corresponds to a measurement time. For K=1, at the m^th stage there are J_m +1 states, one for each measurement and one to account for a missed target. A branch is a connection from a state at stage m-1 to another state at stage m. At time n, the L_n^' candidate tracks $\mbox{\boldmath$\theta$ }_n^l ; l=1,2, \cdots, L_n^'$correspond to the L_n^' possible paths through the trellis from stage 1 to n. For each track, we assign an incremental cost to each branch. For example, for the l^th candidate track $\mbox{\boldmath$\theta$ }_n^l$, the branch cost from stage m-1 to m (i.e. from state j_m-1 (l) to j_m (l)) is $\lambda_m ( \mbox{\boldmath$\theta$ }_n^i )$. It is important to note that since for each candidate track a Kalman filter (which has memory back to the 1^st stage through the Kalman states) is being used to compute the incremental costs, the cost associated with a branch depends on what track is being considered. That is, each branch has multiple costs assigned to it, one for each track through it. The cost of the path $\mbox{\boldmath$\theta$ }_n^l$ is the sum of its branch costs. The Bayesian track estimation problem is now one of finding the minimum-cost path through this trellis.

  

Figure 1: Trellis Diagram for K=1.

For K track estimation, each state of the trellis in Figure 4 represents a set of K measurements and/or missed measurements. So, for stage m with J_m measurements, there are

$$M_m = \sum_{j=0}^{K} \left( \begin{array}{c} {J_m} \\ j \end{array} \right)$$ (21)

states. Each branch from stage m-1 to m has a set of K!/(K-T_mⁱ )! permutations associated with it, specifying the possible orders in which the K measurements and/or missed measurements are used. Now for each candidate K-track set, the incremental cost assigned to a branch is the sum of the costs of K candidate tracks. So, for candidate K-track set $\mbox{\boldmath$\tau$ }_n^i$, the branch cost from stage m-1 to m is $\Lambda_m ( \mbox{\boldmath$\tau$ }_n^i )$. As with the K=1 case, the Bayesian K-track estimation problem is now one of finding the minimum-cost path through this trellis.