Crowd-sourced information for interior localization and navigation

• US 8,320,939 B1
• Filed: 04/21/2011
• Issued: 11/27/2012
• Est. Priority Date: 04/21/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Vincent, Luc
• Primary Examiner(s): DOAN, PHUOC HUU
• Application Number:
  US13/091,504
• Time in Patent Office: 586 Days
• Field of Search: 455/456.1, 455/415, 455/440, 455/404.2, 709/224, 340/572.1, 370/338
• US Class Current: 455/456.1
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01S 19/48 by combining or switching between position solutions derived from the satellite radio beacon positioning system and position solutions derived from a further system
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: G01S 5/013 Identifying areas in a building
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings

Abstract

Aspects of the disclosure relate generally to using crowd sourced information to generate walkable paths through indoor spaces. More specifically, aspects relate to recording data such as accelerometer readings, wireless network or other beacon signal information, and timestamps while a client device moves within an indoor space. If the user reaches a destination within the indoor space, the client device may prompt the user for information about the destination. The information received and recorded by the client device may be sent to a server computer for further processing. The server may use the information to identify walkable paths within the indoor space. This information in turn may be used in various ways, such as to provide navigation assistance to users though the indoor space.

Claims

1. A method comprising:

determining, by a processor, that a GPS signal is insufficient to accurately determine position based on a characteristic of the GPS signal;

identifying an entrance location of a building based on a GPS coordinate identified before determining that the GPS signal is insufficient;

after the GPS signal is determined to be insufficient, recording a set of route data including a timestamp, accelerometer data, and a wireless network signal fingerprint comprising one or more wireless network signal beacon identifiers and associated signal strengths;

identifying an exit location of the building based on a GPS coordinate determined after the processor is able to accurately determine position based on GPS signals;

storing the entrance location, the exit location, and the route data in memory accessible by the client device;

generating, by the processor, a track including a set of location coordinates based on the route data, the entrance location, and the exit location; and

transmitting the track to a server.

2. The method of claim 1, further comprising:

determining when the client device has stopped moving based on the accelerometer data;

when the client device has stopped, presenting to a user a request for information regarding a current location of the client device;

receiving information identifying the current location of the client device; and

storing the received information as a destination.

3. The method of claim 2, further comprising:

identifying location coordinates associated with the destination based on the entrance location, exit location, and route data; and

transmitting the location coordinates associated with the destination and the destination to the server.

4. The method of claim 1, further comprising:

identifying a particular building associated with the entrance location and the exit location based on a map of building footprint data;

associating the particular building with the route; and

transmitting the particular building associated with the route to the server.

5. The method of claim 1, wherein the signal beacon identifiers include wireless network access point identifiers.

6. A method comprising:

identifying a plurality of tracks, each track including (a) an entrance location of a particular building based on a last set of GPS signals determined by a given client device before the given client device determines that a GPS signal is insufficient to accurately determine position based on a characteristic of the GPS signal, (b) a set of intermediate locations, each intermediate location being associated with an estimated geolocation coordinate a wireless network signal fingerprint comprising wireless network signal beacon identifiers and associated signal strengths, the set of intermediate locations being recorded after the GPS signal has been determined to be insufficient, (c) destination data including information about the destination received from a user, a destination wireless network signal fingerprint, and an estimated geolocation coordinate for the destination, and (d) an exit location of the particular building determined based on GPS signals received by the client device after the client device is able to accurately determine position based on the received GPS signals;

selecting a subset of the plurality of tracks having a common entrance location and a common estimated geolocation coordinate for a particular destination associated with an interior of the particular building;

refining the subset of tracks based on the wireless network signal fingerprints associated with the set of intermediate locations associated with each track of the subset of tracks; and

identifying one or more walkable paths through the particular building based on the refined subset of tracks.

7. The method of claim 6, further comprising:

receiving, from a particular client device, a request for directions to the particular destination;

generating a set of instructions for navigating to the destination based on the identified one or more walkable paths; and

transmitting the set of instructions to the particular client device.

8. The method of claim 6, wherein the refining is based on clustering the tracks of the subset of tracks.

9. The method of claim 6, further comprising receiving the plurality of tracks from a plurality of client devices.

10. The method of claim 6, further comprising:

