Reducing Location Search Space

• US 20140213294A1
• Filed: 01/31/2013
• Published: 07/31/2014
• Est. Priority Date: 01/31/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Mayor, Robert, Ma, Shannon M.
• Granted Patent: US 9,179,265 B2
• Time in Patent Office: Days
• US Class Current: 455/456.2
• CPC Class Codes: G01S 5/0236 Assistance data, e.g. base station almanac
• CPC Class Codes: G01S 5/02521 using a radio-map
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Methods, program products, and systems for reducing a location search space are described. A mobile device, when arriving at a venue, can determine a location of the mobile device using signals from one or more signal sources associated with the venue. The mobile device can use a coarse location estimator to estimate a coarse location of the mobile device at the venue. The mobile device can request, from a server, detailed location data associated with the coarse location. The detailed location data can include location fingerprint data associated with a portion of the venue that includes the coarse location. The mobile device can determine an estimated location that has finer granularity than the coarse location using the location fingerprint data.

Claims

1. A method comprising:

receiving, by a server and from a mobile device, an indication that the mobile device is located at a venue and is requesting information for determining a venue location of the mobile device, the venue comprising a space accessible by a pedestrian and one or more constraints of movements of the pedestrian, the venue location being a location of the mobile device relative to the venue;

providing, by the server, coarse location data to the mobile device, the coarse location data including one or more estimated locations, each estimated location corresponding to a signal source a signal of which is estimated to be detectable by mobile devices at the venue;

receiving, by the server and from the mobile device, a coarse location, the coarse location being a location of the mobile device estimated by the mobile device using the coarse location data; and

providing, by the server and to the mobile device, location fingerprint data for determining the venue location, the location fingerprint data comprising a fingerprint for the coarse location, the fingerprint including a set of one or more measurements that the mobile device is expected to receive when the mobile device measures signals of the one or more signal sources at the coarse location,

wherein the server comprises one or more processors.

2. The method of claim 1, wherein each signal source includes at least one of a cellular transceiver, a wireless access point, a light source, a sound source, a magnetic field source, or a heat source.

3. The method of claim 1, wherein each measurement includes at least one of a received signal strength indication (RSSI), a round-trip time, a magnetic field strength, a temperature, a sound level, or an air pressure level.

4. The method of claim 1, wherein each estimated location is determined based on survey data using a probability density function, the survey data include data received by the server from a sampling device, the sampling device being a mobile device designated to measure signals from the signal sources from a plurality of sampling points at the venue.

5. The method of claim 1, wherein the location fingerprint data comprises a plurality of fingerprints, each fingerprint corresponding to a tile, each tile being an area of the venue, at least one first tile of the tiles being an area corresponding to the coarse location, and at least one second tile of the tiles being an area neighboring the first tile.

6. A method comprising:

obtaining, by a server and from a sampling device, a plurality of sampling points and a set of measurements, the sampling device being a mobile device designated to measure signals from one or more signal sources at a venue, the sampling points being points along a route traveled by the sampling device and being locations at which the sampling device measures the signals using one or more sensors or receivers, the venue comprising a space accessible by a pedestrian and one or more constraints of movements of the pedestrian, each measurement being associated with a location of a sampling point at which the sampling device measures the signals;

determining, by the server, estimated locations of the signal sources based on the measurements and associated sampling points using a probability density function;

determining, by the server, location fingerprint data of the venue, the location fingerprint data comprising expected measurements of signals from the one or more signal sources at sampling points and other locations at the venue;

receiving, from a requesting device, a request for coarse location data, the requesting device being a mobile device requesting information for determining a venue location, the venue location being a location of the requesting device relative to the venue;

providing, by the server and to the requesting device, the estimated locations of the signal sources for estimating a coarse location of the requesting device; and

providing, by the server and to the requesting device for determining the venue location, a portion of the fingerprint data that corresponds to the coarse location,

wherein the server comprises one or more computers.

7. The method of claim 6, wherein obtaining the sampling points and the set of measurements comprises at least one of:

receiving, by the server, the sampling points from the sampling device, the sampling points being locations at the venue designated by a surveyor on a venue map displayed on the sampling device using a user input, the user input triggering the sampling device to take the measurements, or

by the server;

receiving, from the sampling device, a plurality of survey timestamps, each survey timestamp being associated with a sampling point; and

determining, by the server, the sampling points, including determining a location of each sampling point along the route based on the survey timestamp associated with the sampling point, a beginning timestamp associated with a beginning of the route, a finishing timestamp associated with an ending of the route, and a length of the route.

