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

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 greater than or equal to 3 lists of size n, k relaxations) the (approximately) m-best solut ions to an S-D assignment problem, The m-best S-D algorithm is applicable t o tracking problems where either the sensors are synchronized or the sensor s 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 pr ovide for an efficient implementation of a suboptimal multiple hypothesis t racking (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, Spe cifically, given line of sight (LOS) (i,e,, incomplete position) measuremen ts from S sensors, sets of complete position measurements are extracted, na mely, the 1st,2nd,...,mth best (in terms of likelihood) sets of composite m easurements are determined by solving a static S-D assignment problem. Util izing the joint likelihood functions used to determine the m-best S-D assig nment solutions, the composite measurements are then quantified with a prob ability of being correct using a JPDA-like (joint probabilistic data associ ation) technique, Lists of composite measurements from successive scans, al ong with their corresponding probabilities, are used in turn with a state e stimator in a dynamic 2-D assignment algorithm to estimate the states of mo ving 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) In-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 proble m, consisting of multiple time samples of LOS measurements originating from multiple (S = 7) synchronized high frequency direction finding sensors.