A NEW RELAXATION ALGORITHM AND PASSIVE SENSOR DATA ASSOCIATION

This paper is concerned with the static problem of associating measurements at a given time from three angle-only sensors in the presence of clutter, missed detections, and an 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 three-dimensional (3-D) assignment (matching) problem, which is known to be NP hard; that is, the complexity of an optimal algorithm increases exponentially with the size of the problem, since no known polynomial time algorithm exists. Suboptimal algorithms of quantifiable accuracy are therefore of considerable importance. The new solution to the optimization problem developed in this paper is a Lagrangian relaxation technique that successively solves a series of generalized two-dimensional (2-D) assignment problems, with the worst case complexity of O(3kn3), where k is the number of relaxation iterations and n is the number of reports from each sensor. The dual optimization problem is solved via an acclerated subgradient method. A useful feature of the relaxation approach is that the resulting dual optimal cost is a lower bound on the feasible cost and, hence, provides a measure of how close the feasible solution is to the (perhaps unknowable) optimal solution. For the passive sensor data association problem, the feasible solution costs are typically within 1% of their corresponding dual optimal costs. A comparison of our relaxation algorithm to the optimal branch-and-bound and suboptimal row-column algorithms demonstrates that our algorithm is superior to these alternative approaches in terms of computational complexity and/or measurement-target association accuracy. Finally, the algorithm is illustrated via several application examples.