8. The method of claim 6, wherein determining the estimated locations of the signal sources comprises:

determining a propagation characteristic of signals from each signal source based on a venue map, the venue map representing structures of the venue that attenuate the signals; and

determining one or more estimated locations for each signal source based on the measurements, the associated sampling locations, and the propagation characteristic, wherein each of the one or more estimated locations is associated with a probability that the corresponding estimated location of the signal source is located at the estimated location.

9. The method of claim 6, wherein the request for coarse location data includes an identifier of at least one of the one or more signal sources, each signal source comprising a radio frequency (RF) signal transmitter, the identifier comprises a media access control address of the corresponding RF signal transmitter.

10. The method of claim 6, wherein determining the location fingerprint data of the venue comprises:

determining the location fingerprint data using at least one of interpolation or extrapolation, wherein;

determining the location fingerprint data using interpolation comprises determining the expected measurements of signals by interpolating the sampling points and a set of measurements to determine expected measurements at the other locations at the venue, and

determining the location fingerprint data using extrapolation comprises determining the expected measurements of signals based on known relative locations of the one or more signal sources and signal propagation characteristics of structures of the venue.

11. The method of claim 6, wherein providing the portion of the fingerprint data comprises:

determining a portion of the venue that includes the coarse location; and

providing a portion of the fingerprint data associated with the portion of the venue to the mobile device.

12. A method, comprising:

submitting, by a mobile device and to a server, a request for coarse location data, the request for coarse location data comprising an identifier of each of one or more signal sources detected by the mobile device;

receiving, by the mobile device and from the server, coarse location data, the coarse location data comprising an estimated location of each signal source;

determining, by the mobile device, a coarse location of the mobile device based on a measurement of signals from the one or more signal sources and a function of a signal source uncertainty and the measurement;

submitting, by the mobile device and to the server, a request for location fingerprint data, the request for location fingerprint data identifying the coarse location;

receiving, by the mobile device and from the server, the location fingerprint data associated with at least of a portion of a venue that includes the coarse location, the location fingerprint data comprising expected measurements of signal of each signal source; and

determining, by the mobile device, an estimated location of the mobile device based on statistical classification of a measurement of the signals from each signal source using the location fingerprint data.

13. The method of claim 12, wherein:

the estimated location of each signal source is determined based on a multi-modal probability function applied to survey data, the survey data being provided by a sampling device measuring signals from the signal source at the venue.

14. The method of claim 12, wherein the location fingerprint data comprises training data generated based on one or more previously conducted surveys of the venue.

15. The method of claim 12, wherein the function comprises a weighted average of measurements of signals from the one or more signal sources.

16. The method of claim 15, wherein:

each of the one or more signal sources is a radio frequency signal transmitter, and

the measurements include signal strengths or round trip time.

17. A storage device storing computer instructions operable to cause a server to perform operations comprising:

receiving, from a mobile device, an indication that the mobile device is located at a venue and is requesting information for determining a venue location of the mobile device, the venue comprising a space accessible by a pedestrian and one or more constraints of movements of the pedestrian, the venue location being a location of the mobile device relative to the venue;

providing coarse location data to the mobile device, the coarse location data including one or more estimated locations, each estimated location corresponding to a signal source a signal of which is estimated to be detectable by mobile devices at the venue;

receiving, from the mobile device, a coarse location, the coarse location being a location of the mobile device estimated by the mobile device using the coarse location data; and

providing, to the mobile device, location fingerprint data for determining the venue location, the location fingerprint data comprising a fingerprint for the coarse location, the fingerprint including a set of one or more measurements that the mobile device is expected to receive when the mobile device measures signals of the one or more signal sources at the coarse location,

wherein the server comprises one or more processors.

18. The storage device of claim 17, wherein:

each signal source includes at least one of a cellular transceiver, a wireless access point, a light source, a sound source, a magnetic field source, or a heat source; and

each measurement includes at least one of a received signal strength indication (RSSI), a round-trip time, a magnetic field strength, a temperature, a sound level, or an air pressure level.

19. The storage device of claim 17, wherein each estimated location is determined based on survey data using a probability density function, the survey data include data received by the server from a sampling device, the sampling device being a mobile device designated to measure signals from the signal sources from a plurality of sampling points at the venue.

20. The storage device of claim 17, wherein the location fingerprint data comprises a plurality of fingerprints, each fingerprint corresponding to a tile, each tile being an area of the venue, at least one first tile of the tiles being an area corresponding to the coarse location, and at least one second tile of the tiles being an area neighboring the first tile.

