Automatically constructing paths

• US 8,412,183 B1
• Filed: 05/16/2011
• Issued: 04/02/2013
• Est. Priority Date: 05/16/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadous, Mohammed Waleed, Lookingbill, Andrew, Ettinger, Scott
• Primary Examiner(s): Tran, Tuan A
• Application Number:
  US13/108,127
• Time in Patent Office: 687 Days
• Field of Search: 455423-425, 4554141-4144, 4554561-4566, 455/457, 455/446, 455/448, 455/67.11, 455/67.13, 455 411- 412, 709220-224
• US Class Current: 455/425
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation

Abstract

Aspects of the present disclosure relate generally to generating reliable data for indoor navigation. More specifically, aspects relate to identifying a route for a person to follow in order to record data such wireless network access location or other beacon signal information and signal strengths for an indoor space. In one example, the pre-defined route may be generated based on a map of the indoor space, a set of predefined walking strategies, an average walking speed, a time limit, and an optimization goal. For example, if a person is able walk at some average speed for a set period of time, a route may be identified which provides a given density of data points (the optimization goal) within the indoor space. The collected data may then used to build a wireless network model of the indoor space for navigation.

Claims

1. A method for generating routes for collecting data points in an indoor space, the method comprising:

identifying a map of the indoor space;

identifying an optimization goal for collecting data points in the indoor space;

accessing a plurality of templates including strategies for walking through indoor spaces;

selecting, by a processor, a set of templates from the plurality of templates based on the map and the optimization goal; and

generating a route for collecting data points in the indoor space based on the selected set of templates.

2. The method of claim 1, further comprising:

receiving, from a client device, information identifying the indoor space;

wherein identifying the map is based on the received information identifying the indoor space.

3. The method of claim 2, wherein identifying the time parameter includes receiving, from a client device, a time parameter of a user.

4. The method of claim 1, further comprising identifying a time parameter and wherein selecting the set of templates is further based on the identified time parameter.

5. The method of claim 1, further comprising identifying a walking speed and wherein selecting the set of templates is further based on the identified walking speed.

6. The method of claim 5, wherein identifying the walking speed includes receiving, from a client device, a walking speed of a user.

7. The method of claim 1, wherein the optimization goal includes a specific density of data points in the indoor space.

8. The method of claim 1, wherein the map of the indoor space includes a plurality of hallways, the strategies for walking through the indoor spaces include strategies for walking through hallways, and the subset of templates are selected based on the plurality of hallways and the strategies for walking through hallways.

9. The method of claim 1, wherein the map of the indoor space includes a plurality of rooms, the strategies for walking through the indoor spaces include strategies for walking through rooms, and the subset of templates are selected based on the plurality of rooms and the strategies for walking through rooms.

10. A method of collecting data points along a route through an indoor space, the method comprising:

transmitting, to a server, a request for the route, the request including information identifying the indoor space;

receiving a route based on the indoor space and an optimization goal;

displaying, by a processor, the route on a display of a client device;

collecting data points along the route, each data point including wireless network access location identifiers and associated signal strengths; and

transmitting the collected data points to the server.

11. The method of claim 10, wherein the request further includes a time parameter and the route is based on the time parameter.

12. The method of claim 10, wherein the request further includes a walking speed and the route is based on the walking speed.

13. The method of claim 12, further comprising receiving, by the client device, input from a user identifying the walking speed.

14. A device for generating routes for collecting data points in an indoor space, the device comprising:

memory storing a plurality of templates including strategies for walking through indoor spaces; and

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

identify a map of the indoor space;

identify an optimization goal for collecting data points in the indoor space;

select a set of templates from the stored plurality of templates based on the map and the optimization goal; and

generate a route for collecting data points in the indoor space based on the selected set of templates.

15. The device of claim 14, wherein the processor is further operable to identify a time parameter and the processor selects the set of templates based on the time parameter.

16. The device of claim 14, wherein the processor is further operable to identify a walking speed and the processor selects the set of templates based on the walking speed.

17. The device of claim 14, wherein the processor is further operable to receive, from a client device, a walking speed of a user the processor selects the set of templates based on the received walking speed.

18. A device for collecting data points along a route through an indoor space, the device comprising:

a display; and

a processor coupled to the display, the processor being operable to;

transmit to a server, a request for the route, the request including information identifying the indoor space;

receive a route based on the indoor space, a time parameter, a walking speed, and an optimization goal;

display the route on the display;

collect data points along the route, each data point including wireless network access location identifiers and associated signal strengths; and

transmit the collected data points to the server.

19. The device of claim 18, wherein the processor is further operable to receive input identifying the time parameter from a user and to transmit the time parameter to the server.

20. The device of claim 18, wherein the processor is further operable to receive input identifying the walking speed from a user and to transmit the walking speed to the server.