Particle filtering method and navigation system using measurement correlation

Patent metadata

Field	Value
Publication number	US-12112280-B2
Application number	US-202017612753-A
Country	US
Kind code	B2
Filing date	Apr 10, 2020
Priority date	May 22, 2019
Publication date	Oct 8, 2024
Grant date	Oct 8, 2024

Abstract

A method for box regularized particle filtering, used to predict a state of a system, is modified such that it can be implemented in a parallel manner. The modification concerns a step of redistributing state intervals and in particular a determination of a number of sub-intervals intended to replace each state interval. The method is particularly suitable for being implemented in a navigation system with measurement correlation, for example an aircraft navigation system using ground-correlation, and for being executed by a field-programmable or fixed-gate array circuit.

First claim

The invention claimed is:

1. A method of box regularized particle filtering, for predicting a state of a system, comprising at least one execution of a sequence which includes the following steps:
/ 1 / a prediction step, comprising a predicting of subsequent state intervals, each subsequent state interval being obtained by applying at least one propagation rule to one among a plurality of previous state intervals;
/ 2 / a step of measuring a actual state of the system;
/ 3 / a step of contracting at least one of the subsequent state intervals, as a function of at least one measurement result of the actual state that was obtained in step / 2 /;
/ 4 / a weight update step, comprising an assigning of a weight to each subsequent state interval as a function of a size of said subsequent state interval as resulting from step / 3 /, of a size of said subsequent state interval as resulting from step / 1 / before step / 3 /, and of a weight of the previous state interval from which said subsequent state interval resulted during step / 1 /; and
/ 5 / a step of redistributing the subsequent state intervals, comprising a replacing of at least one of the subsequent state intervals i by n i sub-intervals obtained from a division of subsequent state interval i, i being an integer index numbering the subsequent state intervals and n i being a number of the sub-intervals which replace said subsequent state interval i, each sub-interval being intended to constitute a previous state interval for a subsequent iteration of the sequence of steps / 1 / to / 5 /,

wherein step / 5 / comprises an initializing of the number of sub-intervals n i , and comprises the sequence of following sub-steps / 5 - 1 / to / 5 - 4 / which is performed for each of the subsequent state intervals alternatively used as a reference interval:
/ 5 - 1 / initially adopting the reference interval as retained state interval;
/ 5 - 2 / obtaining a number which is between 0 and 1, called random factor, by a drawing method considered to be random, and selecting one of the subsequent state intervals, different or not different from the reference interval, as a comparison interval, by a selection method considered to be random;
/ 5 - 3 / if a result of multiplying the random factor by the weight of the reference interval, as updated in step / 4 /, is less than the weight of the comparison interval, also as updated in step / 4 /, then replacing the previously retained state interval by the comparison interval;

sub-steps / 5 - 2 / and / 5 - 3 / being repeated several times for each subsequent state interval used as a reference interval, then
/ 5 - 4 / incrementing by one the number of sub-intervals intended to replace the state interval that is retained at the end of the repetition of sub-steps / 5 - 2 / and / 5 - 3 /; and

each subsequent state interval then being replaced in a sub-step / 5 - 5 / by sub-intervals obtained from a division of said subsequent state interval, in accordance with the number of sub-intervals which results for said subsequent state interval from all executions of sub-step / 5 - 4 /.

2. The method of claim 1 , wherein sub-steps / 5 - 2 / and / 5 - 3 / are repeated a number of times which is between 1 and 100 for each subsequent state interval used as a reference interval.

3. The method of claim 2 , wherein step / 5 / is performed only if a representativeness criterion is not satisfied by the weights of the subsequent state intervals as updated in step / 4 /.

4. The method of claim 2 , wherein, in step / 4 /, the updated weight of each subsequent state interval is equal to the weight of the previous state interval from which resulted said subsequent state interval in step / 1 /, multiplied by the size of the subsequent state interval as resulting from step / 3 /, and divided by the size of the subsequent state interval as resulting from step / 1 / before the application of step / 3 / to said subsequent state interval.

5. The method of claim 2 , wherein step / 5 / further comprises the following additional sub-step, performed after each subsequent state interval has been replaced by sub-intervals obtained by dividing said subsequent state interval:
/ 5 - 6 / a kernel-smoothing sub-step, during which at least one of the sub-intervals and a weight associated with said sub-interval are modified according to a probability kernel in order to form a previous state interval intended to be used for the subsequent iteration of the sequence of steps / 1 /through / 5 /.

6. The method of claim 2 , wherein, at each execution of sub-step / 5 - 2 /, the random factor is obtained by a linear-feedback shift-register type of method, and/or the comparison interval is selected by a linear-feedback shift-register type of method.

7. The method of claim 1 , wherein step / 5 / is performed only if a representativeness criterion is not satisfied by the weights of the subsequent state intervals as updated in step / 4 /.

8. The method of claim 7 , wherein, in step / 4 /, the updated weight of each subsequent state interval is equal to the weight of the previous state interval from which resulted said subsequent state interval in step / 1 /, multiplied by the size of the subsequent state interval as resulting from step / 3 /, and divided by the size of the subsequent state interval as resulting from step / 1 / before the application of step / 3 / to said subsequent state interval.

9. The method of claim 7 , wherein step / 5 / further comprises the following additional sub-step, performed after each subsequent state interval has been replaced by sub-intervals obtained by dividing said subsequent state interval:
/ 5 - 6 / a kernel-smoothing sub-step, during which at least one of the sub-intervals and a weight associated with said sub-interval are modified according to a probability kernel in order to form a previous state interval intended to be used for the subsequent iteration of the sequence of steps / 1 /through / 5 /.

10. The method of claim 1 , wherein, in step / 4 /, the updated weight of each subsequent state interval is equal to the weight of the previous state interval from which resulted said subsequent state interval in step / 1 /, multiplied by the size of the subsequent state interval as resulting from step / 3 /, and divided by the size of the subsequent state interval as resulting from step / 1 / before the application of step / 3 / to said subsequent state interval.

11. The method of claim 10 , wherein step / 5 / further comprises the following additional sub-step, performed after each subsequent state interval has been replaced by sub-intervals obtained by dividing said subsequent state interval:
/ 5 - 6 / a kernel-smoothing sub-step, during which at least one of the sub-intervals and a weight associated with said sub-interval are modified according to a probability kernel in order to form a previous state interval intended to be used for the subsequent iteration of the sequence of steps / 1 /through / 5 /.

12. The method of claim 1 , wherein step / 5 / further comprises the following additional sub-step, performed after each subsequent state interval has been replaced by sub-intervals obtained by dividing said subsequent state interval:
/ 5 - 6 / a kernel-smoothing sub-step, during which at least one of the sub-intervals and a weight associated with said sub-interval are modified according to a probability kernel in order to form a previous state interval intended to be used for the subsequent iteration of the sequence of steps / 1 / through / 5 /.

13. The method of claim 1 , wherein, at each execution of sub-step / 5 - 2 /, the random factor is obtained by a linear-feedback

Assignees

• Office National Detudes Rech Aerospatiales

Inventors

• Merlinge Nicolas
• Audebert Clément
• Dahia Karim
• Herisse Bruno
• Allard Jean-Michel

Classifications

• G07C5/0808

  Diagnosing performance data (testing of vehicles G01M17/00; testing of electrical installation on vehicles G01R31/005) · CPC title

• G01C21/165 Primary

  combined with non-inertial navigation instruments · CPC title

• G01C21/188

  for accumulated errors, e.g. by coupling inertial systems with absolute positioning systems · CPC title

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title