Hypothesis selection for evidential reasoning systems

• US 6,304,833 B1
• Filed: 04/27/1999
• Issued: 10/16/2001
• Est. Priority Date: 04/27/1999
• Status: Active Grant

• Current Assignee: the united states of america as represented by the secretary of the navy
• Original Assignee: the united states of america as represented by the secretary of the navy
• Inventors: Hammel, Sherry E., Ferkinhoff, David J., Nardone, Steven C., Gong, Kai F.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US09/301,383
• Time in Patent Office: 903 Days
• Field of Search: 703/2, 703/3, 706/49, 706/12, 706/13, 706/14, 706/9, 706/47, 706/52, 382/103, 382/226, 382/240, 382/450, 324/323, 324/345, 342/450
• US Class Current: 703/2
• CPC Class Codes: G01S 5/18 using ultrasonic, sonic, or infrasonic waves

Abstract

A method for the selection of hypotheses for modeling physical phenomena, includes detecting if selected features are present by analyzing actual sensed data and parameter values of an initial physical phenomena model; comparing feature estimating hypotheses to the actual data for determining a belief probability assignment value (bpa) for each of the hypotheses which indicates the likelihood that the selected features exist in the actual data and the likelihood that such selected features cannot accurately be determined as existing due to the presence of noise; selecting a set of the hypotheses most accurately modeling the physical phenomena based on the bpa of each selected hypotheses meeting a predetermined criteria; generating evidential support values and lack of evidential support values for subsets of the set having non-zero subset bpa'"'"'s; ranking the subsets having non-zero subset bpa'"'"'s in order of decreasing subset bpa; unioning subsets of the power set for forming unioned subsets and determining support values and plausibility values for the unioned subsets; comparing the unioned evidential support values to a predefined threshold value; and using at least one of the unioned subsets having a unioned evidential support value most closely approximating or exceeding the threshold value for selecting alternate models having selected features which more closely approximate the actual data.

Claims

1. A method for the selection of hypotheses for modeling physical phenomena, comprising the selection steps of:

sensing actual data from said physical phenomena;

providing an initial model of said physical phenomena comprising parameter values which represent said actual data if said actual data was sensed in the absence of noise;

detecting if selected features are present by analyzing said actual data and parameter values;

extracting said selected features if present using hypotheses for estimating said selected features;

comparing said hypotheses to said actual data for determining a belief probability assignment value for each of said hypotheses which indicates the likelihood that said selected features exist in said actual data and the likelihood that such selected features cannot accurately be determined as existing due to the presence of noise and for determining the strength and variance of said estimated selected features as represented by said hypotheses relative to said actual data;

selecting a set of said hypotheses believed to most accurately model said physical phenomena based on said belief probability assignment values of said hypotheses meeting a predetermined criteria;

determining subsets of said set and a subset belief probability for each of said subsets;

generating evidential support values and lack of evidential support values for each of said subsets having non-zero subset belief probability assignment values, wherein said evidential support value is indicative of the amount of confirming evidence for each of said hypotheses and said lack of evidential support value is indicative of a lack of supporting evidence for each of said hypotheses;

ranking said subsets having non-zero subset belief probability assignment values in order of decreasing subset belief probability assignment values for forming a power set;

unioning subsets of said power set for forming unioned subsets and determining unioned evidential support values for said unioned subsets and unioned belief probability assignment values for said unioned subsets;

thresholding said unioned subsets by comparing said unioned evidential support values to a predefined threshold value; and

using at least one of said unioned subsets having a unioned evidential support value most closely approximating or exceeding said threshold value for selecting alternate models having selected features which more closely approximate said actual data.

2. The method according to claim 1 further comprising the step of iteratively repeating said selection steps until a unioned subset having a unioned evidential support value equalling or exceeding said threshold value is determined.

3. The method according to claim 1 wherein the step of thresholding includes defining said threshold value as having a value less than one.

4. The method according to claim 3 wherein said step of thresholding further comprises selecting said unioned subset having a unioned evidential support value meeting said threshold value.

5. The method according to claim 1 wherein said step of generating further includes using the Dempster-Shafer frame of evidential reasoning for generating said evidential support values and lack of evidential support values for each of said subsets having non-zero subset belief probability assignment values.

6. The method according to claim 1 wherein said step of unioning includes combining said subsets of said power set in order of decreasing subset belief probability assignment values.

7. The method according to claim 6 wherein said step of unioning comprises:

designating a one of said subsets with a highest subset belief probability assignment value as the first unioned subset;

combining said first unioned subset with another one of said subsets having a next highest subset belief probability assignment and creating a next unioned subset;

further combining said next unioned subset with another one of said subsets having a next highest belief probability assignment and creating a new next unioned subset; and

