KEYWORDS: Sensors, Chemical elements, Missiles, Data fusion, Defense and security, Detection and tracking algorithms, Surveillance, Data centers, Data communications, Lawrencium
In this paper we compare the performance of two Multidimensional Assignment Algorithms (MDA), the Lagrangean Relaxation based S-D algorithm and the Sequential m-best 2-D algorithm, applied to a realistic problem in missile defense surveillance. The benchmark problem consists of a set of sources that provide "event" (track) estimates of multiple launches, via a number of communication networks to a Fusion Center (FC) which has to perform data association prior to fusion. The network model used "loses" the information tag that distinguishes reports from the same source transmitted through different networks, i.e., the track identity (ID) assigned by the source is not passed on. Only a track ID assigned by the network, and the source ID accompany the track. Thus detection and elimination of track duplications at the FC is needed. The proposed hierarchical approach to the problem requires the solution of several MDA problems before calculating the fused estimate, so accuracy of the solution of each is crucial. Examples with several launches, sources and networks are presented to compare the performance of the two assignment algorithms.
KEYWORDS: Data fusion, Mahalanobis distance, Lawrencium, Missiles, Chemical elements, Defense and security, Sensors, Surveillance, Data centers, Data communications
This paper formulates a benchmark data association problem in a missile defense surveillance problem. The specific problem considered deals with set of sources that provide "event" (track) estimates via a number of communication networks to a Fusion Center (FC) which has to perform data association prior to fusion. A particular feature of the network model is that the information to distinguish among reports from the same source transmitted through different networks is not available at the FC: the track identity (ID) assigned by the
source is not passed on, but only a track ID assigned by the network, and the source ID accompany the track. This makes it necessary to detect and eliminate track duplications at the FC among the messages with the same source ID but different network ID. The resulting data, organized into sensor lists, is associated using a likelihood
based cost function with one of the several existing multidimensional assignment (MDA) methods. A comparison of the following two association criteria: Mahalanobis distance ("chi-square") and likelihood ratio (LR) is carried out. It is shown that the LR yields significantly superior results. The tracks obtained after association are fused using a Maximum Likelihood approach. An additional complication is that false reports can be also transmitted by the sources. Examples with several launches, sources and networks are presented to illustrate the proposed solution and compare the performances of two assignment algorithms - the Lagrangean relaxation based S-D and the sequential m-best 2-D - on this realistic problem.
KEYWORDS: Failure analysis, Roentgenium, Data modeling, Monte Carlo methods, Barium, Systems modeling, Performance modeling, Sensors, Mahalanobis distance, Matrices
Many tracking systems have the requirement to transfer information about a particular tracked object between two systems. The general approach to this involves generation of an object map by the system designating the particular track followed by receipt of the map and correlation to the local track picture of the second system. Correlation performance is in general limited by a number of factors: random track errors added by each system, miss-registration of the two systems' coordinate frames, and miss-match between the numbers of objects tracked by the two systems. Two correlation algorithms are considered for this problem: Global Nearest Neighbor (GNN) and Global Nearest Pattern (GNP). Four basic failure modes are identified for the GNP formulation, and three of these explain failures in the GNN formulation. Analytic expressions are derived for each of these modes, and a comparison of each to Monte-Carlo experiment is provided to demonstrate overall validity.
Sharing data between two tracking systems frequently involves use of an object map: the transmitting system sends a frame of data with multiple observations, and the receiving system uses an assignment algorithm to correlate the information with its local observation data base. The usual prescription for this problem is an optimal assignment algorithm (such as JVC or auction) using a cost matrix based upon chi-squared distances between the local and remote observation data. The optimal assignment algorithm does not actually perform pattern matching, so this approach is not robust to large registration errors between the two systems when there exist differences in the number of observations held by both systems. Performance of a new assignment algorithm that uses a cost function including terms for both registration errors and track to track random errors is presented: the cost function explicitly includes a bias between the two observation sets and thus provides a maximum likelihood solution to the assignment problem. In practice, this assignment approach provides near perfect assignment accuracy in cases where the bias errors exceed the dimension of the transmitted object map and there exist mismatches in the numbers of observations made by the two systems. This performance extends to many cases where the optimal assignment algorithm methodology produces errors nearly 100% of the time. The paper includes the theoretical foundation of the assignment problem solved and comparison of achieved accuracy with existing optimal assignment approaches.
The processing time requirements of several algorithms for solving the 2-d (also called single frame) linear assignment problem are compared, along with their accuracy given either random or biased measurement errors. The specific problem considered is that of assigning measurements to truth objects using costs that are the chi-squared distances between them. Performance comparisons are provided for the algorithms implemented both in a compiled language C or FORTRAN) as well as the interpretive MatLab language. Accuracy considerations show optimal assignment algorithm is preferred if biased measurement errors are present. The Jonker-Volgenant-Castanon (JVC) algorithm is the preferred approach considering both average and maximum solution time. The Auction algorithm finds favor due to being both efficient as well as easy to understand, but is never faster and often much slower than the JVC algorithm. Both algorithms are dramatically faster than the Munkres algorithm. The greedy nearest neighbor algorithm is an ad hoc solution to provide a sub-optimal but unique solution more cheaply than the optimal assignment algorithms. However, the JVC algorithm is as fast as the greedy for simple problems, marginally slower at hard problems, and is vastly more accurate in the presence of measurement biases.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.