Method for locating a device which is moved in a three-dimensional space

• US 10,408,970 B2
• Filed: 06/17/2015
• Issued: 09/10/2019
• Est. Priority Date: 06/18/2014
• Status: Active Grant

• Current Assignee: Commissariat a L'Energie Atomique (AES Corporation), Movea
• Original Assignee: Movea
• Inventors: Villien, Christophe
• Primary Examiner(s): Nguyen, Duy T
• Application Number:
  US14/741,818
• Publication Number:
  US 20150369958A1
• Time in Patent Office: 1,546 Days
• Field of Search: 702152
• CPC Class Codes: G01B 21/16 for measuring distance of clearance between spaced objects
• CPC Class Codes: G01C 21/166 Mechanical, construction or arrangement details of inertial navigation systems
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01V 9/00 Prospecting or detecting by methods not provided for in groups G01V1/00 - G01V8/00

Abstract

A method of location of a device includes a displacement law containing a corrective factor of a bias combined by an arithmetical operation with a measured variable, and particles, each particle being associated with a current value of the corrective factor. The current value of the corrective factor being constructed at each iteration on the basis of a previous current value of the corrective factor, computed during a previous iteration, to which is added a random variable drawn according to a predefined probability law. The current values of various particles are initialized, before the first iteration, to various initial values, and during each iteration, for each particle whose coordinates are updated with the aid of this displacement law, the value of the corrective factor in the displacement law is taken equal to this corrective factor'"'"'s current value associated with the particle.

Claims

1. A method comprising locating a device that has been displaced inside a three-dimensional space, wherein said device comprises

an inertial platform,

an electronic locating-unit, and

a bus,

wherein said electronic locating-unit comprises a programmable electronic computer and a memory,

wherein said programmable electronic computer is capable of executing instructions stored in said memory,

wherein said inertial platform comprises sensors that are onboard said displaced device, wherein said sensors comprise an accelerometer,

wherein said bus connects said inertial platform to said electronic locating-unit,

wherein said electronic-locating unit is configured to detect, based at least in part on measurements provided by said accelerometer and provided to said electronic locating-unit by said bus, movement of said inertial platform, said movement being indicative of said displacement of said device,

wherein said memory stores a map of said three-dimensional space and instructions for execution by said programmable electronic computer,

wherein said method comprises

executing a first step,

executing a second step,

repeating a sequence of steps, said sequence comprising

a third step,

a fourth step, and

a fifth step,

wherein said first step comprises providing said map of said three-dimensional space and of predefined constraints on displacements of said device in said three-dimensional space,

wherein said second step comprises generating a number of distinct particles, said number depending on initial knowledge about a location of said device, wherein each of said distinct particles is associated with coordinates that code a position of said particle in said map and a weight that represents a probability that said device is situated at said position,

wherein said third step comprises receiving measurements representative of a magnitude and direction of displacement of said device from a previous position thereof, said measurements having been carried out by said sensors onboard said displaced device,

wherein said fourth step comprises executing a transformation of each particle, wherein executing a transformation comprises updating coordinates of positions of each particle as a function of said measurements received during said third step with the aid of a predetermined displacement law, said predetermined displacement law being a law for displacing said particle from a previous position to a new position in a manner that is correlated with said measured displacement of said device, each displacement law comprising a first measured-variable and a second measured-variable, said first measured-variable having a value that depends on said measurement of said direction of displacement received during said third step and said second measured-variable having a value that depends on said measurement of said amplitude of said displacement received during said third step,

wherein said fifth step comprises, for each particle, if a latest displacement of said particle from said previous position to said new position satisfies said predefined constraints, increasing said weight associated with said particle relative to weights of said particles whose latest displacement fails to satisfy said predefined constraints, said weights comprising highest weights and lowest weights,

wherein said fifth step comprises estimating said position of said device on said basis of said positions of said particles and of said weights associated with said particles,

wherein estimating said position of said device comprises allotting more importance to positions of particles associated with said highest weights,

wherein said displacement law comprises using an arithmetical operation to combine a corrective factor with one of said measured variables, said corrective factor being corrective of a bias,

wherein each particle is associated with a current value of said corrective factor, said current value of said corrective factor being constructed at each iteration of said fourth step based on a previous current-value of said corrective factor that was computed during a previous iteration of said fourth step and to which is added a random variable drawn according to a predefined probability law, said current values of various particles having been initialized to corresponding initial values before said first execution of said fourth step, and

