An interior point linear programming approach to two-scan data association

We present an efficient two-scan data association method (TSDA) based on an interior point linear programming (LP) approach. In this approach, the TSD A problem is first formulated as a 3-dimensional assignment problem, and th en relaxed to a linear program; the latter is subsequently solved by the hi ghly efficient homogeneous, self-dual interior point LP algorithm. When the LP algorithm generates a fractional optimal solution, we use a technique s imilar to the joint probabilistic data association method (JPDA) to compute a weighted average of the resulting fractional assignments, and use it to update the states of the existing tracks generated by Kalman tilters. Unlik e the traditional single scan JPDA method, our TSDA method provides an expl icit mechanism for track initiation. Extensive computer simulations have de monstrated that the new TSDA method is not only far more efficient in terms of low computational complexity, but also considerably more accurate than the existing single-scan JPDA method.