Use of the Auction Algorithm for Target Object Mapping

摘要

This report compares the performance of two algorithms in correlatingobservations from multiple sensors. This correlation problem can be treated as an assignment problem in operations research, with assignment costs being equal to the sufficient statistic of the generalized likelihood ratio test. In sensor to sensor correlation, the main concern is a one-to-the solution in which targets from one sensor are matched in an optimal manner with targets from the other sensor. This corresponds to a classical assignment problem that is often solved using Munkres' algorithm. In target object mapping, concern shifts to correctly associating a subset of high value targets between sensors. We hypothesize that this goal could be better attained by allowing for a many-to-one solution and propose the use of a modified auction algorithm to solve this generalized assignment problem. Results of Monte Carlo simulations of such situations are analyzed to compare the performance of the two solution methods.