Is there any tracking algorithm utilizing 'assignsd'?

trackerGNN utilizes the assignment algorithms such as matchpairs, Munkres, Jonker-Volgenant, Auction which solve 2-D assignment problem. Also, we have Custom assignment algorithm option. But, I don't think it allows me to do multi-dimensional assignment in my way, because the cost matrices are arranged in 2-D. trackFuser also use GNN by assuming each tracks are coming from a single source by reducing dimension in trackFuser --> Core Algorithm --> distance().

trackerTOMHT utilizes the assignTOMHT algorithm which does only gating as far as I understand.

In addition, we have another method for assignment assignsd or assignkbestsd which is introduced in

1. Deb, S., Yeddanapudi, M., Pattipati, K., and Bar-Shalom, Y. (1997). A generalized SD assignment algorithm for multisensor-multitarget state estimation.

However, even we have multi-sensor or multi track source, none of above algorithms calls assignsd or assignkbestsd. Is there any use case for S-D assignment problem? Does any tracking algorithm do multi-dimensional assignment at once not pretending the problem is 2-D? If not, why?

Answer 1

[Prashant Arora]

Hi Said,

You are right that assignment between tracks and measurements/tracks from multiple sources can be formulated as a S-D assignment problem. Here the first dimension will refer to "tracks", and the subsequent dimensions refer to measurements from S-1 sensors. The S-D assignment has much higher complexity than 2-D assignment problems. I believe the complexity grows linearly with maximum number of iterations and the number of dimensions. It is also a suboptimal algorithm and often requires parallel computing resources when number of sensors > 3.

The tracking algorithms (trackerGNN, trackerJPDA, and trackerTOMHT) do not use S-D assignment as of R2023a. These trackers use an "iterated-corrector" approach for multi-sensor fusion, which is a popular method in literature.

1. trackerGNN uses 2-D assignment for each sensor. Technically, it is possible to use the best solution to S-D assignment for a GNN tracker at the cost of increased computation and possible sub-optimality at each sensor.
2. trackerJPDA generates feasible events from 2-D assignment problems to compute data association probabilities. The literature is sparse for generating feasible events using S-D assignment problems. The number of feasible events from a S-D assignment can be really high, hurting the efficiency of JPDA algorithm. A possible alternate can be to use m-best solutions to S-D assignment problem for data association probabilities. However, it will again be much slower as compared to iterated 2-D problems for practical applications.
3. trackerTOMHT generates all assignment hypothesis (based on gating thresholds) at the track-level. It does not solve a global assignment problem for that. Instead, it first generates track-level assignment hypothesis, which are then used to define global hypothesis. A hypothesis-oriented MHT (HOMHT) may use 2-D or S-D assignment to generate global hypothesis.

The S-D assignment is also popular for "static fusion". "Static fusion" aims to associate detections from multiple synchronous sensors to each other. See some examples here:

Static fusion of synchronous sensor detections - MATLAB (mathworks.com)

Tracking Using Distributed Synchronous Passive Sensors - MATLAB & Simulink (mathworks.com)

Tracking Using Bistatic Range Detections - MATLAB & Simulink (mathworks.com)

Object Tracking Using Time Difference of Arrival (TDOA) - MATLAB & Simulink (mathworks.com)

If you would like to use S-D assignment for multi-sensor object tracking, consider using building blocks offered by the toolbox. These include:

1. Tracking filters (trackingEKF, trackingUKF etc.) - They offer estimation + association likelihood/distance methods.
2. S-D assignment algorithms (assignsd, assignkbestsd)
3. Track management logics (trackHistoryLogic, trackScoreLogic) - They offer ways to know when to confirm, initialize and delete tracks.
4. Filter initialization functions (initcvekf, initcaekf etc.) - They offer ways to initialize a filter from a measurement.

Hope this helps.

Thanks,

Prashant

[Said Kemal]

Hi again, I revisited your comment and wanted to ask one more question. You have mentioned about computational complexity of s-D assignment methods as well as their sub-optimality.

1. Are not s-D assignment techniques able to achieve more accurate results in dense and complex scenarios?
2. If s-D assignment techniques are more accurate but more computationally complex, is it more trouble than it is worth?

Thanks for your valuable comments.