EFFICIENT DATA ASSOCIATION ALGORITHMS FOR MULTI-TARGET TRACKING

Abstract

In this work, we propose a novel convex dual approach to the multidimensional dimensional assignment problem, which is an NP-hard binary programming problem. It is shown that the proposed dual approach is equivalent to the Lagrangian relaxation method in terms of the best value attainable by the two approaches. However, the pure dual representation is not only more elegant, but also makes the theoretical analysis of the algorithm more tractable. In fact, we obtain a su cient and necessary condition for the duality gap to be zero, or equivalently, for the Lagrangian relaxation approach to nd the optimal solution to the assignment problem with a guarantee. Also, we establish a mild and easy-to-check condition, under which the dual problem is equivalent to the original one. In general cases, the optimal value of the dual problem can provide a satisfactory lower bound on the optimal value of the original assignment problem. We then extend the purely dual formulation to handle the more general multidimensional assignment problem. The convex dual representation is derived and its relationship to the Lagrangian relaxation method is investigated once again. Also, we discuss the condition under which the duality gap is zero. It is also pointed out that the process of Lagrangian relaxation is essentially equivalent to one of relaxing the binary constraint condition, thus necessitating the auction search operation to recover the binary constraint. Furthermore, a numerical algorithm based on the dual formulation along with a local search strategy is presented. Finally, the newly proposed algorithm is shown to outperform the Lagrangian relaxation method in a number of multi-target tracking simulations.