SHARED-MEMORY PARALLELIZATION OF THE DATA ASSOCIATION PROBLEM IN MULTITARGET TRACKING

The focus of this paper is to present the results of our investigation and evaluation of various shared-memory parallelizations of the data association problem in multitarget tracking. The multitarget tracking algorithm developed was for a sparse air traffic surveillance problem, and is based on an Interacting Multiple Model (IMM) state estimator e mbedded into the (2D) assignment framework. The IMM estimator imposes a computational burden in terms of both space and time complexity, sin ce more than one filter model is used to calculate state estimates, co variances, and likelihood functions. In fact, contrary to conventional wisdom, for sparse multitarget tracking problems, we show that the as signment (or data association) problem is not the major computational bottleneck. Instead, the interface to the assignment problem, namely, computing the rather numerous gating tests and IMM state estimates, co variance calculations, and likelihood function evaluations (used as co st coefficients in the assignment problem), is the major source of the workload. Using a measurement database based on two FAA air traffic c ontrol radars, we show that a ''coarse-grained'' (dynamic) paralleliza tion across the numerous tracks found in a multitarget tracking proble m is robust, scalable, and demonstrates superior computational perform ance to previously proposed ''fine-grained'' (static) parallelizations within the IMM.