Communications: directive radio wave systems and devices (e.g. – Determining velocity – Combined with determining distance
Reexamination Certificate
1993-06-15
2001-05-29
Davis, George B. (Department: 2122)
Communications: directive radio wave systems and devices (e.g.,
Determining velocity
Combined with determining distance
C342S099000, C342S062000, C342S096000, C706S905000
Reexamination Certificate
active
06239740
ABSTRACT:
FIELD OF THE INVENTION
The invention pertains generally to tracking of objects, such as aircraft by radar or submarines by sonar, and particularly to computationally efficient apparatus and methods of tracking and data fusion.
BACKGROUND OF THE INVENTION
As demand for practical solutions to larger scale data fusion or data association tasks increases, issues of computational complexity of the algorithmic approaches used become topics of more serious interest. Theoretically well-defined and well-grounded analytical models for data association problems may exist without having easily computed solutions. When such situations arise it is desirable to determine efficient approximation procedures that, if possible, are well-conditioned such that certain bounds on errors can be determined.
When data association tasks consist of merging, or fusing, two or more large sets of data that both represent a common underlying reality or ground truth, such issues of the computational complexity of the algorithms do arise. We assume that a general task of data association is to take two independent sets of state estimates, e.g., measurements and predicted state values, that each represent a common underlying set of objects and to determine the associations between the elements from the distinct sets of data. Fusion, or subsequent assignment of the elements from the independent representations to a single representation will depend on the determination of these associations.
Typically in discussions of computational complexity, reference is made to the underlying graph theoretic structure of the problem at hand. The purpose of this exercise is to determine if the general problem has ever arisen in other applications. In fact, this is indeed the case with some data association problems. The graph structure associated with the fusion problem is a bipartite graph, since by assumption there are two sets of data, independently arrived at. From each element a&egr;A there may be an association with an element b&egr;B represented by an edge &ohgr;
ab
&egr;E. On the graph, &Ggr;{A, B, E} this corresponds to vertices of A connected to vertices of B with weighted edges, where the weight represents the weight of association. One may think of the association weights forming an association matrix, &OHgr;. In the process of fusion there are commonly constraints that describe feasible joint events, i.e., each element of one set may be assigned to at most only one element of the other set and vice-versa. In such cases the joint event is properly termed a match or, defined on a bipartite graph, a bipartite match. If this match has maximum cardinality, generally corresponding to the constraint that a feasible joint event is a one-to-one mapping (always possible with false alarms), then it is called a perfect match.
In general the representation of objects is a multidimensional state value with an associated error estimate. Commonly the state value is an estimated mean value and the error is represented as an associated covariance matrix defining a Gaussian probability distribution. When a probabilistic interpretation is given to the association weights, as we have assumed, the merging may be done in a variety of ways that have particular probabalistic interpretations. The nearest-neighbor approach, where the largest association weight at each node of one set alone determines the assignment, essentially assumes that there is virtually only one individual pairwise association of importance for every element, a condition of sparsity of the association matrix, &OHgr;. The nearest-neighbor approach is the simplest of greedy heuristics. The optimum weighted bipartite match corresponds to the most probable, or modal, joint event, and is also used as a fusion method.
In dense environments where individual elements appear to have many significant associations, a more appropriate approach to this data association problem is described by Bar-Shalom (Tracking and Data Association, ACADEMIC PRESS (1968)) and is referred to as JPDA (joint probabilistic data association). In this approach each association weight is taken as an individual pairwise association probability or marginal association probability. The relative probability of one match with respect to any other is taken as the product of the individual pairwise association probabilities (the edge weights) of the match. (Since objective functions are usually summed, this corresponds to the sum over the log of the pairwise association probabilities). The expected probability that a and b refer to the same object is determined by summing the joint probabilities of the perfect matches in which a and b are paired and normalizing by the sum of joint probabilities over all possible perfect matches. For an N×N association matrix, &OHgr;, this may be alternatively stated as
<p
ab
>=&OHgr;
ij
*perM
(i,j)
/per&OHgr; (1)
where the permanent of &OHgr;is defined as
per
Ω
=
∑
i
1
,
i
2
,
…
,
i
N
&LeftBracketingBar;
ε
i
1
,
i
2
,
…
,
i
N
&RightBracketingBar;
Ω
i
1
,
1
Ω
i
2
,
2
…
Ω
i
N
,
N
=
∑
σ
Ω
σ
1
,
1
Ω
σ
2
,
2
…
Ω
σ
N
,
N
(
2
)
which is similar to the definition of the determinant with the exception that the absolute value of the Levi-Civita symbol is used to represent the sum over all permutations, &sgr;, of the indices 1 . . . N and the permanent—minor, or perM
(i,j)
, is determined by taking the permanent of the matrix M
(i,j)
, generated by crossing out the ith row and jth column of the matrix &OHgr;.
Valiant (The Complexity of Computing the Permanent, THEORETICAL COMPUTER SCIENCE, 8, 189-201 (1979)) has shown that the evaluation of the permanent of a 0-1 matrix (similar to the validation matrix for JPDA), equivalent to counting the number of perfect matches, is NP-hard. Complete evaluation of the permanent of a general association matrix is equivalent to enumeration of all possible perfect matches, a significantly more difficult problem. This implies that the exact solution of the JPDA is indeed NP-hard. Approximation methods, however, do exist and generally reduce the computational scaling significantly. These methods themselves then become the important subjects of consideration in terms of computational scaling.
Determining computational tractability in approaches to tracking for large-scale real-time problems is an exercise of putting practical upper bounds on algorithmic scaling. Clearly, any algorithm will scale at least linearly with the size of the input data. We would maintain, perhaps arbitrarily, that for large-scale problems quadratic algorithmic scaling forms a practical upper bound.
Thresholding the elements of &OHgr; is one approach that reduces the scaling of JPDA (or any other approach). The permanent may be evaluated recursively via a development through permanent-minors in the same manner as a determinant is evaluated by a Laplacian development through minors. For sparse matrices with O(kN) elements this evaluation method appears to scale at worst as N
k
. Clearly, by thresholding matrix elements to guarantee sparsity, one may both approximate the permanent and put a limit on the scaling behavior of the evaluation algorithm.
Gating is the general problem in data fusion of determining significant association probabilities between two large sets of linear, multidimensional pattern elements (see S. S. Bleckman, Multi-Target Tracking with Radar Applications (Artech House 1986)), e.g., thresholding the association probability overlap integrals between a set of measured state vectors and a set of of estimated state vectors, both having associated error distributions. As a precursorial coarse assignment method for multitarget tracking, it reduces the computational complexity of the NP-hard exact JPDA, or any other data association method.
Computing the full association matrix between two
Collins Joseph B.
Uhlmann Jeffrey K.
Davis George B.
McDonnell Thomas E.
Miles Edward
The United States of America as represented by the Secretary of
LandOfFree
Efficient data association with multivariate Gaussian... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient data association with multivariate Gaussian..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient data association with multivariate Gaussian... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2510487