Using constructed paths to supplement map data

• US 8,386,422 B1
• Filed: 07/08/2011
• Issued: 02/26/2013
• Est. Priority Date: 07/08/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadous, Mohammed Waleed, Lookingbill, Andrew, Thrun, Sebastian
• Primary Examiner(s): Le, Miranda
• Application Number:
  US13/178,941
• Time in Patent Office: 599 Days
• Field of Search: 707/609, 701/454, 455/456.1
• US Class Current: 707/609
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation

Abstract

Aspects of the present disclosure relate generally to indoor localization, for example, where GPS or other localization signals are unavailable. More specifically, aspects relate to using a particle filter in conjunction with one or more orientation devices to identify a location of a client device with respect to a map of an indoor space. This location may then be used to identify the path of the client device through the indoor space. The paths of a plurality of different client devices through the same indoor space may be used to update the map based on common patterns or inconsistencies between the map and the paths of the plurality of client devices.

Claims

1. A method of updating a map of an indoor space, the map being based on a plurality of features, the method comprising:

determining a plurality of paths of a portable handheld device through the indoor space, wherein determining each particular path of the plurality of paths includes;

generating, by a processor, a first set of particles, each particle of the first set of particles representing a location on the map and being associated with a likelihood value, and wherein each particle of the first set of particles further represents a device heading;

receiving data from one or more orientation devices;

determining a direction and speed of movement based on the received data;

identifying a heading based on the received data;

applying the direction and speed of movement to each one of the first set of particles;

adjusting the likelihood value of each particle of the first set of particles, based on whether the particular particle violated one or more of the plurality of features and whether the heading associated with each particular particle is associated with a heading consistent with the identified heading;

generating a second set of particles by selecting particles of the first set of particles based on the likelihood values associated with the first set of particles and adjusting the representative locations of the selected particles of the first set by a minimal value;

for each particular particle of the second set of particles, storing information identifying the particle of the first set selected to generate the particular particle of the second set;

if all of the particles of the second set of particles are within a threshold radius of one another, selecting a given particle of the second set of particles closest to an average representative location of the second set of particles; and

determining the particular path based on the stored information identifying the particle of the first set selected to generate the selected given particle of the second set;

storing the plurality of determined paths in memory;

comparing each path of the stored plurality of determined paths to the map to identify common patterns; and

updating the map by making one or more changes to the plurality of features based on the identified common patterns.

2. The method of claim 1, wherein the plurality of features are walls which define areas where a user may not pass through.

3. The method of claim 2, wherein the one or more changes include adding a wall to the map.

4. The method of claim 2, wherein the one or more changes include adjusting a wall.

5. The method of claim 2, wherein the one or more changes include adding a feature representing an object to the map.

6. The method of claim 1, wherein the plurality of features are rails which define areas where a user is permitted to go.

7. The method of claim 6, wherein the one or more changes include adding a rail to the map.

8. The method of claim 6, wherein the one or more changes include adjusting a rail.

9. The method of claim 1, wherein the first set of particles and the second set of particles each includes the same number of particles.

10. The method of claim 1, wherein each particle of the first set of particles further represents a possible heading of the portable handheld device, and the method further comprises, for each particular particle of the second set of particles, storing information identifying the representative heading of the particle of the first set selected to generate the particular particle.

11. The method of claim 1, further comprising for each particular particle of the second set of particles, storing information identifying the representative location of the particle of the first set selected to generate the particular particle of the second set.

12. A device for updating a map of an indoor space, the device comprising:

memory storing the map of the indoor space, the map being based on a plurality of features; and

a processor coupled to the memory, the processor being configured to;

determine a plurality of paths of a portable handheld device through the indoor space, by;

generating a first set of particles, each particle of the first set of particles representing a location on the map and being associated with a likelihood value, and wherein each particle of the first set of particles further represents a device heading;

receiving data from one or more orientation devices;

determining a direction and speed of movement based on the received data;

identifying a heading based on the received data;

applying the direction and speed of movement to each one of the first set of particles;

adjusting the likelihood value of each particle of the first set of particles, based on whether the particular particle violated one or more of the plurality of features and whether the heading associated with each particular particle is associated with a heading consistent with the identified heading;

generating a second set of particles by selecting particles of the first set of particles based on the likelihood values associated with the first set of particles and adjusting the representative locations of the selected particles of the first set by a minimal value;

for each particular particle of the second set of particles, storing, in the memory, information identifying the particle of the first set selected to generate the particular particle of the second set;

if all of the particles of the second set of particles are within a threshold radius of one another, selecting a given particle of the second set of particles closest to an average representative location of the second set of particles; and

determining the particular path based on the stored information identifying the particle of the first set selected to generate the selected given particle of the second set;

store the plurality of determined paths in memory;

compare each path of the stored plurality of determined paths to the map to identify common patterns; and

update the map by making one or more changes to the plurality of features based on the identified common patterns.

13. The device of claim 12, wherein the plurality of features are walls which define areas where a user may not pass through.

14. The device of claim 13, wherein the one or more changes include adding a feature representing an object to the map.

15. The device of claim 12, wherein the plurality of features are rails which define areas where a user is permitted to go.

16. The device of claim 15, wherein the one or more changes include adding a rail to the map.

17. The device of claim 15, wherein the one or more changes include adjusting a rail.

18. The device of claim 13, wherein the one or more changes include adding a wall to the map.

19. The device of claim 13, wherein the one or more changes include adjusting a wall.

20. The device of claim 12, wherein the first set of particles and the second set of particles each includes the same number of particles.

21. The device of claim 12, wherein each particle of the first set of particles further represents a possible heading of the portable handheld device, and the processor is further operable to, for each particular particle of the second set of particles, store, in the memory, information identifying the representative heading of the particle of the first set selected to generate the particular particle.

22. The device of claim 12, wherein the processor is further operable to, for each particular particle of the second set of particles, store, in the memory, information identifying the representative location of the particle of the first set selected to generate the particular particle of the second set.

23. A tangible, non-transitory, computer-readable storage medium on which computer readable instructions of a program are stored, the instructions, when executed by a processor, cause the processor to perform a method of updating a map of an indoor space the map being based on a plurality of features, the method comprising:

determining a plurality of paths of a portable handheld device through the indoor space, wherein determining each particular path of the plurality includes;

generating a first set of particles, each particle of the first set of particles representing a location on the map and being associated with a likelihood value, and wherein each particle of the first set of particles further represents a device heading;

receiving data from one or more orientation devices;

identifying a heading based on the received data;

determining a direction and speed of movement based on the received data;

applying the direction and speed of movement to each one of the first set of particles;

adjusting the likelihood value of each particle of the first set of particles, based on whether the particular particle violated one or more of the plurality of features and whether the heading associated with each particular particle is associated with a heading consistent with the identified heading;

generating a second set of particles by selecting particles of the first set of particles based on the likelihood values associated with the first set of particles and adjusting the representative locations of the selected particles of the first set by a minimal value;

for each particular particle of the second set of particles, storing information identifying the particle of the first set selected to generate the particular particle of the second set;

if all of the particles of the second set of particles are within a threshold radius of one another, selecting a given particle of the second set of particles closest to an average representative location of the second set of particles; and

determining the particular path based on the stored information identifying the particle of the first set selected to generate the selected given particle of the second set;

storing the plurality of determined paths in memory;

comparing each path of the stored plurality of determined paths to the map to identify common patterns; and

updating the map by making one or more changes to the plurality of features based on the identified common patterns.