United States Patent 8799189
Inventors:
Blackman, Samuel S. (Los Angeles, CA, US)
Norman, Rachel B. (Long Beach, CA, US)
Carroll, Douglas E. (Downey, CA, US)
Capparelli, Stephen A. (Torrance, CA, US)
FIELD OF THE INVENTION
The currently described invention relates to multiple hypothesis systems and methods for tracking observations.
BACKGROUND
Prior art methods for multiple hypothesis tracking have been implemented in radar tracking systems. Consecutive radar observations of the same target are grouped in tracks. The multiple hypothesis tracking methods allow a track to be updated by more than one observation for each radar update cycle. This produces multiple possible tracks. As each radar update cycle is received every possible track can be potentially updated. The tracks branch into many possible directions. The multiple hypothesis tracking methods calculate the probability of each potential track and typically only report the most probable of all the tracks. Existing methods are limited to use in specific domains that prevent them from being used in alternative domains or across multiple types of domains.
A need therefore exists for improved multiple hypothesis systems and methods for tracking observations.
SUMMARY
Embodiments described herein are directed to multiple hypothesis systems and methods for tracking observations that are domain agnostic. One embodiment described herein relates to cyber security tracking methods and systems.
Discussion of Patent Validity
Requirements for PatentabilityThe patent laws usually require that, for an invention to be patentable, it must be:
- Patentable subject matter, i.e., a kind of subject-matter eligible for patent protection
- Novel (i.e. at least some aspect of it must be new)
- Non-obvious (in United States patent law) or involve an inventive step (in European patent law)
- Useful (in U.S. patent law) or be susceptible of industrial application (in European patent law[1])
multiple hypothesis tracking - Google Search
Is this really novel and non-obvious from seminal MHT papers and general clustering techniques? A Google search reveals over 22 million hits. MHT has been used for several decades in JDL Level 1 multi-sensor fusion for satellite surveillance and intelligence MULTI-INT fusion. The earliest paper specifically to develop the MHT concept (not cited in the patent) was by D.B. Reid:
Reid, D.B., "An algorithm for tracking multiple targets," Automatic Control, IEEE Transactions on , vol.24, no.6, pp.843,854, Dec 1979
doi: 10.1109/TAC.1979.1102177
keywords: {Bayes procedures; Tracking;Air traffic control; Clustering algorithms; Land vehicles; Marine vehicles; Military aircraft; Probability;Radar detection; Radar tracking;Sea measurements; Target tracking},
URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1102177&isnumber=24175
2 comments:
I have always wondered how something can be patented after the fact after
it is widely published in the open literature and persisted for years and there are so many prior precedents (by others): this interesting area of multi-sensor \multi-target tracking (sometimes pursued even in clutter) is related to optimal resource
allocation and solved by invoking either the Munkres Algorithm or the Hungarian Algorithm or the Jonker-Volgenent-Castanon’s
(J-V-C) Algorithm or Murty’s Algorithm (1968) or Track-Before-Detect in conjunction with use of Generalized Likelihood Ratio
(GLR) or Multi-Hypothesis Testing (MHT) algorithms from the Operations Research area (or the Auction Algorithm for a
decentralized, distributed implementation)]. Also see Miller, M. L., Stone, H, S., Cox, I. J., “Optimizing Murty’s Ranked Assignment Method,” IEEE Trans. on Aerospace and Electronic Systems, Vol. 33, No. 7, pp. 851-862, July 1997. Another: Frankel, L., and Feder, M., “Recursive Expectation-Maximizing (EM) Algorithms for Time-Varying Parameters with Applications to Multi-target Tracking,” IEEE Trans. on Signal Processing, Vol. 47, No. 2, pp. 306-320, February 1999. Yet another: Buzzi, S., Lops, M., Venturino, L., Ferri, M., “Track-before-Detect Procedures in
a Multi-Target Environment,” IEEE Trans. on Aerospace and Electronic Systems, Vol. 44, No. 3, pp. 1135-1150, July 2008.
Similar algorithms such as squareroot filtering could not be patented because of its detailed
documentation in published literature:
[1] Carison, N. A., "Fast Thangular Formulation of the Squareroot Filter," AIAA Journal, Vol. 11, No. 9, pp. 1259-1265,
1973.
[2] Bierman, G.J., Factorization Methods for Discrete Sequential Estimation, Academic Press, 1977.
Especially since reference [2] above had detailed FORTRAN subroutines for all aspects (Thus blocking JPL and his prior manager co-author Ms. Thorton at JPL).
Interesting. This 2011 patent application acknowledges some of the prior art in radar-oriented MHT, but claims uniqueness for domain-agnostic and "cyber security" MHT applications.
For example, here is its first claim:
"A multiple hypothesis cyber security tracking method for tracking observations, the method comprising: receiving observations associated with cyber sensor data signals from a plurality of cyber-domain types; distributing each of the observations to one or more association engines, wherein each association engine is configured for a particular domain type and each association engine manages zero or more preexisting tracks of observations; associating each of the observations with a) the one or more preexisting tracks, or b) a newly generated track to generate an updated set of tracks, wherein associating each of the observations comprises associating a new observation with the observations of a first preexisting track if the new observation satisfies a predetermined criterion; sending the updated set of tracks with track quality scores for each track to a domain agnostic hypothesis manager; updating a track hypothesis model of the domain agnostic hypothesis manager with the updated set of tracks; determining a probability estimate for each track in the track hypothesis model and selecting a hypothesis for each cluster of related tracks stored in the track hypothesis model that satisfies a predetermined cluster condition; sending the probability estimate for each track in the track hypothesis model and the selected hypothesis for each cluster of tracks to the one or more association engines to update track information in the one or more association engines; and sending the updated track information with cyber-domain specific information to an entity collector module for distribution to a recipient processor."
Unique or novel? Not so much, IMHO. Omit the words "cyber ..." above and it sounds like the same old song. But no worse than many other successful patents, I suppose.
As for the (omitted) earlier works, I feel obliged to cite the following one, based on -- based on IR&D projects at Hughes Aircraft Company, Fullerton -- including my first assignment on the Hughes work / study fellowship program!
Singer, R.A; Sea, R.G.; Housewright, K., "Derivation and evaluation of improved tracking filter for use in dense multitarget environments," Information Theory, IEEE Transactions on , vol.20, no.4, pp.423,432, Jul 1974.
Post a Comment