Selectively resampling particle filter

• US 7,058,550 B2
• Filed: 06/25/2004
• Issued: 06/06/2006
• Est. Priority Date: 06/25/2003
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Kouritzin, Michael A.
• Primary Examiner(s): Nghiem, Michael
• Assistant Examiner(s): Sun, Xiuqin
• Application Number:
  US10/877,879
• Publication Number:
  US 20050049830A1
• Time in Patent Office: 711 Days
• Field of Search: 702/189, 702/190, 702179-181, 702/198, 702/199, 375/315, 375/341, 375/316, 706 46- 48, 700/174, 166/255.1, 324/204, 250/397, 356/337, 356/484
• US Class Current: 702/189
• CPC Class Codes: G05B 13/021 in which a variable is automatically adjusted to optimise the performance

Abstract

A method, and program for implementing such method, for use in estimating a conditional probability distribution for past signal states, current signal states, future signal states, and/or complete pathspace of a non-linear random dynamic signal process, includes providing sensor measurement data associated therewith and state data including at least location and weight information associated with each of a plurality of particles as a function thereof. An estimate of the conditional probability distribution is compared for the signal state based on the state data for particles under consideration and such particles are resampled upon receipt of sensor measurement data. The resampling includes comparing weight information associated with a first particle (e.g., the highest weighted particle) with weight information associated with a second particle (e.g., the lowest weighted particle) to determine if the state data of the first and second particles is to be adjusted.

Claims

1. A real time method for use in estimating a conditional probability distribution for past signal states, current signal states, future signal states, and/or complete pathspace of a non-linear random dynamic signal process, the method comprising:

providing sensor measurement data from one or more sensors associated with the non-linear random dynamic signal process, wherein the sensor measurement data is dependent on some component of a sampled signal;

providing state data for a plurality of particles as a function of the sensor measurement data that collectively probabilistically represents the state of the non-linear random dynamic signal process at time t, wherein the state data comprises at least location and weight information associated with each particle;

computing an estimate of the conditional probability distribution for the signal state of the non-linear random dynamic signal process at time t based on the state data for particles under consideration; and

resampling the particles under consideration upon receipt of sensor measurement data, wherein resampling the particles comprises at least comparing weight information associated with a first particle with weight information associated with a second particle to determine if the state data of the first and second particles is to be adjusted, wherein the first particle is the highest weighted particle under consideration and the second particle is the lowest weighted particle under consideration.

2. The method of claim 1, wherein comparing the weight information associated with the first particle with the weight information associated with the second particle comprises determining whether a function based on such weight information for the pair of first and second particles satisfies one or more defined control parameters.

3. The method of claim 2, wherein the method further comprises experimentally determining, off-line, optimal values for the one or more defined control parameters.

4. The method of claim 3, wherein the method further comprises determining optimal values for the one or more defined control parameters using at least one of dynamic programming and reinforced learning.

5. The method of claim 1, wherein at least the weight information for the particles under consideration is represented in a hash table data structure to segregate the particles into groups with approximately the same associated weight.

6. The method of claim 1, wherein comparing the weight information associated with the first particle with the weight information associated with the second particle comprises averaging the weight information associated with both the first and second particles if the state data thereof is to be adjusted.

7. The method of claim 1, wherein resampling the particles under consideration comprises repeatedly comparing the state data of particles until weight information associated with all pairs of the particles under consideration satisfies one or more defined control parameters.

8. The method of claim 1, wherein the method further comprises evolving all particles independently of one another after resampling the particles.

9. The method of claim 8, wherein the method further comprises reweighting all particles under consideration using sensor measurement data after evolving the resampled particles.

10. The method of claim 8, wherein evolving all particles independently comprises simulating the evolution of each particle using explicit solutions.

11. The method of claim 1, wherein the non-linear random dynamic signal process is associated with multiple independent targets, and wherein the method further comprises simulating the multiple targets by separating target paths from the particles under consideration.

12. The method of claim 1, wherein the method further comprises storing state data of the particles for use in providing particle paths based on ancestral states thereof, wherein one or more particles may have the same ancestral states.

13. The method of claim 12, wherein intermediate ancestral state data is generated at selected instances of time to facilitate calculation of asymptotically optimal smoothing and historical filters.

14. The method of claim 12, wherein state data for the earliest stored ancestral states is discarded if a most recent measurement time is greater than a defined span of time from creation of the state data for the earliest stored ancestral state.

15. The method of claim 1, wherein the method further comprises estimating a joint conditional probability that the non-linear random dynamic signal process is represented by any set of possible particle paths at various past, current, and future instants of time given sampled data up to the current time, wherein estimating the joint conditional probability comprises assigning weight information of the particles under consideration to each of the possible particle paths with common ancestors being counted in each of particle paths they are in, wherein a pathspace conditional distribution given observations up to a given time is then calculated as a weighted average over such paths.

16. A computer readable medium comprising a program operable in conjunction with one or more processors of a computer system to implement a filter for past signal states, current signal states, future signal states, and/or complete pathspace of a non-linear random dynamic signal process, wherein the program is operable to:

recognize sensor measurement data provided from one or more sensors associated with the non-linear random dynamic signal process, wherein the sensor measurement data is dependent on some component of a sampled signal;

provide state data for a plurality of particles as a function of the sensor measurement data that collectively probabilistically represents the state of the non-linear random dynamic signal process at time t, wherein the state data comprises at least location and weight information associated with each particle;

compute an estimate of the conditional probability distribution for the signal state of the non-linear random dynamic signal process at time t based on the state data for particles under consideration; and

resample the particles under consideration upon receipt of sensor measurement data, wherein resampling the particles comprises at least comparing weight information associated with a first particle with weight information associated with a second particle to determine if the state data of the first and second particles is to be adjusted, wherein the first particle is the highest weighted particle under consideration and the second particle is the lowest weighted particle under consideration.

17. The computer readable medium of claim 16, wherein the program is further operable to determining whether a function based on such weight information for the pair of first and second particles satisfies one or more defined control parameters.

18. The computer readable medium of claim 16, wherein at least the weight information for the particles under consideration is represented in a hash table data structure to segregate the particles into groups with approximately the same associated weight.

19. The computer readable medium of claim 16, wherein the program is further operable to average the weight information associated with both the first and second particles if the state data thereof is to be adjusted.

20. The computer readable medium of claim 16, wherein the program is further operable to repeatedly compare the state data of particles until weight information associated with all pairs of the particles under consideration satisfies one or more defined control parameters.

21. The computer readable medium of claim 16, wherein the program is further operable to evolve all particles independently of one another after resampling the particles.

22. The computer readable medium of claim 21, wherein the program is further operable to reweight particles under consideration using sensor measurement data after evolving the resampled particles.

23. The computer readable medium of claim 22, wherein the program is further operable to evolve all particles independently by simulating the evolution of each particle using explicit solutions.

24. The computer readable medium of claim 16, wherein the non-linear random dynamic signal process is associated with multiple independent targets, and wherein the program is further operable to simulate the multiple targets by separating target paths from the particles under consideration.