A generalized S-D assignment algorithm for multisensor-multitarget state estimation

We develop a new algorithm to associate measurements from multiple sensors to identify the real targets in a surveillance region, and to estimate their states at any given time. The central problem in a multisensor-multitarget state estimation problem is that of data association-the problem of determining from which target, if any, a particular measurement originated. The data association problem is formulated as a generalized S-dimensional (S-D) assignment problem, which is NP-hard for S/spl ges/3 sensor scans (i.e., measurement lists). We present an efficient and recursive generalized S-D assignment algorithm (S/spl ges/3) employing a successive Lagrangian relaxation technique, with application to the localization of an unknown number of emitters using multiple high frequency direction finder sensors (S=3, 5, and 7).