Autoware.Auto
|
|
We require a method to associate distinct data together.
This can include multiple observations, but the main use case is to associate observations with tracks, that is, tracked objects.
The Hungarian algorithm was chosen instead of the Global Nearest Neighbors (GNN) algorithm because the GNN algorithm assumes a euclidean cost function, whereas the Hungarian algorithm can take in arbitrary costs.
The primary trade-off here is that the Hungarian algorithm is O(N^3) instead of O(N log N) for GNN.
This package is a fairly standard implementation of the O(N^3 ) Hungarian algorithm (see external links), however we have made some minor changes in book-keeping to save some work:
In addition, our implementation of the Hungarian algorithm can support the unbalanced assignment problem and missing weights (that is, illegal assignments).
The following functionality for a matrix class is used:
set_weight()
set_weight()
for a given index pair occurs only onceassign()
fails and returns false, it is assumed that the user will then need to check for an UNASSSIGNED
assignmentBasic usage:
Inputs:
Outputs:
Impossible assignments are detected by hitting loop bounds. In some cases, we can also check before doing computation if assignment is impossible (e.g. if a column is completely empty).
In the above case, the full algorithm will run, but assign()
will return false. This is a signal to the user that they need to check the result of get_assignment()
for the value UNASSIGNED
For indexing (e.g. set_size()
, set_weight()
), exceptions can be thrown due to indexing errors.
For some inner loops, certain conditions should be theoretically guaranteed (e.g. maximum size of augmented path, maximum number of iterations for loops, etc.).
If these conditions are not met, an exception will be thrown.
TBD by a security specialist.
N/A