wherein, during said fourth step, for each particle whose coordinates are updated with said aid of said displacement law, said value of said corrective factor in said displacement law is set equal to said current value of said corrective factor associated with said particle, after several iterations of said sequence of steps, re-sampling said particles,

wherein resampling said particles comprises carrying out another transformation on said set of particles,

wherein said another transformation comprises eliminating particles that are associated with said lowest weights, automatically generating new particles to replace said eliminated particles, and assigning a new current-value of said corrective factor to each new particle, each new value of said corrective factor being dependent on one or more of said corrective factor'"'"'s current values associated with said particles that have not been eliminated and independent of said corrective factor'"'"'s current values associated with said particles that have been eliminated.

2. The method of claim 1, wherein, in the displacement law, the corrective factor is added to or multiplied by the second measured variable, and the variation of the standard deviation σ

ε

of the predefined probability law is maintained below 10% per second for more than 90% of the time of use of the method for locating the device, wherein the variation of the standard deviation, σ

ε

, is given by Σ

σ

ε

k/T, wherein σ

ε

k is the standard deviation of the predefined probability law during the k^th iteration of the fourth step, wherein Σ

σ

ε

k is the sum of the standard deviations, σ

ε

k, between the q^th iteration and the p^th iteration of the fourth step, wherein q is an integer that is less than p, and wherein T is the duration, in seconds, of the time interval that has elapsed between the q^th and the p^th iteration of the fourth step.

3. The method of claim 1, wherein the corrective factor is, in the displacement law, added to or multiplied by the first measured variable and the variation of the standard deviation σ

α

of the predefined probability law is maintained below 10°

per second for more than 90% of the time of use of the method for locating the device, wherein the variation of the standard deviation σ

α

is given by Σ

σ

α

k/T, wherein σ

α

k is the standard deviation of the predefined probability law during the k^th iteration of the fourth step wherein Σ

σ

α

k is the sum of the standard deviations σ

α

k between the q^th iteration and the p^th iteration of the fourth step, wherein q is an integer that is less than p, and wherein T is the duration in seconds of the time interval that has elapsed between the q^th and the p^th iteration of the fourth step.

4. The method of claim 1, wherein, during the first step, the predefined constraints comprise coordinates that code positions and dimensions of obstacles that are impassable to the device in the three-dimensional space, and wherein the fifth step comprises, for each particle searching for an intersection between a segment that is defined between the previous position and the new position of the particle and an impassable obstacle by using coordinates of the impassable obstacle, the coordinates having been provided during the first step, decreasing the weight associated with the particle if such an intersection exists and, in the converse case, neither increasing nor decreasing the weight associated with the particle.

5. The method of claim 4, wherein the map that was provided during the first step contains several distinct zones, wherein each distinct zone is associated with coordinates and a list of identifiers, wherein the coordinates delimit a periphery of the distinct zone, wherein the identifiers identity only those impassable objects that are inside the distinct zone, wherein the fifth step comprises, for each particle, identifying the distinct zone in which the particle is situated by comparing updated coordinate of the particle with peripheries of the distinct zones on the map, the coordinates of the peripheries having been provided during the first step, and having identified the distinct zone in which the particle is situated, searching only for an intersection between the segment and the impassable objects that are identified by the identifiers in the list of identifiers as being in the distinct zone.

6. The method of claim 1, wherein, the map provided during the first step includes distinct zones, wherein each distinct zone is associated with coordinates and a selected displacement law, the selected displacement law having been selected from a set of several different displacement laws, wherein the coordinates define a periphery of the distinct zone on the map, wherein the selected displacement law associated with the distinct zone is selected to be associated with the distinct zone because the selected displacement law estimates a value more precisely than other displacement laws in said set of displacement laws, wherein the value that the selected displacement law estimates more precisely is an estimate of an amplitude and direction of displacement of the device when the device is situated inside the distinct zone, wherein the estimate is based on measurements received during the third step, wherein the displacement laws in the set of displacement laws differ from one another by using different mathematical operations to estimate the coordinates of the particle based on the measurements received during the third step wherein the fourth step systematically comprises, for each particle, executing a first operation and a second operation, wherein the first operation comprises identifying the distinct zone in which the particle is situated by comparing coordinates of the particle with peripheries of the distinct zones on the map, said distinct zones having been identified by coordinates provided during the first step, and wherein the second operation comprises updating the coordinates of the particle using only the displacement law associated with the distinct zone identified in the first operation.

