Main Content

S-D assignment using Lagrangian relaxation

`[`

returns a table of assignments, `assignments`

,`cost`

,`solutionGap`

] = assignsd(`costmatrix`

)`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`

.

`[`

also
specifies the desired maximum gap, `assignments`

,`cost`

,`solutionGap`

] = assignsd(`costmatrix`

,`desiredGap`

)`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.

`[`

also
specifies the maximum number of iterations, `assignments`

,`cost`

,`solutionGap`

] = assignsd(`costmatrix`

,`desiredGap`

,`maxIterations`

)`maxIterations`

.

`[`

also
specifies the assignment algorithm, `assignments`

,`cost`

,`solutionGap`

] = assignsd(`costmatrix`

,`desiredGap`

,`maxIterations`

,`algorithm`

)`algorithm`

.

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.

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