Markov Chain Monte Carlo Data Association for Multi-Target Tracking Univ

data association (MCMCDA) for solving data association prob-lems arising in multi-target tracking in a cluttered environment. When the number of targets is fixed, the single-scan version of MCMCDA approximates joint probabilistic data association (JPDA). Although the exact computation of association probabili-ties in JPDA is NP-hard, we prove that the single-scan MCMCDA algorithm provides a fully polynomial randomized approximation scheme for JPDA. For general multi-target tracking problems, in which unknown numbers of targets appear and disappear at random times, we present a multi-scan MCMCDA algorithm that approximates the optimal Bayesian filter. We also present exten-sive simulation studies supporting theoretical results in this paper. Our simulation results also show that MCMCDA outperforms multiple hypothesis tracking (MHT) by a significant margin in terms of accuracy and efficiency under extreme conditions, such as a large number of targets in a dense environment, low detection probabilities, and high false alarm rates. Index Terms—Joint probabilistic data association (JPDA), Markov chain Monte Carlo data association (MCMCDA), mul-tiple hypothesis tracking (MHT). I