21. A storage device storing computer instructions operable to cause a server to perform operations comprising:

obtaining from a sampling device, a plurality of sampling points and a set of measurements, the sampling device being a mobile device designated to measure signals from one or more signal sources at a venue, the sampling points being points along a route traveled by the sampling device and being locations at which the sampling device measures the signals using one or more sensors or receivers, the venue comprising a space accessible by a pedestrian and one or more constraints of movements of the pedestrian, each measurement being associated with a location of a sampling point at which the sampling device measures the signals;

determining estimated locations of the signal sources based on the measurements and associated sampling points using a probability density function;

determining location fingerprint data of the venue, the location fingerprint data comprising expected measurements of signals from the one or more signal sources at sampling points and other locations at the venue;

receiving, from a requesting device, a request for coarse location data, the requesting device being a mobile device requesting information for determining a venue location, the venue location being a location of the requesting device relative to the venue;

providing, to the requesting device, the estimated locations of the signal sources for estimating a coarse location of the requesting device; and

providing to the requesting device for determining the venue location, a portion of the fingerprint data that corresponds to the coarse location,

wherein the server comprises one or more computers.

22. The storage device of claim 21, wherein obtaining the sampling points and the set of measurements comprises at least one of:

receiving, by the server, the sampling points from the sampling device, the sampling points being locations at the venue designated by a surveyor on a venue map displayed on the sampling device using a user input, the user input triggering the sampling device to take the measurements, or

by the server;

receiving, from the sampling device, a plurality of survey timestamps, each survey timestamp being associated with a sampling point; and

determining, by the server, the sampling points, including determining a location of each sampling point along the route based on the survey timestamp associated with the sampling point, a beginning timestamp associated with a beginning of the route, a finishing timestamp associated with an ending of the route, and a length of the route.

23. The storage device of claim 21, wherein determining the location fingerprint data of the venue comprises:

determining the location fingerprint data using at least one of interpolation or extrapolation, wherein;

determining the location fingerprint data using interpolation comprises determining the expected measurements of signals by interpolating the sampling points and a set of measurements to determine expected measurements at the other locations at the venue, and

determining the location fingerprint data using extrapolation comprises determining the expected measurements of signals based on known relative locations of the one or more signal sources and signal propagation characteristics of structures of the venue.

24. The storage device of claim 21, wherein providing the portion of the fingerprint data comprises:

determining a portion of the venue that includes the coarse location; and

providing a portion of the fingerprint data associated with the portion of the venue to the mobile device.

25. A storage device storing computer instructions operable to cause a mobile device to perform operations comprising:

submitting, by the mobile device and to a server, a request for coarse location data, the request for coarse location data comprising an identifier of each of one or more signal sources detected by the mobile device;

receiving, by the mobile device and from the server, coarse location data, the coarse location data comprising an estimated location of each signal source;

determining, by the mobile device, a coarse location of the mobile device based on a measurement of signals from the one or more signal sources and a function of a signal source uncertainty and the measurement;

submitting, by the mobile device and to the server, a request for location fingerprint data, the request for location fingerprint data identifying the coarse location;

receiving, by the mobile device and from the server, the location fingerprint data associated with at least of a portion of a venue that includes the coarse location, the location fingerprint data comprising expected measurements of signal of each signal source; and

determining, by the mobile device, an estimated location of the mobile device based on statistical classification of a measurement of the signals from each signal source using the location fingerprint data.

26. The storage device of claim 25, wherein:

the estimated location of each signal source is determined based on a multi-modal probability function applied to survey data, the survey data being provided by a sampling device measuring signals from the signal source at the venue.

27. A system, comprising:

a server comprising one or more processors; and

a storage device storing computer instructions operable to cause the server to perform operations comprising;

receiving, from a mobile device, an indication that the mobile device is located at a venue and is requesting information for determining a venue location of the mobile device, the venue comprising a space accessible by a pedestrian and one or more constraints of movements of the pedestrian, the venue location being a location of the mobile device relative to the venue;

providing coarse location data to the mobile device, the coarse location data including one or more estimated locations, each estimated location corresponding to a signal source a signal of which is estimated to be detectable by mobile devices at the venue;

receiving, from the mobile device, a coarse location, the coarse location being a location of the mobile device estimated by the mobile device using the coarse location data; and

