m-Best S-D Assignment Algorithm for Tracking

January 2001 No Comments

m-Best S-D Assignment Algorithm with Application to Multitarget Tracking.

Author: Popp, R., Pattipati, K. & Bar-Shalom, Y.

Abstract

In this paper we describe a novel data association algorithm, termed m-best S-D, that determines in O(mSkn^3) time (m assignments, S >=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.

Conclusion

In this paper we described an efficient and novel approach to data association based on the m-best S-D assignment algorithm. We demonstrated the feasibility of the m-best S-D assignment algorithm for track formation and maintenance using a passive sensor multitarget tracking problem (operating in a type III configuration [5]). We showed how to efficiently (and nonenumeratively) extract sets of complete position “composite measurements” and determine their probabilities using a JPDA-like technique (based on the likelihoods associated with the feasible joint events corresponding to the (static) m-best S-D assignment solutions). We then used the series of composite measurement lists, along with their corresponding probabilities, in a dynamic 2-D assignment algorithm to estimate the states of the moving targets over time. We formulated the 2-D assignment cost coefficients using a likelihood function that incorporates the “true” composite measurement probabilities. Using a simulated passive sensor multitarget tracking problem, we showed that the m-best S-D assignment algorithm can perform well. Another significance of this work is that the m-best S-D assignment algorithm (in a sliding window mode) provides for an efficient implementation of a suboptimal MHT algorithm by obviating the need for a brute force enumeration of an exponential number of joint hypotheses.

Citation

Popp, R., K. Pattipati and Y. Bar-Shalom, “m-best SD Assignment Algorithm with Application to Multitarget Tracking,” IEEE Trans. Aerospace and Electronic Systems, vol. 37, no. 1, pp. 22-39, Jan 2001.