METHOD FOR LOCALISATION AND MAPPING OF PEDESTRIANS OR ROBOTS USING WIRELESS ACCESS POINTS

• US 20150031390A1
• Filed: 09/17/2012
• Published: 01/29/2015
• Est. Priority Date: 09/16/2011
• Status: Abandoned Application

• 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, Bruno, Luigi
• Application Number:
  US14/345,284
• Publication Number:
  US 20150031390A1
• Time in Patent Office: Days
• US Class Current: 455/456.1
• CPC Class Codes: G01C 21/165 combined with non-inertial navigation instruments
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 5/0242 Determining the position of transmitters to be subsequently used in positioning G01S5/0289 takes precedence
• CPC Class Codes: G01S 5/02585 at least one of the measurements being a non-radio measurement
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G05D 1/027 comprising intertial navigation means, e.g. azimuth detector inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0285 using signals transmitted via a public communication network, e.g. GSM network
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

The method for localisation and mapping of pedestrians or robots using Wireless Access Points comprises the following steps: Wireless Signal Strength and/or time delay measurements from wireless access points (e.g. Wireless Local Area Network access points (WLAN, Wifi, WIMAX), or mobile radio base stations (e.g. GSM, UMTS, LTE, 4G, IS95 or RFID tags or transmitters) are taken at regular or irregular time instances by a device carried by the pedestrian or robot in addition to odometry measurements (e.g. human step measurements, human pedestrian dead-reckoning, robot or wheelchair wheel counter measurements, robot motor or wheelchair motor control inputs), and providing a particle filter which has a state model that comprises the pedestrian or robot location history for each particle, and also the location probability distribution of one or more wireless access points, wherein at each time-step of the particle filter each particle of the particle filter is weighted and/or propagated according to the odometry measurements and weighted and/or propagated according to the wireless measurement, wherein at each time-step of the particle filter the location probability distribution of the wireless access points for each particle is updated according to the measurement and the previous location probability distribution of that particle, and wherein the location of the pedestrian or robot and/or the map of the wireless access point(s) is extracted from the particle population (e.g. from the state of the particle with greatest weight, from the weighted state across all particles, from the state of a randomly chosen particle, from the state of the maximum likelihood particle).

Claims

1. A method for localisation and mapping of pedestrians or robots using Wireless Access Points comprising the following steps:

received Wireless Signal Strength (RSS) measurements and/or time delay measurements from wireless access points (AP) (e.g. Wireless Local Area Network access points (WLAN, Wifi, WIMAX), or mobile radio base stations (e.g. GSM, UMTS, LTE, 4G, IS95) or RFID tags or transmitters) are taken at regular or irregular time instances by a device carried by the pedestrian or robot

providing odometry measurements (e.g. human step measurements, human pedestrian dead-reckoning, robot or wheelchair wheel counter measurements, robot motor or wheelchair motor control inputs) from an odometry system to be carried/worn/attached to/by the pedestrian or robot, and

providing a particle filter which has a state model that comprises the pedestrian or robot location history for each particle, and also the location probability distribution of one or more wireless access points, wherein at each time-step of the particle filter each particle of the particle filter is weighted and/or propagated according to the odometry measurements and weighted and/or propagated according to the wireless measurement,

wherein at each time-step of the particle filter the location probability distribution of the wireless access points for each particle is updated according to the measurement and the previous location probability distribution of that particle, and

wherein the location of the pedestrian or robot and/or the map of the wireless access point(s) is extracted from the particle population (e.g. by reading the location and/or map from the state of the particle with greatest weight, or by reading the location and/or map from the weighted state across all particles, or by reading the location and/or map from the state of a randomly chosen particle, or by reading the location and/or map from the state of the maximum likelihood particle).

2. The method according to claim 1, further comprising the step of preprocessing of the RSS and/or time delay measurements to determine which APs should be processed, for example by assigning a threshold of signals strength or time-of-arrival or time-difference-of-arrival which is used to determine that an AP is suitably close to be useful and located on the same floor level.

3. The method according to claim 1, further comprising the step of preprocessing of the RSS and/or time delay measurements to exclude outliers of the measurements (e.g. using well known outlier detection algorithms to remove data).

4. The method according to claim 1, further comprising the step of preprocessing of the RSS and/or time delay measurements to filter the measurements (e.g. low-pass filtering or down- or up-sampling).

5. The method according to claim 1, further comprising the step of preprocessing of the RSS and/or time delay measurements to determine which time instances of the signal from an AP should be processed (i.e. pruning the signal).

6. The method according to claim 1, wherein measurements from more than one walk (from the same user of different users) in the same area are combined.

7. The method according to claim 1, wherein the state space is extended to three dimensions by including the height of the user in the user position and the height of the AP in the map by using either a full 3D representation or a discrete third (height) dimension (called 2½

D).

8. The method according to claim 1, wherein during usage of the map or during a second or further SLAM stage it is detected whether APs have moved wherein moved APs are determined by observing the weight contributions of particles from a respective AP allowing detection of a mismatch between the previous estimated map and new measurements for that AP.

9. The method according to claim 1, wherein the location probability distribution of an AP is represented in two different forms, depending on the number of measurements available for that AP, whereby in the initialization phase (i.e. during the first measurements) the representation is by storing a number of functions (e.g. circular, donut shaped) that each represent the probability distribution of the AP location at each measurement for a particular particle, whereas after the initialization phase the representation is by using a one or more peaks (e.g. a mixture of Normal distributions).

10. The method according to claim 1, wherein in addition to the state model of the particle filter comprising the location probability distribution of one or more wireless access points the state model of the particle filter also comprises the probability distribution of the power emitted by each AP.

11. The method according to claim 10, wherein the probability distribution of the power emitted by each AP is represented by a discrete probability distribution and for each range value of this discrete distribution the state model of the particle filter comprises an individual probability distribution of the AP location.