Stochastic Systems Group  

Lei Chen, Martin Wainwright, Mujdat Cetin, Alan Willsky
SSG, MIT
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, errorcorrecting codes). The algorithms commonly used for inference on graphical models involve messagepassing operations that are not only efficient, but also wellsuited to realization via physicallydistributed 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 selforganization 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 selforganization 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 maxproduct or minsum algorithm) can be applied. We use a treereweighted version of the maxproduct 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 jonesb@mit.edu