Method for creating a map relating to location-related data on the probability of future movement of a person

• US 8,626,443 B2
• Filed: 09/20/2010
• Issued: 01/07/2014
• Est. Priority Date: 09/18/2009
• Status: Active Grant

• Current Assignee: Deutsches Zentrum Fã¼R Luft- Und Raumfahrt E.V.
• Original Assignee: Deutsches Zentrum Fã¼R Luft- Und Raumfahrt E.V.
• Inventors: Robertson, Patrick, Angermann, Michael, Krach, Bernhard
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): BRUSHABER, FREDERICK M
• Application Number:
  US13/496,889
• Publication Number:
  US 20120232795A1
• Time in Patent Office: 1,205 Days
• Field of Search: 701/120, 701/532
• US Class Current: 701/532
• CPC Class Codes: G01C 21/3837 Data obtained from a single source
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G01C 22/006 Pedometers

Abstract

The invention relates to a method for creating a map relating to location-related data on the likelihood of the future movement of a person in a spatial environment, such as a building, forest, tunnel system or public place, and in particular a shopping center, airport or train station. In the method according to the invention, at least one person is supplied with one or more sensors (e.g. inertial sensors, rotation rate sensors, optical sensors) for odometrical measurement (odometry) (e.g. attached to a shoe), wherein the odometry has errors due to inherent measurement inaccuracies of the sensor(s) (e.g. angle deviations, length deviations). The at least one person moves by foot through the spatial environment. Information regarding the pedestrian step lengths and/or pedestrian step direction and/or orientation of the sensor or the person (called odometry information Z^u) is determined from the measurement signals of the sensor(s). Based on said odometry information, a map is created using a Bayesian estimator (e.g. particle filter, Rao-Blackwellized particle filter, Kalman filter, Mone-Cario hypothesis filter or combined forms of such filters), the state-variable space thereof (e.g. hypothetical space of the particle of a particle filter) comprising both the current pedestrian step (pedestrian step length and optionally movement direction change as well) of the person U, odometry errors E (e.g. drift parameters with respect to the determined pedestrian step lengths and/or pedestrian step direction and/or orientation of the sensor or the person) and also the location-related data on the probabilities of the future movement of the person.

Claims

1. A method for creating a map relating to location-related data on the likelihood of the future movement of a person in a spatial environment, said method comprising

causing at least one person to carry one or more sensors for odometrical measurement (odometry), wherein the odometry is error-prone due to inherent measurement inaccuracies of the one or more sensors,

causing the at least one person to move by foot through the spatial environment,

determining from measurement signals of the one or more sensors information regarding the pedestrian step lengths and/or pedestrian step direction and/or orientation of the sensor or the person (called odometry information Z^u),

creating a map based on said odometry information using a Bayesian estimator, wherein a state-variable space thereof comprises both the current pedestrian step (pedestrian step length and optionally movement direction change as well) of the person, odometry errors E and also the location-related data on the probabilities of the future movement of the person.

2. The method according to claim 1, wherein said map is created with a delay during the movement of the person through the environment or after storage of the sensor measurement signals or the detected odometry information.

3. The method according to claim 1, wherein the computations for creating the map are performed either on an end device carried by the person, or on a server.

4. The method according to claim 1, comprising the step of using the created map either for positioning or routing of the person or for improved positioning or routing of other persons.

5. The method according to claim 1, wherein, for improvement of the odometry information, use is made of measurement signals/data of one or more further sensors including one or more of satellite navigation, magnetic compass, WLAN, measurements for positioning, mobile phone position measurements, UWB measurements for positioning, and/or that use is made of partial regions of a map of the environment for restricting the state space of the Bayesian estimator.

6. The method according to claim 1, wherein use is made of real or virtual reference marks which can be perceived by the person and whose presence and optionally position are included as further parameters into the state space of the Bayesian estimator.

7. The method according to claim 1, wherein the method is combined with optical SLAM methods known from robotics by including, into the determining of the state space of the Bayesian estimator, the visual features measured by optical sensors.

8. The method according to claim 1, wherein use is made of magnetic sensors by including the respective strength and direction of the local magnetic field as a feature and entering them corresponding to a visual feature into the computations.

9. The method according to claim 1, wherein the person is provided with a plurality of sensors for reducing odometry errors, wherein an improved odometry can be achieved by combining the measurement signals of the plurality of sensors.

10. The method according to claim 1, wherein sensors for odometry can be placed on parts of the body other than the feet/shoes, and that methods known from Pedestrian Dead Reckoning are used for computation and respectively improvement of the odometry.

11. The method according to claim 1, wherein, as a representation of the likelihood density function of the Bayesian estimator, use is made of the following mathematical product:

the conditioned likelihood density of the current odometry errors E, conditioned to the odometry errors in the last time-instant step, multiplied by the conditioned likelihood density of the current pedestrian step vector U, conditioned to the current odometry information Z^u and the current drift parameter E.

12. The method according to claim 1, wherein, for a map relating to location-related data on the likelihood of the future movement of a person in a spatial environment, use is made of data on transition probabilities over edges of spatially arranged polygons, wherein, in case of realization by means of a particle filter, the edge transitions of the particle at each polygon transition for this particle are counted and included into a weight computation.

13. The method according to claim 12, wherein the counters are updated and stored only for one edge between two adjacent polygons and not individually for all edges of all polygons, whereby the required storage capacity can be distinctly reduced.

14. The method according to claim 1, wherein use is made of visual odometry methods known from robotics, wherein, with the aid of optical sensors, use is made of the change of the appearance of the environment for estimating the change of location and position of the person.

15. The method according to claim 1, wherein, with use of polygon representations, e.g. hexagon of the map, the polygon grid is adapted to the environment so as to be configured with varying density, wherein the polygons can overlap and/or a plurality of polygon planes can be used hierarchically and the transition counters are computed separately for each plane, and wherein, in the weight computation of the hypotheses of a particle filter, all planes are included.

16. The method according to claim 1, wherein, if polygons are used for the map, the polygons are configured with overlap or without overlap and/or are regular or irregular and/or are configured in a plurality of planes.

17. The method according to claim 1, wherein, if polygons are used for the map, use is made, instead of using a polygon grid, of a regular or irregular arrangement of circles or ovals or other geometric shapes, wherein, instead of counting an edge transition, there is detected the angle via which the shape is left during a pedestrian step or part of a pedestrian step, and an angle range transition counter is evaluated and updated for this angle, wherein, in case of an over-lapping pattern of shapes, there is always selected that shape whose center is closest to the particle, and, in analogy with the realization by hexagons, the angle range transitions are counted and included in the weight computation.

18. The method according to claim 1, wherein there are evaluated not only the counters for edge transitions and respectively angle range transitions per hexagon or other structure but also those for each combination of any number of previous transitions.

19. The method according to claim 1, wherein, when creating the map, use is made of already created maps of other users or other walks of a person, e.g. by placing the “

a-priori”

counters for edge transitions of polygon maps onto already measured transition counters and/or performing an iterative processing wherein the map creation for an odometry data set is continuously repeated with use of mutually created maps.

20. The method according to claim 1, wherein the created map represents three spatial dimensions.