Main Content

K-best S-D solution that minimizes total cost of assignment

`[`

returns a table of `assignments`

,`cost`

,`solutionGap`

] = assignkbestsd(`costmatrix`

)`assignments`

of detections to tracks by finding the
best S-D solution that minimizes the total cost of the assignments. The algorithm uses
Lagrangian relaxation to convert the S-D assignment problem to a corresponding 2-D
assignment problem and then solves the 2-D problem. The cost of each potential assignment is
contained in the cost matrix, `costmatrix`

.

`costmatrix`

is an n-dimensional cost matrix
where `costmatrix(i,j,k ...)`

defines the cost of the n-tuple ```
(i,j,k,
...)
```

in assignment. The index '1' on all dimensions in
`costmatrix`

represents dummy measurement or a false track and is used to
complete the assignment problem. The index 1, being a dummy, can be a part of multiple n-tuples.
The index can be assigned more than once. A typical cost value for
`costmatrix(1,1,1,1, ...)`

is 0.

The function also returns the solution gap, `solutionGap`

, and the
cost of assignments, `cost`

.

`[`

also specifies the number, `assignments`

,`cost`

,`solutionGap`

] = assignkbestsd(`costmatrix`

,`k`

)`k`

of *K*-best S-D
solutions. The function finds *K* optimal solutions that minimize the total
cost. First, the function finds the best solution. Then, the function uses the Murty
algorithm to generate partitioned cost matrices. Finally, the function obtains the remaining
*K* - 1 minimum cost solutions for each partitioned matrix.

`[`

also specifies the desired maximum gap, `assignments`

,`cost`

,`solutionGap`

] = assignkbestsd(`costmatrix`

,`k`

,`desiredGap`

)`desiredGap`

, between the dual
solution and the feasible solution. The gap controls the quality of the solution. Values
usually range from 0 to 1. A value of 0 means the dual and feasible solutions are the same.

`[`

also specifies the maximum number of iterations allowed. The `assignments`

,`cost`

,`solutionGap`

] = assignkbestsd(`costmatrix`

,`k`

,`desiredGap`

,`maxIterations`

)`desiredGap`

and `maxIterations`

arguments define the terminating conditions for the
S-D algorithm.

`[`

also specifies the `assignments`

,`cost`

,`solutionGap`

] = assignkbestsd(`costmatrix`

,`k`

,`desiredGap`

,`maxIterations`

,`algorithm`

)`algorithm`

for finding the assignments.

All numeric inputs can be single or double precision, but they all must have the same precision.

[1] Popp, R.L., Pattipati, K., and Bar
Shalom, Y. *"M-best S=D Assignment Algorithm with Application to Multitarget
Tracking"*. IEEE Transactions on Aerospace and Electronic Systems, 37(1), 22-39.
2001.

[2] Deb, S., Yeddanapudi, M.,
Pattipati, K., & Bar-Shalom, Y. (1997). *"A generalized SD assignment algorithm
for multisensor-multitarget state estimation"*. IEEE Transactions on Aerospace
and Electronic Systems, 33(2), 523-538.