System and method for improving route finding

• US 9,194,712 B2
• Filed: 06/23/2011
• Issued: 11/24/2015
• Est. Priority Date: 06/23/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Siliski, Michael, Hughes, Joseph
• Primary Examiner(s): Cheung, Calvin
• Assistant Examiner(s): WEEKS, MARTIN A
• Application Number:
  US13/167,008
• Publication Number:
  US 20150168160A1
• Time in Patent Office: 1,615 Days
• Field of Search: 701201-213, 701410-411, 3409951-99512
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance

Abstract

A method and system for improving route finding are described. Aspects of the disclosure determine a bearing for a client device using a compass. The determined bearing is used to optimize route finding operations performed by the client device. The bearing may be mapped to a road graph and used in conjunction with a location of the client device to determine an efficient route to a destination. For example, aspects of the method and system may identify a nearest turn in the direction the client device is traveling without the need to obtain multiple location readings to identify a direction of travel.

Claims

1. A computer-implemented method for improving route finding, the method comprising:

receiving, by one or more computing devices, a request for walking directions, for directing a user to a destination;

identifying, in response to the received request, a bearing of a client device of the user using a compass;

determining, using at least one of an accelerometer or a gyroscope, an orientation of the client device relative to an upright position of the client device for the user;

calibrating, by the one or more computing devices, the compass with respect to the identified bearing to provide an updated bearing reading, based on the determined orientation of the client device relative to the upright position of the client device for the user;

determining, by the one or more computing devices, a location of the client device;

mapping, by the one or more computing devices, the updated bearing reading and the determined location to a road graph to determine a direction of travel along a particular road from the updated bearing reading and the determined location;

determining, by the one or more computing devices, an optimal route from a plurality of routes, corresponding to walking directions for the user, from the determined location to the destination, using the updated bearing reading and determined location as mapped to the road graph such that the optimal route includes traveling along the particular road in the determined direction of travel and eliminates one or more routes that require initial travel in a direction other than the determined direction of travel; and

displaying, by the one or more computing devices, the optimal route from the determined location to the destination.

2. The method of claim 1, further comprising determining the route by using the updated bearing reading to identify a direction of travel along a road from the road graph.

3. The method of claim 2, further comprising:

identifying the road as a two way street separated by a median from the road graph; and

eliminating one or more routes that require the client device to travel on the side of the road contrary to the travel bearing.

4. The method of claim 2, further comprising identifying the most efficient route by identifying a next turn off of the road in the identified direction of travel.

5. The method of claim 1, further comprising identifying the bearing using the compass in response to a determination that the client device cannot obtain a bearing by a location extrapolation process.

7. The method of claim 1, wherein the orientation of the client device is determined to be upside-down relative to an upright position of the user, and the updated bearing reading corresponds to a reversed value of the identified bearing.

6. A processing system for improving route finding, the processing system comprising:

a processor;

a memory coupled to the processor for storing a map application and a road graph;

a positioning element for identifying a location of the processing system;

a compass for identifying, in response to a request for walking directions for directing a user to a destination, a bearing of the processing system; and

at least one of an accelerometer or a gyroscope for determining an orientation of the processing system relative to an upright position of the processing system for the user,

wherein the processor calibrates the compass with respect to the identified bearing to provide an updated bearing reading, based on the determined orientation of the processing system relative to the upright position of the processing system for the user, and

wherein the map application is managed by the processor and is configured to receive the location from the positioning element and the updated bearing reading, to map the position and the updated bearing reading to the road graph to determine a direction of travel along a particular road from the updated bearing reading and the determined location, and to determine the most efficient route from a plurality of routes, corresponding to walking directions for the user, to the destination, based on the position and updated bearing reading as mapped to the road graph such that the optimal route includes traveling along the particular road in the determined direction of travel and eliminates one or more routes that require initial travel in a direction other than the determined direction of travel; and

a display for displaying the most efficient route from the determined location to the destination.

8. The processing system of claim 6, wherein the processor determines the route by using the updated bearing reading to identify a direction of travel along a road from the road graph.

9. The processing system of claim 8, wherein the processor identifies the road as a two way street separated by a median from the road graph, and eliminates one or more routes that require the client device to travel on the side of the road contrary to the travel bearing.

10. The processing system of claim 6, wherein the most efficient route is determined by identifying a next turn off of the road in the identified direction of travel.

11. The processing system 6, wherein the bearing is identified using the compass in response to a determination that the client device cannot obtain a bearing by a location extrapolation process.

12. A non-transitory computer readable storage medium containing instructions that, when executed by a processor, cause the processor to perform a method comprising:

receiving a request for walking directions, for directing a user to a destination;

identifying, in response to the received request, a bearing of a client device of the user using a compass;

determining, using at least one of an accelerometer or a gyroscope, an orientation of the client device relative to an upright position of the client device for the user;

calibrating the compass with respect to the identified bearing to provide an updated bearing reading, based on the determined orientation of the client device relative to the upright position of the client device for the user;

determining a location of the client device;

mapping the updated bearing reading and the determined location to a road graph to determine a direction of travel along a particular road from the updated bearing reading and the determined location;

determining a most efficient route from a plurality of routes, corresponding to walking directions for the user, from the determined location to the destination, using the updated beating reading and determined location as mapped to the road graph such that the optimal route includes traveling along the particular road in the determined direction of travel and eliminates one or more routes that require initial travel in a direction other than the determined direction of travel; and

displaying the most efficient route from the determined location to the destination.

13. The non-transitory computer readable storage medium of claim 12, further comprising determining the most efficient route by using the updated beating reading to identify a direction of travel along a road from the road graph.

14. The non-transitory computer readable storage medium of claim 13, further comprising:

identifying the road as a two way street, separated by a median, from the road graph; and

eliminating one or more routes that require the client device to travel on the side of the road contrary to the travel bearing.

15. The non-transitory computer readable storage medium of claim 12, further comprising determining the most efficient route by identifying a next turn off of the road in the identified direction of travel.

16. The non-transitory computer readable storage medium of claim 12, further comprising identifying the bearing using the compass in response to a determination that the client device cannot obtain a bearing by a location extrapolation process.