Optimization Problems in Multitarget/Multisensor Tracking

Book excerpt: 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 the desired track identification and accurate state estimation; however, one must solve an NP-hard data association problem of partitioning observations into tracks and false alarms in real-time. This report summarizes the development of a multisensor-multitarget tracker based on the use of near-optimal and real-time algorithms for the data association problem and is divided into several parts. The first part addresses the formulation of multisensor and multiscan processing of the data association problem as a combinatorial optimization problem. The new algorithms under development for this NP-hard problem are based on a recursive Lagrangian relaxation scheme, construct near-optimal solutions in real-time, and use a variety of techniques such as two-dimensional assignment algorithms, a bundle trust region method for the nonsmooth optimization, and graph theoretic algorithms for problem decomposition. A brief computational complexity analysis as well as a comparison with some additional heuristic and optimal algorithms is included to demonstrate the efficiency of the algorithms. New results on numerical efficiency and increased robustness for track maintenance are also discussed. This program has produced two U.S. patents with a third pending and has developed the basis for the IBest of Breed Tracker Contest winner at Hanscom AFB in 1996.