Assignment Algorithms For The Passive Sensor Data Association Problem

Somnath Deb; Krishna R. Pattipati; Yaakov Bar-Shalom; Robert B. Washburn

doi:10.1117/12.960357

5 September 1989 Assignment Algorithms For The Passive Sensor Data Association Problem

Somnath Deb, Krishna R. Pattipati, Yaakov Bar-Shalom, Robert B. Washburn

Proceedings Volume 1096, Signal and Data Processing of Small Targets 1989; (1989) https://doi.org/10.1117/12.960357
Event: SPIE 1989 Technical Symposium on Aerospace Sensing, 1989, Orlando, FL, United States

Abstract

This paper is concerned with the problem of associating measurements from multiple passive line-of-sight only sensors in the presence of clutter, missed detections and unknown number of targets. The measurement-target association problem is formulated as one of maximizing the joint likelihood function of the measurement partition. Mathematically, this formulation of the data association problem leads to a generalization of the multi-dimensional matching problem, which is known to be NP-complete ( of non polynomial complexity ) when the number of sensors S ≥ 3. Suboptimal algorithms are therefore of considerable importance. In this paper we present two suboptimal algorithms - a backtracking algorithm with a complexity of order 0(M in M), where M is the number of possible measurement-target associations, and a relaxation algorithm that successively solves a series of generalized two-dimensional assignment problems, with the worst case complexity of 0(3k n3 ), where n is the number of reports from each sensor, and k is the number of relaxation iterations. The performance of the backtracking algorithm is guaranteed to be much better than the "row-column" heuristic, which has complexity of 0(M). A nice feature of the relaxation approach is that the resulting primal and dual solutions provide a measure of how close the solution is to the (perhaps unknowable) optimal solution in terms of the duality gap. For the passive sensor data association problem, the duality gaps are typically less than 1%. We present comparisons between the two algorithms in terms of performance and time complexity in the context of passive sensor data-association problem involving three sensors. Both of the algorithms are tested on a wide variety of scenarios involving a wide range of target densities, measurement accuracy, and false alarm and missed-detection probabilities.

Citation Download Citation

Somnath Deb, Krishna R. Pattipati, Yaakov Bar-Shalom, and Robert B. Washburn "Assignment Algorithms For The Passive Sensor Data Association Problem", Proc. SPIE 1096, Signal and Data Processing of Small Targets 1989, (5 September 1989); https://doi.org/10.1117/12.960357

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available