receiving, from a plurality of client devices, a received plurality of routes including (a) an entrance location of the particular building based on the last GPS signals determined by a given one of the plurality of client device before the given client device determines that a GPS signal is insufficient to accurately determine position based on a characteristic of the GPS signal, (b) a received set of intermediate locations, each intermediate location being associated with accelerometer data, a wireless networksignal fingerprint, and a time stamp, (c) received destination data including the information about the destination received from a user, a destination wireless networksignal fingerprint, and a timestamp, and (d) an exit location of the particular building determined based on GPS signals received by the given client device after the given client device is able to accurately determine position based on the received GPS signals; and

generating, by the processor, the estimated geolocation coordinates for each of the intermediate locations and the estimated geolocation coordinate for the destination, based on the received plurality of routes; and

wherein the plurality of tracks are identified based on the received plurality of routes, the estimated geolocation coordinates for each of the intermediate locations and the estimated geolocation coordinate for the destination.

11. The method of claim 6, further comprising:

selecting a particular walkable path of the one or more identified walkable paths based on the number of the subset of tracks which correspond to the particular walkable path;

storing the particular walkable path;

receiving, from a particular client device, a request for directions to the particular destination;

generating a set of instructions for navigating to the destination based on the particular walkable paths; and

transmitting the set of instructions to the particular client device.

12. The method of claim 6, wherein the signal beacon identifiers include wireless network access point identifiers.

13. A device comprising:

memory;

a processor to;

determine that a GPS signal is insufficient to accurately determine position based on a characteristic of the GPS signal;

identify an entrance location of a building based on a GPS coordinate identified before determining that the GPS signal is insufficient;

after the GPS signal is determined to be insufficient, record a set of route data including a timestamp, accelerometer data, and a wireless network signal fingerprint comprising one or more wireless network signal beacon identifiers and associated signal strengths;

identify an exit location of the building based on a GPS coordinate determined after the processor is able to accurately determine position based on GPS signals;

store the entrance location, the exit location, and the route data in the memory;

generate a track including a set of location coordinates based on the route data, the entrance location, and the exit location; and

transmit the track to a server.

14. The device of claim 13, wherein the processor further:

determines when the client device has stopped moving based on the accelerometer data;

when the client device has stopped, presents to a user a request for information regarding a current location of the client device;

receives information identifying the current location of the client device; and

stores the received information as a destination.

15. The device of claim 14, wherein the processor further:

identifies location coordinates associated with the destination based on the entrance location, exit location, and route data; and

transmits the location coordinates associated with the destination and the destination to the server.

16. The device of claim 13, wherein the processor further:

identifies a particular building associated with the entrance location and the exit location based on a map of building footprint data;

associates the particular building with the route; and

transmits the particular building associated with the route to the server.

17. The device of claim 16, wherein the processor also:

receives, from a particular client device, a request for directions to the particular destination;

generates a set of instructions for navigating to the destination based on the identified one or more walkable paths; and

transmits the set of instructions to the particular client device.

18. The device of claim 16, wherein the processor refines by clustering the tracks of the subset of tracks.

19. The device of claim 16, wherein the processor further receives the plurality of tracks from a plurality of client devices.

20. The device of claim 16, wherein the processor further:

selects a particular walkable path of the one or more identified walkable paths based on the number of the subset of tracks which correspond to the particular walkable path;

stores the particular walkable path in the memory;

receives, from a particular client device, a request for directions to the particular destination;

generates a set of instructions for navigating to the destination based on the particular walkable paths; and

transmits the set of instructions to the particular client device.

21. A device comprising:

memory; and

a processor to;

identify a plurality of tracks, each track including (a) an entrance location of a particular building based on a last set of GPS signals determined by a given client device before the given client device determines that a GPS signal is insufficient to accurately determine position based on a characteristic of the GPS signal, (b) a set of intermediate locations, each intermediate location being associated with an estimated geolocation coordinate a wireless network signal fingerprint comprising wireless network signal beacon identifiers and associated signal strengths, the set of intermediate locations being recorded after the GPS signal has been determined to be insufficient, (c) destination data including information about the destination received from a user, a destination wireless network signal fingerprint, and an estimated geolocation coordinate for the destination, and (d) an exit location of the particular building determined based on GPS signals received by the client device after the client device is able to accurately determine position based on the received GPS signals;

select a subset of the plurality of tracks having a common entrance location and a common estimated geolocation coordinate for a particular destination associated with an interior of the particular building;

refine the subset of tracks based on the wireless network signal fingerprints associated with the set of intermediate locations associated with each track of the subset of tracks;

identify one or more walkable paths through the particular building based on the refined subset of tracks; and

store the one or more walkable paths in the memory.