Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking

The ever-increasing demand in surveillance is to produce highly accurate target and track identification and estimation in real-time, even for dense target scenarios and in regions of high track contention. The use of multiple sensors, through more varied information, has the potential to greatly enhance target identification and state estimation. For multitarget tracking, the processing of multiple scans all at once yields high track identification. However, to achieve this accurate state estimation and track identification, one must solve an NP-hard data association problem of partitioning observations into tracks and false alarms in real-time. The primary objective in this work is to formulate a general class of these data association problems as multidimensional assignment problems to which new, fast, near-optimal, Lagrangian relaxation based algorithms are applicable. The dimension of the formulated assignment problem corresponds to the number of data sets being partitioned with the constraints defining such a partition. The linear objective function is developed from Bayesian estimation and is the negative log posterior or likelihood function, so that the optimal solution yields the maximum a posteriori estimate. After formulating this general class of problems, the equivalence between solving data association problems by these multidimensional assignment problems and by the currently most popular method of multiple hypothesis tracking is established. Track initiation and track maintenance using anN-scan sliding window are then used as illustrations. Since multiple hypothesis tracking also permeates multisensor data fusion, two example classes of problems are formulated as multidimensional assignment problems.This work was partially supported by the Air Force Office of Scientific Research through AFOSR Grant Numbers AFOSR-91-0138 and F49620-93-1-0133 and by the Federal Systems Company of the IBM Corporation in Boulder, CO and Owego, NY.