Reducing location search space

• US 9,179,265 B2
• Filed: 01/31/2013
• Issued: 11/03/2015
• 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.
• Primary Examiner(s): WASHINGTON, ERIKA ALISE
• Application Number:
  US13/756,470
• Publication Number:
  US 20140213294A1
• Time in Patent Office: 1,006 Days
• Field of Search: None
• US Class Current: 1/1
• 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, wherein the indication includes one or more identifiers of one or more signal sources detected by the mobile device at the venue location;

providing, by the server, coarse location data to the mobile device based on the one or more identifiers, the coarse location data including one or more actual or estimated locations of the one or more signal sources;

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:

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.

7. The method of claim 6, 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.

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

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

10. The method of claim 9, 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.

11. A non-transitory 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, wherein the indication includes one or more identifiers of one or more signal sources detected by the mobile device at the venue location;

providing location data to the mobile device based on the one or more identifiers, the coarse location data including one or more actual or estimated locations of the one or more signal sources;

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.

12. The non-transitory storage device of claim 11, 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.

13. The non-transitory storage device of claim 11, 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.

14. The non-transitory storage device of claim 11, 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.

15. A non-transitory 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.

16. The non-transitory storage device of claim 15, 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.

17. A system, comprising:

a server comprising one or more processors; and

a non-transitory 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, wherein the indication includes one or more identifiers of one or more signal sources detected by the mobile device at the venue location;

providing, by the server, coarse location data to the mobile device based on the one or more identifiers, the coarse location data including one or more actual or estimated locations of the one or more signal sources;

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.

18. The system 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 system 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 system 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 mobile device, comprising:

one or more processors; and

a non-transitory storage device storing computer instructions operable to cause the one or more processors 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.

22. The mobile device of claim 21, 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.