Trellis Diagram Formulation

To derive an equivalent cost from which a time recursive trellis structure representation can be derived, take the negative natural log of (6), ignoring $p \left( {\cal Z}^n \right)$. For the i^th track set, the following equivalent MAP optimization problem is obtained:

$$\min_{ \mbox{\boldmath$\tau$ }_n^i } \; \; \; \; \; \Lambda^... ...ht) = \sum_{m=1}^{n} \Lambda_m ( \mbox{\boldmath$\tau$ }_n^i )$$ (12)

where the time m incremental cost is

$$\Lambda_m ( \mbox{\boldmath$\tau$ }_n^i ) = \lambda_m ( \mbo... ..._{p=1}^{K} \lambda_m ( \mbox{\boldmath$\theta$ }_n^{l_p (i)} )$$ (13)

where $\lambda_m ( \mbox{\boldmath$\tau$ }_n^i ) = \ln \{ p\left( \mbox{\boldmath$\tau$ }_n^i \right) \}$and the p^th track incremental cost at time m is

$$\lambda_m ( \mbox{\boldmath$\theta$ }_n^{l_p (i)} ) \frac{1}{2} \ln ( \det ({\bf S}_{m,j_m ( l_p (i) )})) + \frac{D}{2} \ln (2 \pi )$$ = (14)

$$\frac{1}{2} {\bf v}_{m,j_m ( l_p (i) )}^T {\bf S}_{m,j_m ( l_p (i) )}^{-1} {\bf v}_{m,j_m ( l_p (i) )} \; .$$ +

For K track estimation, under the assumptions that tracks can not share detections, and that missed detections (as many as K) are possible, we choose a trellis, depicted in Figure 1, in which each state represents a set of K measurements and/or missed measurements. (This is the trellis used in [18].) 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)$$ (15)

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 represented by the state at stage m are used⁵. Now for each hypothesized K-track set, the incremental cost assigned to a branch is the sum of the costs of K hypothesized tracks. So, for hypothesized 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 )$. The MAP K-track estimation problem is now one of finding the minimum-cost path through this trellis.

  

Figure 1: Trellis Diagram for general K.