7. The method of claim 1, wherein the map provided during the first step contains a zone having a favored displacement-direction, coordinates that define the position of the periphery of the zone, and the favored displacement-direction of the zone, wherein the fifth step comprises, for each particle, detecting the presence of the particle in the zone by comparing the coordinates of the particle with the periphery of the zone as defined by the coordinates provided during the first step, if the particle is detected as being in the zone and if a displacement of the particle within the zone satisfies a condition, increasing the weight associated with the particle, wherein the displacement of the particle satisfies the condition if an angular deviation between the favored displacement-direction and the displacement of the particle between a previous position and a new position thereof is within a pre-selected tolerance of an angle selected from the group consisting of 0°

and 180°

, wherein increasing the weight comprises increasing the weight relative to other particles within the zone, wherein for each of the other particles, the displacement of that particle fails to satisfy the condition, and if the particle is detected as being outside the zone, prohibiting the use of the favored displacement-direction when updating the weight assigned to the particle.

8. The method of claim 1, wherein said inertial platform further comprises a barometer, a gyrometer, a magnetometer, wherein said magnetometer is a triaxial magnetometer, wherein said accelerometer is triaxial.

9. A manufacture comprising a non-transitory computer-readable medium having encoded thereon instructions that, when executed by said electronic computer, cause said electronic computer to execute the method recited in claim 1.

10. An apparatus for locating a device displaceable inside a three-dimensional space, the apparatus comprising

a memory and

a processor,

wherein the memory contains a map of the three-dimensional space and predefined constraints on the displacements of the device in the three-dimensional space, and

wherein the processor is configured to execute a first step, execute a second step, repeat a sequence of steps, the sequence comprising a third step, a fourth step, and a fifth step, wherein the first step comprises providing the map of the three-dimensional space and of predefined constraints on displacements of the device in the three-dimensional space, wherein the second step comprises generating distinct particles, each of the distinct particles being associated with coordinates that code a position of the particle in the map and with a weight that represents a probability that the device is situated at the position, wherein the third step comprises receiving measurements representative of a magnitude and direction of displacement of the device from a previous position thereof, the measurements having been carried out by sensors onboard the displaced device, wherein the fourth step comprises updating coordinates of positions of each particle as a function of the measurements received during the third step with the aid of a predetermined displacement law, the displacement law being a law for displacing the particle from a previous position to a new position in a manner that is correlated with the measured displacement of the device, each predetermined displacement law comprising a first measured-variable and a second measured-variable, the first measured-variable having a value that depends on the measurement of the direction of displacement received during the third step and the second measured-variable having a value that depends on the measurement of the amplitude of the displacement received during the third step, wherein the fifth step comprises, for each particle, if the latest displacement of the particle from the previous position to the new position satisfies the predefined constraints, increasing the weight associated with the particle relative to weights of the particles whose latest displacement fails to satisfy the predefined constraints, the weights comprising highest weights and lowest weights, wherein the fifth step comprises estimating the position of the device on the basis of the positions of the particles and of the weights associated with the particles, wherein estimating the position of the device comprises allotting more importance to positions of particles associated with the highest weights, wherein the displacement law comprises using an arithmetical operation to combine a corrective factor with one of the measured variables, the corrective factor being corrective of a bias, wherein each particle is associated with a current value of the corrective factor, the current value of the corrective factor being constructed at each iteration of the fourth step based on a previous current-value of the corrective factor that was computed during a previous iteration of the fourth step and to which is added a random variable drawn according to a predefined probability law, the current values of various particles having been initialized to corresponding initial values before the first execution of the fourth step, and wherein, during the fourth step, for each particle whose coordinates are updated with the aid of the displacement law, the value of the corrective factor in the displacement law is set equal to the current value of the corrective factor associated with the particle, after several iterations of said sequence of steps, re-sampling the particles, wherein resampling the particles comprises eliminating particles that are associated with the lowest weights, automatically generating new particles to replace the eliminated particles, and assigning a new current-value of the corrective factor to each new particle, each new value of the corrective factor being dependent on one or more of the corrective factor'"'"'s current values associated with the particles that have not been eliminated and independent of the corrective factor'"'"'s current values associated with the particles that have been eliminated.

11. The apparatus of claim 10, further comprising a portable electronic locating-unit that is directly transportable by a pedestrian who is moving through the three-dimensional space, the portable electronic locating-unit comprising an inertial platform that is configured to measure physical quantities representative of the amplitude and direction of displacement of the portable electronic locating-unit, wherein the portable electronic locating-unit comprises the memory and the processor.