Solving the multisensor data association problem

In this paper we focus on the multisensor data association problem. This is the process of determining which measurements from one or more sensors act ually relate to the same object. One formulation of the data association pr oblem is a multi-dimensional assignment problem, which is computationally d ifficult (NP hard) for in greater than or equal to 3 sensors. In the case o f m = 3 sensors, the data association problem is formulated as a three-dime nsional assignment problem. The cost coefficients in the assignment problem are obtained by maximising the non-linear joint likelihood function of the measurement partition. We present exact solution methods such as Lagrangia n Relaxation and Branch and Bound to solve the problem. These methods are e valuated on randomly generated test problems of size varying from 64 to 64, 000 binary variables. The relaxation method is able to solve the problems w ithin 2% of the theoretical optimum. Within the one hour of CPU time allowe d, the depth-first Branch and Bound algorithm is able to solve problems wit h up to 13,824 binary variables. For problems with more variables, an incre ase in CPU time is required for the algorithm to terminate with an optimal solution.