Stochastic Systems Group  

Lei Chen
SSG Doctoral Student
Data association is a fundamental problem in multitargetmultisensor tracking. It entails selecting the most probable association from a very large set of possibilities. With $M$ sensors and $N$ targets in the range of each sensor, there are $(N !)^{M  1}$ different configurations, which renders infeasible a solution by direct computation even in modestlysized applications. (For example, for $M = 7$ and $N = 5$, there are slightly less than $3$ trillion possible configurations.) We describe an iterative method for solving the optimal data association in a distributed fashion; the work exploits the framework of graphical models. Our basic idea is to treat the measurement assignment for each sensor as a random variable, which is in turn represented as a node in an underlying graph. Neighboring nodes are coupled by the targets visible to both sensors. Thus we transform the data association problem to that of computing the maximum a posteriori (MAP) configuration in a graphical model, to which efficient techniques (e.g., the maxproduct/minsum algorithm) can be applied. We use the treereweighted maxproduct algorithm instead of the regular version to get the exact MAP estimates of the association variables on any graph topology (subject to some necessary conditions). For acyclic graphs, our algorithm can solve the data association problem directly and recursively with complexity of $\mathcal{O}\left( (N !)^2 M \right)$. On graphs with cycles, the algorithm may require more iterations to converge. However, for the data association problem the coupling matrices are inherently of low rank, and experiments show that the algorithm still converges very fast in this case.
Joint work with Martin J. Wainwright, Mujdat Cetin, and Alan S. Willsky.
Problems with this site should be emailed to jonesb@mit.edu