A LAGRANGIAN RELAXATION ALGORITHM FOR MULTIDIMENSIONAL ASSIGNMENT PROBLEMS ARISING FROM MULTITARGET TRACKING

The central problem in multitarget tracking is the data association problem of partitioning the observations into tracks in some optimal way so that an accurate estimate of the true tracks can be recovered. This work considers what is perhaps the simplest multitarget tracking problem in a setting where the issues are easily delineated, i.e., straight lines in two-dimensional space-time with an error component introduced into the observations. A multidimensional assignment problem is formulated using gating techniques to introduce sparsity into the problem and filtering techniques to generate tracks which are then used to score each assignment of a collection of observations to a filtered track. Problem complexity is further reduced by decomposing the problem into disjoint components, which can then be solved independently. A recursive Lagrangian relaxation algorithm is developed to obtain high quality suboptimal solutions in real-time. The algorithms are, however, applicable to a large class of sparse multidimensional assignment problems arising in general multitarget and multisensor tracking. Results of extensive numerical testing are presented for a case study to demonstrate the speed, robustness, and exceptional quality of the solutions.