# US 12,112,280 B2 · Particle filtering method and navigation system using measurement correlation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,112,280 B2 - Document ID: US12112280B2 - Status: Granted - Kind: B2 - Application number: 17/612,753 - Filed: 2020-04-10 - Published: 2022-08-04 - Granted: 2024-10-08 - Earliest claimed: 2019-05-22 - Assignees: Office National d'Etudes et de Recherches Aerospatiales - Applicants: Office National D'Etudes Et De Recherches AéRospatiales - Inventors: Nicolas Merlinge; Clément Audebert; Karim Dahia; Bruno Herisse; Jean-Michel Allard - Web page: https://patentgrep.com/patent/US12112280B2 ## CPC - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G01C 21/165: {combined with non-inertial navigation instruments} - G01C 21/188: {for accumulated errors, e.g. by coupling inertial systems with absolute positioning systems} - G07C 5/0808: {Diagnosing performance data (testing of vehicles G01M17/00; testing of electrical installation on vehicles G01R31/005)} - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G07C: TIME OR ATTENDANCE REGISTERS; REGISTERING OR INDICATING THE WORKING OF MACHINES; GENERATING RANDOM NUMBERS; VOTING OR LOTTERY APPARATUS; ARRANGEMENTS, SYSTEMS OR APPARATUS FOR CHECKING NOT PROVIDED FOR ELSEWHERE ## 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. ## Claims ### Claim 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 ni sub-intervals obtained from a division of subsequent state interval i, i being an integer index numbering the subsequent state intervals and ni 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 ni, 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/. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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/. ### Claim 4 (depends on 2) 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. ### Claim 5 (depends on 2) 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/. ### Claim 6 (depends on 2) 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. ### Claim 7 (depends on 1) 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/. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 7) 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/. ### Claim 10 (depends on 1) 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. ### Claim 11 (depends on 10) 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/. ### Claim 12 (depends on 1) 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/. ### Claim 13 (depends on 1) The method of claim 1, 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. ### Claim 14 (depends on 1) The method of claim 1, wherein sub-steps /5-1/ through /5-5/ are carried out in parallel for all of the subsequent state intervals that are each used as the reference interval. ### Claim 15 (depends on 1) The method of claim 1, wherein the system is an aircraft, the state of the system comprises coordinates of position, velocity, and attitude of the aircraft during flight, and wherein each measurement of the actual state of the system provides a value of a distance which exists between the aircraft and a ground point. ### Claim 16 (depends on 1) A computing unit, comprising at least a first input suitable for receiving results of repeated measurements of acceleration and angular velocity of a system, a second input suitable for receiving results of repeated measurements of an actual state of the system, in addition to the measurements of acceleration and angular velocity, and the computing unit being arranged to execute a method of box regularized particle filtering in accordance with claim 1, so as to output a series of state intervals with respective weights, the weight associated with each of the state intervals corresponding to a probability value that the actual state of the system is within said state interval. ### Claim 17 (depends on 16) The computing unit of claim 16, of the field-programmable gate array type, fixed-gate array type, or central processing unit type. ### Claim 18 (depends on 16) The computing unit of claim 16, comprising several computing sub-units intended to be dedicated one-to-one to the subsequent state intervals, and suitable for executing in parallel at least sub-steps /5-1/ to /5-5/, for all subsequent state intervals. ### Claim 19 (depends on 9) A navigation system with measurement correlation, adapted for being carried on board a vehicle, comprising: an inertial measurement unit, adapted for iteratively measuring accelerations and angular velocities of the vehicle, and for deducing, using measurement results for the accelerations and angular velocities, subsequent state intervals respectively based on several previous state intervals, each state of the vehicle comprising position, velocity, and attitude coordinates of said vehicle; a measurement system, adapted for iteratively measuring at least one characteristic of an actual state of the vehicle; and a computing unit in accordance with claim 9, and adapted for reducing at least one drift of the inertial measurement unit among a position drift, a velocity drift, and an attitude drift, by using measurement results of the characteristic of the actual state of the vehicle which are provided by the measurement system. ### Claim 20 (depends on 19) A vehicle comprising a navigation system with measurement correlation which is in accordance with claim 19.