Tracking Multiple Maneuvering Targets Using Integer Programming and Spline Interpolation

摘要

In this paper, we propose an integer programming based model for tracking multiple maneuverable targets in a planar region. The objective function of this model uses both pairs and triplets of observations, which offer more accurate representation for constant velocity targets. Triplet scores in this model are calculated using a novel approach based on cubic spline interpolation, while the data association problem is solved using a specialized multi-dimensional assignment formulation. We show that the spline interpolation based scoring model provides more accurate reconstruction of trajectories, when compared to a naïve model based on linear interpolation, on various randomly generated trajectories, at the expense of modest increase in computation time. The proposed multi-dimensional assignment formulation has nice structural properties and tight linear programming relaxation bound, which results in small computation times.