METHOD FOR CREATING A MAP RELATING TO LOCATION-RELATED DATA ON THE PROBABILITY OF FUTURE MOVEMENT OF A PERSON

• US 20120232795A1
• Filed: 09/20/2010
• Published: 09/13/2012
• Est. Priority Date: 09/18/2009
• Status: Active Grant

• Current Assignee: Deutsches Zentrum Fuer Luft- Und Raumfahrt E.V.
• Original Assignee: Deutsches Zentrum Fuer Luft- Und Raumfahrt E.V.
• Inventors: Robertson, Patrick, Krach, Bernhard, Angermann, Michael
• Granted Patent: US 8,626,443 B2
• Time in Patent Office: Days
• 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-20. -20. (canceled)

21. 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, such as in particular a shopping center, airport or train station, wherein, in said method,

at least one person carries one or more sensors such as e.g. inertial sensors, rotation-rate sensors, optical sensors, for odometrical measurement (odometry), e.g. attached to a shoe, wherein the odometry is error-prone due to inherent measurement inaccuracies of the sensor(s) such as 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. hypothesis or particle filter, Rao-Blackwellized particle filter, Kalman filter, Mone-Carlo hypothesis filter or combined forms of such filters), the state-variable space thereof (e.g. hypothetical space of the hypotheses 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.

22. The method according to claim 21, 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.

23. The method according to claim 21, wherein the computations for creating the map are performed either on an end device carried along, e.g. a mobile phone, PDA, portable computer, or on a server.

24. The method according to claim 21, wherein the created map is used either for positioning or routing of the person or for improved positioning or routing of other persons.

25. The method according to claim 21, wherein, for improvement of the odometry information, use is made of measurement signals/data of further sensors, e.g. 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.

26. The method according to claim 21, 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, e.g. by a man/machine interface arranged close to the person, such as e.g. a button, a key, voice input.

27. The method according to claim 21, 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 (e.g. by entering them as contributing factors into the weight computation and/or as the “

importance sampling”

step of the particle—

e.g. as a multiplicative term in the weight, wherein each particle now also carries the state of each observed visual feature and adapts the location and spatial position and the accuracy thereof to the current observation of the features and of the other conditions of the particle, and wherein, further, in the same manner, also features of ultrasonic or infrared or microwave sensor systems are used which thus can be considered and used as parts of the created map and/or can improve the creating of the map on the basis of odometry).

28. The method according to claim 21, wherein use is made of magnetic sensors, such as e.g. electronic magnetic field 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.

29. The method according to claim 21, wherein the person is provided with a plurality of sensors for reducing odometry errors such as e.g. the drift, wherein an improved odometry can be achieved by combining the measurement signals of the plurality of sensors, e.g. by averaging of the odometry information or by averaging the raw data of the sensors.

30. The method according to claim 21, 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.

31. The method according to claim 21, wherein, as a representation of the likelihood density function of the Bayesian estimator, use is made e.g. 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.

32. The method according to claim 21, 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 such as e.g. hexagons, 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.

33. The method according to claim 32, wherein, if polygons are used, 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.

34. The method according to claim 21, wherein use is made of visual odometry methods known from robotics, such as e.g. the “

Lucas Kanade”

or “

Focus of Expansion”

methods, wherein, with the aid of optical sensors, use is made e.g. of the change of the appearance of the environment for estimating the change of location and position of the person.

35. The method according to claim 21, 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, and then, as a map, there are output e.g. all planes created in this manner.

36. The method according to claim 21, 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.

37. The method according to claim 21, 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 overlapping 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.

38. The method according to claim 21, 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.

39. The method according to claim 21, 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.

40. The method according to claim 21, wherein the created map represents three spatial dimensions (for example, for an application in three dimensions, use can be made of columnar geometric surfaces with polygon-like footprints and a flat or oblique bottom or roof, wherein, e.g., in analogy with the two-dimensional version of the polygon map, the transitions are counted and evaluated by the therein defined walls or bottom and roof surfaces, e.g. in that, in a two-dimensional map, transitions are observed via lines and, in a three-dimensional map, transitions are observed by surfaces).