Trellis Diagram Formulation

To derive an equivalent cost from which a time recursive trellis structure representation can be developed, take the negative natural log of (14). The following equivalent cost is obtained:

$$\Lambda^n \left( K, \mbox{\boldmath$\tau$ }_n^{i(K)} \right)... ..._{m=1}^{n} \Lambda_m ( K, \mbox{\boldmath$\tau$ }_n^{i(K)} ) ,$$ (16)

where the time m incremental cost is

$$\Lambda_m ( K, \mbox{\boldmath$\tau$ }_n^{i(K)} ) = \lambda_... ...}^{K} \lambda_m ( \mbox{\boldmath$\theta$ }_n^{l_p (i(K))} ) ,$$ (17)

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

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

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

For now, assume that K is known. Assume that tracks can not share detections, and that missed detections (as many as K at time m) are possible. With these assumptions we define a trellis representation of all hypothesized K track sets. This trellis is depicted in Figure 1. At each stage (time), each state represents a set of K measurements and/or missed detections. (This is the trellis proposed by Wolf, et al. [9])

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)$$ (19)

states (nodes). A branch is a connection from a state at some time m-1 to one at time m. Each branch from stage m-1 to m has a set of K !/(K_max - J_m + F_m^i(K) )!permutations associated with it, specifying the possible orders in which the K measurements and/or missed detections represented by the state at stage m are used.⁵ Each permutation corresponds to one or more hypothesized K-track set.

Each incremental cost assigned to a branch is the sum of a prior cost $\lambda_m ( K, \mbox{\boldmath$\tau$ }_n^{i(K)} )$ and the costs of the K hypothesized tracks. So, for hypothesized K-track set $\mbox{\boldmath$\tau$ }_n^{i(K)}$, the branch cost from stage m-1 to m is $\Lambda_m ( \mbox{\boldmath$\tau$ }_n^{i(K)} )$. Note that the problem of identifying the best K-track set is now one of finding the minimum-cost path through this trellis.