An Efficient Implementation of a Batch-Oriented, Multitarget, Multidimensional Assignment Tracking Algorithm with Application to Passive Sonar

Abstract : This research investigates the use of two versions of a batch-oriented, multidimensional assignment tracking algorithm to examine target crossings that are on the order of 100 scans in duration. The simulations use outputs in one dimension (bearings only) from a passive sonar line array. Linear programming relaxation is used to solve the assignment problem for an exhaustive set of measurement-to-track N-tuple costs along the batch. The implementation of the cost evaluations used for the objective function is analyzed for efficiency. The objective function is minimized subject to certain constraints. The constraints are set up such that each measurement-to-track assignment is exclusive per scan along the batch. The algorithm is generic and can be extended to N dimensions (ND). Missing measurements are accounted for as part of the assignment model. An efficient version of the ND assignment is developed to increase the batch length for acceptable runtime performance. Batch lengths of up to 15 scans, equivalent to a 16D assignment, have been developed and tested on various levels of clutter data. Results are tested via 100-trial Monte Carlo simulations for the two algorithms as applied to the long-duration passive sonar crossing targets case with various clutter density and filter settings.