Parallelizations For Multitarget Tracking

September 1999 No Comments

Distributed- and Shared-Memory Parallelizations of Assignment-Based Data Association for Multitarget Tracking.

Author: Popp, R., Pattipati, K. & Bar-Shalom, Y.

Abstract

To date, there has been a lack of efficient and practical distributed- and shared-memory parallelizations of the data association problem for multitarget tracking. Filling this gap is one of the primary focuses of the present work. We begin by describing our data association algo- rithm in terms of an Interacting Multiple Model (IMM) state estimator embedded into an optimization framework, namely, a two-dimensional (2D) assignment problem (i.e., weighted bipartite matching). Contrary to conventional wisdom, we show that the data association (or optimization) problem is not the major computational bottleneck; instead, the interface to the optimization problem, namely, computing the rather numerous gating tests and IMM state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients 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 association problem that focus on the interface problem. For the former, a coarse-grained dynamic parallelization was developed that realizes excellent per- formance (i.e., superlinear speedups) independent of numerous factors influencing problem size (e.g., many models in the IMM, dense?cluttered environments, contentious target-measure- ment data, etc.). For the latter, an SPMD (Single Program Multiple Data) parallelization was developed that realizes near-linear speedups using relatively simple dynamic task allocation algorithms. Using a real measurement database based on two FAA air traffic control radars, we show that the parallelizations developed in this work offer great promise in practice.

Conclusion

In this work, in the context of a sparse multitarget air traffic surveillance problem, we showed (via workload analysis) that the interface to the data association (optimi- zation) problem was the computational bottleneck, as opposed to the optimization problem itself. We then described a coarse-grained shared-memory parallelization of the data association interface problem that yielded excellent performance results, i.e., superlinear speedups, scalable, performance independent of numerous factors influ- encing problem size, e.g., many models in the IMM, large track?scan set sizes, or contentious target-measurement multitarget data due to clutter, dense scenarios, and?or coarse gating policies. In the case of a fine-grained parallelization, the performance was dependent on the number of filter models used, yielding negligible throughput for any number of filter models, marginal speedups when many models were used, and worse execution time than sequential time when three or less filter models were used. We then described an SPMD distributed-memory parallelization of the data association interface problem that also yielded excellent performance (i.e., near-linear speedups) configured with relatively simple task allocation algorithms. Furthermore, consistent with other research efforts, in the context of multitarget tracking, we showed that using relatively simple dynamic (heuristic) task allocation algorithms can offer great promise in practice.

Citation

Popp, R., K. Pattipati and Y. Bar-Shalom, “Distributed- and Shared-Memory Parallelizations of Assignment-Based Data Association for Multi-target Tracking,” Annals of Operations Research: Special Issue on Parallel Optimization, vol. 90, pp. 293–322, Sept 1999.