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

SSG Seminar Abstract

Data Association based on Optimization in Graphical Models
with Application to Sensor Networks

Lei Chen, Martin Wainwright, Mujdat Cetin, Alan Willsky

We propose techniques for the solution of data association problems in a distributed fashion, using the framework of graphical models. We are primarily motivated by problems arising in multiple target tracking with distributed sensor networks. Graphical models provide a powerful tool for encoding the statistical dependencies of a set of random variables, and are widely used in many applications (e.g., computer vision, error-correcting codes).  The algorithms commonly used for inference on graphical models involve message-passing operations that are not only efficient, but also well-suited to realization via physically-distributed processors in parallel, which is a crucial requirement in many sensor network applications.

One key issue we address is how to transform the data association problems arising in distributed sensing scenarios into the graphical model framework. We describe our approach to this issue on two specific problems. In the first problem, we assume that the self-organization of the sensor network has already occurred, and that each sensor produces bearing and/or range measurements for the targets in its surveillance region. The question is to determine which sensor measurement should be associated with which target track. In the second problem, we consider a scenario where self-organization needs to be accomplished, and, for simplicity, we assume that sensors are very simple proximity indicators. The key issue is to figure out which subset of the targets are seen by which subset of the sensors. We transform each problem discussed above to that of computing the maximum a posteriori (MAP) configuration on a graphical model, to which efficient techniques (e.g., the max-product or min-sum algorithm) can be applied.

We use a tree-reweighted version of the max-product algorithm that is able to yield the optimal MAP estimates under relatively weak necessary conditions. We demonstrate the effectiveness and the computational efficiency of this approach on a number of examples.

Problems with this site should be emailed to