Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Multitarget-Multisensor Data Association Using the Tree-Reweighted Max-Product Algorithm

Lei Chen
SSG Doctoral Student

Data association is a fundamental problem in multitarget-multisensor 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 modestly-sized 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 max-product/min-sum algorithm) can be applied. We use the tree-reweighted max-product 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