Dynamically adaptable m-best 2-D assignment algorithm and multilevel parallelization

In recent years, there has been considerable interest within the tracking c ommunity in an approach to data association based on the m-best two-dimensi onal (2-D) assignment algorithm. Much of the interest has been spurred by i ts ability to provide various efficient data association solutions, includi ng joint probabilistic data association (JPDA) and multiple hypothesis trac king (MIT). The focus of this work is to describe several recent improvements to the m- best 2-D assignment algorithm. One improvement is to utilize a nonintrusive 2-D assignment algorithm switching mechanism, based on a problem sparsity threshold. Dynamic switching between two different 2-D assignment algorithm s, highly suited for sparse and dense problems, respectively, enables more efficient solutions to the numerous 2-D assignment problems generated in th e m-best 2-D assignment framework. Another improvement is to utilize a mult ilevel parallelization enabling many independent and highly parallelizable tasks to be executed concurrently, including 1) solving the multiple 2-D as signment problems via a parallelization of the m-best partitioning task, an d 2) calculating the numerous gating tests, state estimates, covariance cal culations, and likelihood function evaluations (used as cost coefficients i n the 2-D assignment problem) via a parallelization of the data association interface task. Using both simulated data and an air traffic surveillance (ATS) problem based on data from two Federal Aviation Administration (FAA) air traffic control radars, we demonstrate that efficient solutions to the data association problem are obtainable using our improvements in the m-bes t 2-D assignment algorithm.