Some assignment problems arising from multiple target tracking

Multiple target tracking is a subject devoted to the estimation of targets’ or objects’ states, e.g., position and velocity, over time using a single or multiple sensors. The development of modern tracking systems requires a wide variety of algorithms ranging from gating (preprocessing), state and bias estimation, and development of likelihood ratios to data association. The central problem is the data association problem of partitioning sensor reports into tracks and false alarms. From a data association perspective, multiple target tracking methods divide into two basic classes, single and multiple frame processing. The advantage of multiple frame methods is that current decisions are improved by the ability to change past decisions, making multiple frame methods the choice for difficult tracking problems. The classical multiple frame method that has been well developed is called multiple hypothesis tracking (MHT). In the last ten to fifteen years, a new method, called multiple frame assignments (MFA) has been developed by formulating MHT as a multi-dimensional assignment problem for which modern optimization methods can be utilized in the development of near-optimal solutions for real-time applications. This work reviews a number of the problem formulations, including two-dimensional asymmetric single and multi-assignment problems, the corresponding multi-dimensional versions, and the newer group assignment problems. Some of the current and future needs are also discussed.