A Polynomial-Time Approximation Algorithm for Joint Probabilistic Data AssociationSonghwai Oh and Shankar SastryJoint probabilistic data association (JPDA) is a powerful tool for solving data association problems. However, the exact computation of association probabilities $\{ \beta_{jk} \}$ in JPDA is NP-hard, where $\beta_{jk}$ is the probability that $j$-th observation is from $k$-th track. Hence, we cannot expect to compute association probabilities in JPDA exactly in polynomial time unless $P=NP$. In this paper, we present a simple Markov chain Monte Carlo data association (MCMCDA) algorithm that finds an approximate solution to JPDA in polynomial time. For $\epsilon >0$ and $0 < \eta < .5$, we prove that the algorithm finds good estimates of $\beta_{jk}$ with probability at least $1-\eta$ in time complexity $O( \epsilon^{-2} \log \eta^{-1} N (N \log N + \log ( \epsilon^{-1})))$, where $N$ is the number of observations.American Control Conference (ACC), Portland, OR, June 2005 Full Text (PDF) |
|
|