In this paper, we present alternate integer programming formulations for the multi-dimensional assignment problem, which is typically employed for multi-sensor fusion, multi-target tracking (MTT) or data association in general. The first formulation is the Axial Multidimensional Assignment Problem with Decomposable Costs (MDADC). The decomposable costs comes from the fact that there are only pairwise costs between stages or scans of a target tracking problem or corpuses of a data association context. The difficulty with this formulation is the large number of transitivity or triangularity constraints that ensure if entity A is associated to entity B and entity B is associated with entity C, then it must also be that entity A is associated to entity C. The second formulation uses both pairs and triplets of observations, which offer more accurate representation for kinematic tracking of targets. This formulation avoids the large number of transitivity constraints but significantly increases the number of variables due to triples. Solution to large-scale problems has alluded researchers and practitioners alike. We present solution methods based on Lagrangian Relaxation and massively parallel algorithms that are implemented on Graphics Processing Units (GPUs). We test the problem formulations and solution algorithms on MTT problems. The triples formulation tends to be more accurate for tracking measures and the MDADC solver can solve much larger problems in reasonable computational time.
In recent years, increasing interest in distributed sensing networks has led to a demand for robust multi-sensor multi-object tracking (MOT) methods that can take advantage of large quantities of gathered data. However, distributed sensing has unique challenges stemming from limited computational resources, limited bandwidth, and complex network topology that must be considered within a given tracking method. Several recently developed methods that are based upon the random finite set (RFS) have shown promise as statistically rigorous approaches to the distributed MOT problem. Among the most desirable qualities of RFS-based approaches is that they are derived from a common mathematical framework, finite set statistics, which provides a basis for principled fusion of full multi-object probability distributions. Yet, distributed labeled RFS tracking is a still-maturing field of research, and many practical considerations must be addressed before large-scale, real-time systems can be implemented. For example, methods that use label-based fusion require perfect label consistency of objects across sensors, which is impossible to guarantee in scalable distributed systems. This paper provides a survey of the challenges inherent in distributed tracking using labeled RFS methods. An overview of labeled RFS filtering is presented, the distributed MOT problem is characterized, and recent approaches to distributed labeled RFS filtering are examined. The problems that currently prevent implementation of distributed labeled RFS trackers in scalable real-time systems are identified and demonstrated within the scope of several exemplar scenarios.