Multidimensional assignment by dual decomposition

Abstract

Data association, or finding the correspondence between targets and measurements, is an integral part of a surveillance system. This paper studies a classical approach to the multiple scan data association problem, namely multidimensional assignment (MDA). Obtaining the optimal solution to the MDA problem is NP-hard for N ≥ 3, i.e., the computation time exponentially grows with the number of scans. The most successful approach for solving these problems has been using Lagrangian relaxation. This paper investigates the use of the dual decomposition approach, an alternative formulation for Lagrangian relaxation, in MDA problems. For a challenging scenario where targets are closely spaced, the dual decomposition formulation converges to the optimal solution in fewer iterations than a prior recursive Lagrangian relaxation algorithm. The Lagrangian relaxation algorithms are also compared to a formulation that uses loopy belief propagation (LBP). While LBP is not guaranteed to converge, and if it converges it is not guaranteed to be optimal, empirical results show that if LBP converges it produces similar solutions in fewer iterations than the optimisation algorithms.