providing, to the mobile device, location fingerprint data for determining the venue location, the location fingerprint data comprising a fingerprint for the coarse location, the fingerprint including a set of one or more measurements that the mobile device is expected to receive when the mobile device measures signals of the one or more signal sources at the coarse location.

28. The system of claim 27, wherein:

each signal source includes at least one of a cellular transceiver, a wireless access point, a light source, a sound source, a magnetic field source, or a heat source; and

each measurement includes at least one of a received signal strength indication (RSSI), a round-trip time, a magnetic field strength, a temperature, a sound level, or an air pressure level.

29. The system of claim 27, wherein each estimated location is determined based on survey data using a probability density function, the survey data include data received by the server from a sampling device, the sampling device being a mobile device designated to measure signals from the signal sources from a plurality of sampling points at the venue.

30. The system of claim 27, wherein the location fingerprint data comprises a plurality of fingerprints, each fingerprint corresponding to a tile, each tile being an area of the venue, at least one first tile of the tiles being an area corresponding to the coarse location, and at least one second tile of the tiles being an area neighboring the first tile.

31. A system, comprising:

a server comprising one or more processors; and

a storage device storing computer instructions operable to cause the server to perform operations comprising;

obtaining from a sampling device, a plurality of sampling points and a set of measurements, the sampling device being a mobile device designated to measure signals from one or more signal sources at a venue, the sampling points being points along a route traveled by the sampling device and being locations at which the sampling device measures the signals using one or more sensors or receivers, the venue comprising a space accessible by a pedestrian and one or more constraints of movements of the pedestrian, each measurement being associated with a location of a sampling point at which the sampling device measures the signals;

determining estimated locations of the signal sources based on the measurements and associated sampling points using a probability density function;

determining location fingerprint data of the venue, the location fingerprint data comprising expected measurements of signals from the one or more signal sources at sampling points and other locations at the venue;

receiving, from a requesting device, a request for coarse location data, the requesting device being a mobile device requesting information for determining a venue location, the venue location being a location of the requesting device relative to the venue;

providing, to the requesting device, the estimated locations of the signal sources for estimating a coarse location of the requesting device; and

providing to the requesting device for determining the venue location, a portion of the fingerprint data that corresponds to the coarse location.

32. The system of claim 31, wherein obtaining the sampling points and the set of measurements comprises at least one of:

receiving, by the server, the sampling points from the sampling device, the sampling points being locations at the venue designated by a surveyor on a venue map displayed on the sampling device using a user input, the user input triggering the sampling device to take the measurements, or

by the server;

receiving, from the sampling device, a plurality of survey timestamps, each survey timestamp being associated with a sampling point; and

determining, by the server, the sampling points, including determining a location of each sampling point along the route based on the survey timestamp associated with the sampling point, a beginning timestamp associated with a beginning of the route, a finishing timestamp associated with an ending of the route, and a length of the route.

33. The system of claim 31, wherein determining the location fingerprint data of the venue comprises:

determining the location fingerprint data using at least one of interpolation or extrapolation, wherein;

determining the location fingerprint data using interpolation comprises determining the expected measurements of signals by interpolating the sampling points and a set of measurements to determine expected measurements at the other locations at the venue, and

determining the location fingerprint data using extrapolation comprises determining the expected measurements of signals based on known relative locations of the one or more signal sources and signal propagation characteristics of structures of the venue.

34. The system of claim 31, wherein providing the portion of the fingerprint data comprises:

determining a portion of the venue that includes the coarse location; and

providing a portion of the fingerprint data associated with the portion of the venue to the mobile device.

35. A system, comprising:

a mobile device comprising one or more processors; and

a storage device storing computer instructions operable to cause the mobile device to perform operations comprising;

submitting, to a server, a request for coarse location data, the request for coarse location data comprising an identifier of each of one or more signal sources detected by the mobile device;

receiving, from the server, coarse location data, the coarse location data comprising an estimated location of each signal source;

determining, a coarse location of the mobile device based on a measurement of signals from the one or more signal sources and a function of a signal source uncertainty and the measurement;

submitting, to the server, a request for location fingerprint data, the request for location fingerprint data identifying the coarse location;

receiving, from the server, the location fingerprint data associated with at least of a portion of a venue that includes the coarse location, the location fingerprint data comprising expected measurements of signal of each signal source; and

determining, an estimated location of the mobile device based on statistical classification of a measurement of the signals from each signal source using the location fingerprint data.

36. The system of claim 35, wherein:

the estimated location of each signal source is determined based on a multi-modal probability function applied to survey data, the survey data being provided by a sampling device measuring signals from the signal source at the venue.