# assignkbestsd

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

## Syntax

``[assignments,cost,solutionGap] = assignkbestsd(costmatrix)``
``[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k)``
``[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap)``
``[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap,maxIterations)``
``[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap,maxIterations,algorithm)``

## Description

````[assignments,cost,solutionGap] = assignkbestsd(costmatrix)` returns a table of `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`.```
````[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k)` also specifies the number, `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.```
````[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap)` also specifies the desired maximum gap, `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. ```

````[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap,maxIterations)` also specifies the maximum number of iterations allowed. The `desiredGap` and `maxIterations` arguments define the terminating conditions for the S-D algorithm.```
````[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap,maxIterations,algorithm)` also specifies the `algorithm` for finding the assignments.```

## Examples

collapse all

Find the first 5 best assignments of the S-D assignment problem. Set the desired gap to 0.01 and the maximum number of iterations to 100.

`load passiveAssociationCostMatrix.mat`

Find the 5 best solutions.

`[assignments,cost,solutionGap] = assignkbestsd(costMatrix,5,0.01,100)`
```assignments=5×1 cell array {2x3 uint32} {3x3 uint32} {3x3 uint32} {3x3 uint32} {3x3 uint32} ```
```cost = 5×1 -34.7000 -31.7000 -29.1000 -28.6000 -28.0000 ```
```solutionGap = 5×1 0 0.0552 0.0884 0.1075 0.1964 ```

## Input Arguments

collapse all

Cost matrix, specified as an n-dimensional array where ```costmatrix(i,j,k ...)``` defines the cost of the n-tuple `(i,j,k, ...)` in an assignment. The index '1' on all dimensions in `costmatrix` represents a 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.

Data Types: `single` | `double`

Number of best solutions, specified as a positive integer.

Data Types: `single` | `double`

Desired maximum gap between the dual and feasible solutions, specified as a nonnegative scalar.

Example: `0.05`

Data Types: `single` | `double`

Maximum number of iterations, specified as a positive integer.

Example: `50`

Data Types: `single` | `double`

Assignment algorithm for solving the 2-D assignment problem, specified as `'munkres'` for the Munkres algorithm, `'jv'` for the Jonker-Volgenant algorithm, or `'auction'` for the Auction algorithm.

Example: `'jv'`

## Output Arguments

collapse all

Assignments of tracks to detections, returned as a K-element cell array. Each cell is an P-by-N list of assignments. Assignments of the type `[1 1 Q 1]` from a four-dimensional cost matrix can be seen as a `Q-1` entity from dimension 3 that was left unassigned. The cost value at `(1,1,Q,1)` defines the cost of not assigning the (Q-1)th entity from dimension 3.

Total cost of solutions, returned as a K-element vector where K is the number of best solutions. Each element is a scalar value summarizing the total cost of the solution to the assignment problem.

Data Types: `single` | `double`

Solution gap, returned as a positive-valued K-element array where K is the number of best solutions. Each element is the duality gap achieved between the feasible and dual solution. A gap value near zero indicates the quality of solution.

Data Types: `single` | `double`

## Algorithms

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

## References

[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.

## Version History

Introduced in R2018b