In this paper we describe a novel data association algorithm and parallelization, termed m-best SD, that determines in O(mSkn/sup 3/) time (m assignments, S lists of size n, k relaxations) the m-best solutions to an SD assignment problem. The significance of this work is that the m-best SD assignment algorithm (in a sliding window mode) provides for an efficient implementation of an (S-1)-scan Multiple Hypothesis Tracking (MHT) algorithm by obviating the need for a brute force enumeration of an exponential number of joint hypotheses. Initially, given a static SD assignment problem, sets of complete position measurements are extracted, namely, the 1-st, 2-nd, ..., m-th best (in terms of likelihood) sets of composite measurements are determined based on the line of sight (LOS) (i.e., incomplete position) measurements. Using the joint likelihood functions used to determine the m-best SD assignment solutions, the composite measurements are then quantified with a probability of being correct using a JPDA-like technique. Lists of composite measurements, along with their corresponding probabilities, are then used in turn with a state estimator in a dynamic 2D assignment algorithm to estimate the states of the moving targets over time. The 2D assignment cost coefficients are based on a likelihood function that incorporates the true composite measurement probabilities obtained from the (static) m-best SD assignment solutions. We demonstrate m-best SD on a simulated passive sensor track formation and maintenance problem, consisting of multiple time samples of LOS measurements originating from multiple (S=7) synchronized high frequency direction finding sensors.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    An adaptive m-best SD assignment algorithm and parallelization for multitarget tracking


    Contributors:


    Publication date :

    1998-01-01


    Size :

    1846377 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    An Adaptive m-best SD Assignment Algorithm for Parallelization for Multitarget Tracking

    Popp, R. / Pattipati, K. / Bar-Shalom, Y. et al. | British Library Conference Proceedings | 1998


    m-best S-D assignment algorithm with application to multitarget tracking

    Popp, R.L. / Pattipati, K.R. / Bar-Shalom, Y. | IEEE | 2001



    Parallelization of a multiple model multitarget tracking algorithm with superlinear speedups

    Popp, R.L. / Pattipati, K.R. / Bar-Shalom, Y. et al. | IEEE | 1997