Parallel and distributed algorithms for data association and application to multitarget tracking

In the first part of this dissertation, we developed several novel and highly-efficient parallelizations of an existing serial multitarget tracking algorithm based on an Interacting Multiple Model (IMM) state estimator embedded into the 2 D assignment framework. The parallelizations developed were for both a distributed-memory high-performance computer (HPC) and a general-purpose shared-memory MIMD multiprocessor. For a sparse Air Traffic Surveillance (ATS) problem, the results of our work show that: (i) our coarse-grained shared-memory parallelization across the numerous tracks found in a multitarget tracking problem is robust, scalable, and can realize superlinear speedups, unlike previously proposed fine-grained parallelizations, and (ii) a SPMD distributed-memory parallelization using relatively simple task allocation algorithms has excellent performance and can realize near linear speedups.; In the second part of this dissertation, we developed a novel dynamically adaptable m-best 2 D assignment algorithm and multi-level parallelization for a shared-memory multiprocessor. The m-best 2 D assignment algorithm is more efficient than the "best" m-best 2 D assignment algorithm currently in the literature, especially in dynamic multitarget tracking environments. For both simulated data and the same ATS problem, the results of our work show that: (i) a non-intrusive 2 D assignment algorithm switching mechanism enables the numerous 2 D assignment problems generated in the m-best assignment framework to be efficiently solved, and (ii) a multi-level parallelization of the partitioning task and the data association interface task enables many independent and highly parallelizable tasks to be executed in parallel.; In the third part of this dissertation, we developed a novel m-best S D assignment algorithm and its shared-memory parallelization. To date, there has been no precedent to our m-best S D assignment algorithm. Some of the more novel aspects of this work include: (i) an efficient localization solution via a coarse-grained parallelization of the numerous static SD assignment problems generated in the m-best assignment framework, (ii) the formulation of higher-level composite (super) measurements and their corresponding joint event probabilities, and (iii) an efficient tracking solution via a series of dynamic 2 D assignment problems based on the composite measurement lists. We demonstrate m-best S D on a passive sensor multitarget tracking problem consisting of an unknown number of targets (emitters) based on multiple time samples of measurements originating from multiple high frequency direction finders.