Fast data association using multidimensional assignment with clustering

We present a fast data association technique based on clustering and multid imensional assignment algorithms for multisensor-multitarget tracking. Assi gnment-based methods have been shown to be very effective for data associat ion. Multidimensional assignment for data association is an NP-hard problem and various near-optimal modifications with (pseudo-)polynomial complexity have been proposed. In multidimensional assignment, candidate assignment t ree building consumes about 95% of the time. We present the development of a fast data association algorithm, which partitions the problem into smalle r sub-problems. A clustering approach, which attempts to group measurements before forming the candidate tree, is developed for various target-sensor configurations. Simulation results show significant computational savings o ver the standard multidimensional assignment approach without clustering.