repeating said step of combining said next unioned subset for said new next unioned subset.

8. The method according to claim 1 further comprising the step of ranking said unioned subsets in order of decreasing unioned belief probability assignment values.

9. The method according to claim 1 further comprising the step of attributing actual values to said actual data.

10. The method according to claim 9 further comprising the step of determining residual values indicative of differences between said actual values and said parameter values.

11. The method according to claim 10 wherein said step of detecting further comprises analyzing said residual values while analyzing said actual data and said parameter values.

12. The method according to claim 10 wherein said step of extracting comprises applying said hypotheses estimating selected features to said residual values.

13. The method according to claim 1 further comprising the steps determining a level of belief in said strength and variance.

14. A system for the selection of hypotheses for modelling physical phenomena, comprising:

means for sensing actual data from said physical phenomena;

initial model storage means for providing an initial model of said physical phenomena comprising parameter values which represent said actual data if said actual data was sensed in the absence of noise;

feature estimator means for detecting if selected features are present by analyzing said actual data and parameter values;

feature extraction means for extracting said selected features if present by using hypotheses for estimating said selected features;

feature representation means for comparing said hypotheses to said actual data for determining a belief probability assignment value for each of said hypotheses which indicates the likelihood that said selected features exist in said actual data and the likelihood that such selected features cannot accurately be determined as existing due to the presence of noise and for determining the strength and variance of said estimated selected features as represented by said hypotheses relative to said actual data;

feature interpretation means for selecting a set of said hypotheses believed to most accurately model said physical phenomena based on said belief probability assignment values of said hypotheses meeting a predetermined criteria determining subsets of said set and a subset belief probability for each of said subsets;

evidential reasoning means for generating evidential support values and lack of evidential support values for each of said subsets having non-zero subset belief probability assignment values, wherein said evidential support value is indicative of the amount of confirming evidence for each of said hypotheses and said lack of evidential support value is indicative of a lack of supporting evidence for each of said hypotheses, and further for ranking said subsets having non-zero subset belief probability assignment values in order of decreasing subset belief probability assignment values for forming a power set;

model selection means for unioning all subsets of said power set for forming unioned subsets and determining unioned evidential support values for said unioned subsets and unioned belief probability assignment values for said unioned subsets, and for thresholding said unioned subsets by comparing said unioned evidential support values to a predefined threshold value; and

alternate model storage means for using at least one of said unioned subsets having a unioned evidential support value most closely approximating or exceeding said threshold value for selecting alternate models having selected features which more closely approximate said actual data.

15. The system according to claim 14 further comprising means for iteratively repeating said selection steps until a unioned subset having a unioned evidential support value equalling or exceeding said threshold value is determined.

16. The system according to claim 14 wherein said threshold value has a value of less than one.

17. The system according to claim 16 wherein said model selection means further includes means for selecting said unioned subset having a unioned evidential support value meeting said threshold value.

18. The system according to claim 14 wherein said evidential reasoning means comprises means for implementing the Dempster-Shafer frame of evidential reasoning for generating said evidential support values and said lack of evidential support values for each said subsets having non-zero subset belief probability assignment values.

19. The system according to claim 14 wherein said model selection means comprises means for combining said subsets of said power set in order of decreasing subset belief probability assignment values.

20. The system according to claim 19 wherein said means for combining comprises:

means for designating a one of said subsets with a highest subset belief probability assignment value as the first unioned subset;

means for combining said first unioned subset with another one of said subsets having a next highest subset belief probability assignment and creating a next unioned subset;

means for further combining said next unioned subset with another one of said subsets having a next highest belief probability assignment and creating a new next unioned subset; and

means for repeating said step of combining said next unioned subset for said new next unioned subset.

21. The system according to claim 14 wherein said evidential reasoning means includes means for ranking said unioned subsets in order of decreasing unioned belief probability assignment values.

22. The system according to claim 14 wherein said means for sensing comprises means for attributing actual values to said actual data.

23. The system according to claim 22 wherein said feature estimator means includes means for determining residual values indicative of differences between said actual values and said parameter values.

24. The system according to claim 23 wherein said feature estimator means further comprises means for analyzing said residual values while analyzing said actual data and said parameter values.

25. The system according to claim 23 wherein said feature extraction means includes means for applying said hypotheses to said residual values for estimating said selected features.

26. The method according to claim 14 wherein said feature and hypotheses representation means includes means for determining a level of belief in said strength and variance.

27. The system according to claim 14 wherein said physical phenomena comprises a moving target and said selected features comprise at least one of linear drift in a sensed signal from said target, discontinuity in said sensed signal, jump in said sensed signal, non-linearity of said sensed signal, and curvature of said sensed signal.