Distributed- and shared-memory parallelizations of assignment-based data association for multitarget tracking

To date, there has been a lack of efficient and practical distributed- and shared-memory parallelizations of the data association problem for multitar get tracking. Filling this gap is one of the primary focuses of the present work. We begin by describing our data association algorithm in terms of an Interacting Multiple Model (IMM) state estimator embedded into an optimiza tion framework, namely, a two-dimensional (2D) assignment problem (i.e., we ighted bipartite matching). Contrary to conventional wisdom, we show that t he data association (or optimization) problem is not the major computationa l bottleneck; instead, the interface to the optimization problem, namely, c omputing the rather numerous gating tests and IMM state estimates, covarian ce calculations, and likelihood function evaluations (used as cost coeffici ents in the 2D assignment problem), is the primary source of the workload. Hence, for both a general-purpose shared-memory MIMD (Multiple Instruction Multiple Data) multiprocessor system and a distributed-memory Intel Paragon high-performance computer, we developed parallelizations of the data assoc iation problem that focus on the interface problem. For the former, a coars e-grained dynamic parallelization was developed that realizes excellent per formance (i.e., superlinear speedups) independent of numerous factors influ encing problem size (e.g., many models in the IMM, denseycluttered environm ents, contentious target-measurement data, etc.). For the latter, an SPMD ( Single Program Multiple Data) parallelization was developed that realizes n ear-linear speedups using relatively simple dynamic task allocation algorit hms. Using a real measurement database based on two FAA air traffic control radars, we show that the parallelizations developed in this work offer gre at promise in practice.