General Data Association with Possibly Unresolved Measurements Using Linear Programming

In this paper we formulate data association with possibly unresolved measurements as an augmented assignment problem. Unlike conventional measurement-to-track association via assignment, this augmented assignment problem has much greater complexity when each target originated measurement can be of single or multiple origins. The main point is that standard one-to-one assignment algorithms do not work in the case of unresolved measurements because the constraints in the augmented assignment problem are very different. A suboptimal approach is considered for solving the resulting optimization problem via linear programming (LP) by relaxing the integer constraints. A tracker based on probabilistic data association filter (PDAF) using the LP solutions is also discussed. Simulation results show that the percentage of track loss is significantly reduced by solving the augmented assignment rather than the conventional assignment.