assignsd

S-D assignment using Lagrangian relaxation

Syntax

[assignments,cost,solutionGap] = assignsd(costmatrix)

[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap)

[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations)

[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations,algorithm)

Description

[assignments,cost,solutionGap] = assignsd(costmatrix) returns a table of assignments, assignments, of detections to tracks by finding a suboptimal solution to the S-D assignment problem using Lagrangian relaxation. The cost of each potential assignment is contained in the cost matrix, costmatrix. The algorithm terminates when the gap reaches below 0.01 (1 percent) or if the number of iterations reaches 100.

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.

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

The function also returns the solution gap, solutionGap, and the total cost of assignments, cost.

[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap) also specifies the desired maximum gap, desiredGap, between the dual and the feasible solutions as a scalar. 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] = assignsd(costmatrix,desiredGap,maxIterations) also specifies the maximum number of iterations, maxIterations.

[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations,algorithm) also specifies the assignment algorithm, algorithm.

Examples

Assign Detections to Tracks Using assignsd Algorithm

Use assignsd to perform strict assignment without index 1.

Not having dummy index means that no entity is left unassigned. Therefore, define the cost matrix to be equi-dimensional.

costMatrix = rand(6,6,6);

Initialize the fullmatrix to all Inf. The fullmatix is one size larger than the cost matrix in all dimensions.

fullMatrix = inf(7,7,7);

Set the inner matrix to costMatrix to force the assignments involving index 1 to have infinite cost.

fullMatrix(2:end,2:end,2:end) = costMatrix;
fullMatrix(1,1,1) = 0;
[assignments,cost,gapAchieved] = assignsd(fullMatrix,0.01,100);

Restore the actual indices.

assignments = assignments - 1

assignments = 6x3 uint32 matrix

   1   6   6
   2   4   3
   3   3   4
   4   1   2
   5   2   1
   6   5   5

Input Arguments

costmatrix — Cost matrix

real-valued M-by-N

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

desiredGap — Desired maximal gap

0.01 (default) | nonnegative scalar

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

Example: 0.05

Data Types: single | double

maxIterations — Maximum number of iterations

100 (default) | positive integer

Maximum number of iterations, specified as a positive integer.

Example: 50

Data Types: single | double

algorithm — Assignment algorithm

'auction' (default) | 'munkres' | 'jv'

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

assignments — Assignment of tracks to detections

P-by-N matrix

Assignments of tracks to detections, returned as a 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.

cost — Total cost of assignment solution

positive scalar

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

solutionGap — Solution gap

positive scalar (default)

Solution gap, returned as a positive scalar. The solution gap 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

• The Lagrangian relaxation method computes a suboptimal solution to the S-D assignment problem. The method relaxes the S-D assignment problem to a 2-D assignment problem using a set of Lagrangian multipliers. The relaxed 2-D assignment problem is commonly known as the dual problem, which can be solved optimally using algorithms like the Munkres algorithm. Constraints are then enforced on the dual solution by solving multiple 2-D assignment problems to obtain a feasible solution to the original problem. The cost of the dual solution and the feasible solution serves as lower and upper bounds on the optimal cost, respectively. The algorithm iteratively tries to minimize the gap between the dual and feasible solutions, commonly known as the dual gap. The iteration stops when the dual gap is below a desired gap or the maximum number of iterations have reached.

• When using the auction algorithm, the assignsd function uses the Heuristic Price Update algorithm to update the Lagrangian multipliers. When using the Munkres and JV algorithms, the function uses the Accelerated Subgradient Update algorithm.

• For cost matrices with well-defined solutions, such as passive association with high-precision sensors, the solution gap converges to within 0.05 (5 percent) in approximately 100 iterations.

• As the optimal solution is unknown, the solution gap can be non-zero even when the returned solution is optimal.

References

[1] Deb, S., Yeddanapudi, M., Pattipati, K., and 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.

[2] Blackman, Samuel, and Robert Popoli. Design and analysis of modern tracking systems. Norwood, MA: Artech House, 1999. (1999)

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

• In the generated code, assignsd returns an output with a fixed number of columns because it does not drop trailing singleton dimensions of variable-size arrays. In MATLAB, assignsd returns a variable-length output because it drops trailing singleton dimensions.

Version History

Introduced in R2018b