Reducing location search space

• US 9,560,489 B2
• Filed: 09/29/2015
• Issued: 01/31/2017
• 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:
  US14/868,677
• Publication Number:
  US 20160021513A1
• Time in Patent Office: 490 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:

obtaining, by a server from a sampling device, sets of measurements captured at sampling locations along a route traveled by the sampling device at a venue;

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 locations including the sampling locations;

receiving, by the server from a requesting device that is different from the sampling device, a first request for first location data;

providing, by the server to the requesting device as a response to the first request, the estimated locations of the one or more signal sources;

receiving, by the server from the requesting device, a second request for second location data, the second request including an estimated first location of the requesting device at the venue; and

providing, by the server to the requesting device as a response to the second request, a portion of the fingerprint data that corresponds to the estimated first location,

wherein the server comprises one or more computers.

2. The method of claim 1, wherein obtaining the sets of measurements comprises at least one of:

receiving, by the server, the sampling locations from the sampling device, the sampling locations 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 location; and

determining, by the server, the sampling locations, including determining each sampling location along the route based on the survey timestamp associated with the sampling location, 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.

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

4. The method of claim 1, wherein the first request for first 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.

5. The method of claim 1, 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 locations and sets of measurements to determine expected measurements at 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.

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

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

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

7. A non-transitory storage device storing computer instructions operable to cause a server to perform operations comprising:

obtaining, from a sampling device, sets of measurements captured at sampling locations along a route traveled by the sampling device at a venue;

determining estimated locations of one or more signal sources based on the measurements and associated sampling locations using a statistical 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 locations including the sampling locations;

receiving, from a requesting device that is different from the sampling, a first request for first location data;

providing, to the requesting device as a response to the first request, the estimated locations of the one or more signal sources;

receiving, by the server from the requesting device, a second request for second location data, the second request including an estimated first location of the requesting device at the venue; and

providing to the requesting device as a response to the second request, a portion of the fingerprint data that corresponds to the estimated first location,

wherein the server comprises one or more computers.

8. The non-transitory storage device of claim 7, wherein obtaining the sets of measurements comprises at least one of:

receiving, by the server, the sampling locations from the sampling device, the sampling locations 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 location; and

determining, by the server, the sampling locations, including determining each sampling location along the route based on the survey timestamp associated with the sampling location, 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.

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

10. The non-transitory storage device of claim 7, wherein the first request for first 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.

11. The non-transitory storage device of claim 7, 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 locations and sets of measurements to determine expected measurements at 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.

12. The non-transitory storage device of claim 7, wherein providing the portion of the fingerprint data comprises:

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

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

13. 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;

obtaining from a sampling device, sets of measurements captured at sampling locations along a route traveled by the sampling device at a venue;

determining estimated locations of one or more signal sources based on the measurements and associated sampling locations using a statistical 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 locations including the sampling locations;

receiving, from a requesting device that is different from the sampling device, a first request for first location data;

providing, to the requesting device as a response to the first request, the estimated locations of the one or more signal sources;

receiving, by the server from the requesting device, a second request for second location data, the second request including an estimated first location of the requesting device at the venue; and

providing to the requesting device as a response to the second request, a portion of the fingerprint data that corresponds to the estimated first location.

14. The system of claim 13, wherein obtaining sets of measurements comprises at least one of:

receiving, by the server, the sampling locations from the sampling device, the sampling locations 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 location; and

determining, by the server, the sampling locations, including determining each sampling location along the route based on the survey timestamp associated with the sampling location, 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.

15. The system of claim 13, 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.

16. The system of claim 13, wherein the first request for first 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.

17. The system of claim 13, 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 locations and sets of measurements to determine expected measurements at 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.

18. The system of claim 13 wherein providing the portion of the fingerprint data comprises:

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

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

19. 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 that is different from the sampling 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.

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

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

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

23. The method of claim 19, 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 method of claim 19, 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 non-transitory 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 that is different from the sampling 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.

26. 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;

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 that is different from the requesting, 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.