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

SSG Seminar Abstract

Lagrangian-Relaxed Graphical Models for Multiple Hypothesis Tracking

Jason Johnson - SSG, MIT

Multiple Hypothesis Tracking (MHT) is an algorithmic framework for addressing the multi-sensor/multi-target tracking problem. Here, scans of data arrive sequentially in time each scan being comprised of multiple target reports. Each report contains noisy observation of the location and velocity of a detected target. It is the job of MHT to fuse this incoming stream of reports and to render the most likely explanation (MLE) of all reports received thus far. Inherent in this approach is a challenging multidimensional assignment problem of how we should associate reports across multiple scans. Additionally, in order to control the computational complexity of MHT, it is necessary to provide hypothesis pruning methods to limit the number of possible explanations MHT must consider.

In this talk, we introduce MHT and present a graphical model (factor graph) formulation of the MLE and hypothesis pruning problems. We then develop two solution methods based on max-product belief-propagation and Lagrangian relaxation. Several examples are presented. We conclude with possible extensions of the method.

Problems with this site should be emailed to