A New Class of Methods for Solving Data Association Problems Arising from Multiple Target Tracking

The data association problem of partitioning observations into tracks and false alarms is posed as a multi-dimensional assignment problem. Although this combinatorial optimization problem is NP-hard, it is the purpose of this work to present a new formulation of this data association problem, a class of algorithms based on Lagrangean relaxation to solve these problems in real-time, and the results of extensive numerical studies on a modern workstation, the Cray Y-MP, and the Connection Machine. System identification techniques including smoothing, filtering, and prediction are used to determine past, present, and future behavior of the targets.