Linear-Time Direct Data Assignment Algorithm for Passive Sensor Measurements

Chaoxin He, Min Zhang, Guizhou Wu, Fucheng GuoSensors 2019 · DOI

TL;DR

This paper introduces a novel "Direct Data Assignment" (DDA) algorithm for multi-sensor, multi-target tracking using passive sensors. Unlike traditional methods that tackle data association in the measurement domain, DDA operates directly in the target state domain, significantly reducing computational complexity from exponential to linear with the number of sensors and targets. This efficiency gain, achieved by pre-setting candidate target locations, allows for comparable association accuracy with substantially reduced processing time.

What Problem Does This Paper Address?

Tracking multiple targets using passive sensors (like radar or sonar) presents a significant challenge known as data association. The core problem is determining which measurement from which sensor actually corresponds to which target. This becomes incredibly complex when dealing with an unknown number of targets, multiple sensors, and the possibility of spurious (false) measurements or missed detections. Traditional approaches often formulate this as a complex assignment problem (SDA) that suffers from a "combinatorial explosion," meaning the computational cost grows exponentially with the number of sensors and measurements, making them impractical for real-time applications with many targets.

Methods

The paper proposes a "Linear-Time Direct Data Assignment" (DDA) algorithm. The key innovation lies in shifting the problem's domain from measurements to target states. Instead of trying to associate every possible combination of measurements, DDA pre-defines a set of "candidate targets" within a region of interest. The algorithm then calculates a cost for each candidate target based on how well the available measurements align with its assumed position. The association is made by selecting the candidate target with the minimum cost. This approach avoids the combinatorial explosion by directly working with a fixed set of potential target locations. The algorithm iteratively refines the assignments, removing used measurements and candidate targets, leading to a linear time complexity.

Datasets

The paper does not introduce new datasets. Instead, it relies on simulated scenarios to evaluate the proposed DDA algorithm. These simulations are designed to mimic realistic conditions, including varying numbers of sensors and targets, different clutter densities, target separation, measurement noise levels, and detection probabilities.

Key Insights and Ideas

  • Domain Shift is Key: The most significant insight is that solving the data association problem in the target state domain rather than the measurement domain dramatically reduces computational complexity.
  • Pre-defined Candidates Avoids Explosion: By presetting candidate target locations, the algorithm sidesteps the exponential growth in possibilities inherent in traditional methods.
  • Cost-Based Assignment: Using a cost function to evaluate the likelihood of measurements originating from a candidate target provides a robust mechanism for association.
  • Thresholding for Spurious Measurements: The ability to use a measurement threshold to discard measurements far from candidate targets is crucial for handling noise and clutter, especially in low detection probability scenarios.
  • Efficiency Gains are Substantial: The linear time complexity means the algorithm scales much better with increasing numbers of sensors and targets compared to exponential approaches.

Key Results

The simulations demonstrate that the DDA algorithm achieves association accuracy comparable to existing state-of-the-art algorithms (like row-column and Lagrangian relaxation methods). Crucially, it achieves this with a significantly lower computational cost. For instance, in scenarios with multiple sensors, the DDA algorithm's run time was measured in seconds, while traditional methods took minutes or even hours. The paper shows that the DDA algorithm's performance is robust across various scenarios, including high clutter and poor target separation, and that its efficiency advantage is maintained.

Limitations and Future Work

  • Initialization of Candidate Targets: The performance of the DDA algorithm is influenced by the number and placement of candidate targets. While the paper suggests a grid-based initialization related to the Cramér-Rao Lower Bound (CRLB), the optimal initialization strategy for complex scenarios might require further investigation.
  • System Observability: The paper acknowledges that in cases of poor system observability (e.g., targets and sensors aligned linearly), target position might be theoretically unavailable. The proposed solution is to remove unobservable areas from the region of interest, which is a practical but potentially limiting approach.
  • Unresolved Targets: In challenging scenarios where targets are not well-separated in Angle of Arrival (AOA) measurements, the algorithm can still generate "unresolved targets," which might affect accuracy. Future work could explore methods to better handle such situations.

Summary updated

Abstract

To solve the problem of passive sensor data association in multi-sensor multi-target tracking, a novel linear-time direct data assignment (DDA) algorithm is proposed in this paper. Different from existing methods which solve the data association problem in the measurement domain, the proposed algorithm solves the problem directly in the target state domain. The number and state of candidate targets are preset in the region of interest, which can avoid the problem of combinational explosion. The time complexity of the proposed algorithm is linear with the number of sensors and targets while that of the existing algorithms are exponential. Computer simulations show that the proposed algorithm can achieve almost the same association accuracy as the existing algorithms, but the time consumption can be significantly reduced.
BibTeX
@inproceedings{he2019linear,
  author = {Chaoxin He and Min Zhang and Guizhou Wu and Fucheng Guo},
  title = {{Linear-Time Direct Data Assignment Algorithm for Passive Sensor Measurements}},
  booktitle = {Sensors},
  year = {2019},
  doi = {10.3390/s19245347},
}
Figure