Comparison of assignment algorithms with applications to the passive sensor data association problem

Publisher Website
Google Scholar
Abstract
The problem of tracking multiple targets with passive electronic or sonar sensors requires at least three sensors for correct measurement-target association. Mathematically, the measurement -target association problem leads to a generalization of the multi-dimensional assignment problem, which is known to be NP-complete when the number of sensors S /spl ges/ 3, i.e., the complexity of an optimal algorithm increases exponentially with the size of the problem. We consider a three sensor case and solve the 3-dimensional assignment problem using a Lagrangian relaxation algorithm that successively solves a series of generalized two-dimensional assignment subproblems with the worst case complexity of O(k n/sup 3/), where n is the number of reports from each sensor, and k is the number of dual iterations. This paper investigates the computational efficiency of three recently developed assignment algorithms - RELAX II, generalized Auction and generalized Signature methods --- as part of the dual relaxation method. The computational efficiency of the algorithms is evaluated for various target spacing/sensor accuracy ratios, false alarm and missed detection probabilities. It is concluded that the generalized Auction is 4-5 times faster than either RELAX-II or the generalized signature method.