In this paper we describe a novel data association algorithm, termed m-best S-D, that determines in O(mSkn/sup 3/) time (m assignments, S/spl ges/3 lists of size n, k relaxations) the (approximately) m-best solutions to an S-D assignment problem. The m-best S-D algorithm is applicable to tracking problems where either the sensors are synchronized or the sensors and/or the targets are very slow moving. The significance of this work is that the m-best S-D assignment algorithm (in a sliding window mode) can provide for an efficient implementation of a suboptimal multiple hypothesis tracking (MHT) algorithm by obviating the need for a brute force enumeration of an exponential number of joint hypotheses. We first describe the general problem for which the m-best S-D applies. Specifically, given line of sight (LOS) (i.e., incomplete position) measurements from S sensors, sets of complete position measurements are extracted, namely, the 1st, 2nd, ..., mth best (in terms of likelihood) sets of composite measurements are determined by solving a static S-D assignment problem. Utilizing the joint likelihood functions used to determine the m best S-D assignment solutions, the composite measurements are then quantified with a probability of being correct using a JPDA-like (joint probabilistic data association) technique. Lists of composite measurements from successive scans, along with their corresponding probabilities, are used in turn with a state estimator in a dynamic 2-D assignment algorithm to estimate the states of moving targets over time. The dynamic assignment cost coefficients are based on a likelihood function that incorporates the "true" composite measurement probabilities obtained from the (static) m-best S-D assignment solutions. We demonstrate the merits of the m-best S-D algorithm by applying it to a simulated multitarget 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 :

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


    Contributors:


    Publication date :

    2001-01-01


    Size :

    554544 byte




    Type of media :

    Article (Journal)


    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


    Multitarget tracking algorithm performance evaluation

    Zheng, H. Farooq, M. Main, R. R. | British Library Conference Proceedings | 1999


    Continuous 2-D assignment for multitarget tracking with rotating radars

    Habtemariam, B. / Tharmarasa, R. / McDonald, M. et al. | IEEE | 2015