Method and apparatus of route guidance

• US 9,404,759 B2
• Filed: 12/14/2015
• Issued: 08/02/2016
• Est. Priority Date: 12/07/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kalai, Iljya, Ito, Keith, Ulanov, Andrey Yuryevich, Miller, Andrew Tesch, Siliski, Michael
• Primary Examiner(s): Nguyen, Cuong H
• Application Number:
  US14/968,109
• Publication Number:
  US 20160102988A1
• Time in Patent Office: 232 Days
• Field of Search: 701/428, 701532-533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: H04L 67/025 for remote control or remote monitoring of applications
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

Systems and methods of route guidance on a user device are provided. In one aspect, a system and method transmit partitions of map data to a client device. Each map partition may contain road geometries, road names, road network topology, or any other information needed to provide turn-by-turn navigation or driving directions within the partition. Each map partition may be encoded with enough data to allow them to be stitched together to form a larger map. Map partitions may be fetched along each route to be used in the event of a network outage or other loss of network connectivity. For example, if a user deviates from the original route and a network outage occurs, the map data may be assembled and a routing algorithm may be applied to the map data in order to direct the user back to the original route.

Claims

1. A method of generating a route to a destination comprising:

prefetching, with a processor of a user device, a first plurality of map partition data for a first area from a remote computer at a first point in time, each of the first plurality of map partition data being encoded with information for generating driving directions;

determining, at a second point in time later than the first point in time, whether the remote computer is accessible;

if the remote computer is accessible, fetching, with the processor, a second plurality of map partition data for a second area from the remote computer at the second point in time, the second plurality of map partition data being encoded with information for generating driving directions, the second area being within a predetermined distance from a current location of the user device and partially intersecting the first area;

storing the first plurality of map partition data and the second plurality of map partition data in a memory;

determining, at a third point in time later than the second point in time, whether the remote computer is accessible;

if it is determined that the remote computer is not accessible, assembling map data representing a geographic region, the map data being an assemblage of at least one of the first plurality of map partition data and the second plurality of map partition data stored in the memory; and

generating a route to a destination using the map data.

2. The method of claim 1, wherein the geographic region is based on the current position of the user device or a segment of the route, the geographic region including segments that are not on the generated route.

3. The method of claim 2, wherein the second plurality of map partition data is fetched if it is determined that the user device has traveled beyond an area surrounding one location and into an area surrounding another location.

4. The method of claim 1, wherein the first area includes a contiguous series of road between the start location and the destination location, and the second area includes a contiguous series of road within the predetermined distance from the current location of the user device.

5. The method of claim 1, wherein the second area is larger than the first area when network connectivity in the second area is known to be weaker than network connectivity in the first area.

6. The method of claim 1, wherein the first area includes geographic areas from at least one of a user'"'"'s travel history, search history, personal profile, and calendar entries.

7. The method of claim 1, wherein the first plurality of map partition data is prefetched automatically when the user device is turned on and is in an area with network access.

8. The method of claim 1, further comprising receiving input selecting the first area.

9. An apparatus comprising:

a memory capable of caching a plurality of map partition data;

a processor in communication with the memory so as to process the plurality of map partition data in accordance with instructions; and

a display in communication with, and displaying information received from, the processor;

the instructions comprising;

prefetching a first plurality of map partition data for a first area from a remote computer at a first point in time, each of the first plurality of map partition data being encoded with information for generating driving directions;

determining, at a second point in time later than the first point in time, whether the remote computer is accessible;

if the remote computer is accessible, fetching a second plurality of map partition data for a second area from the remote computer at the second point, the second plurality of map partition data being encoded with information for generating driving directions, the second area being within a predetermined distance from a current location of the apparatus and partially intersecting the first area;

storing the first plurality of map partition data and the second plurality of map partition data in a memory;

determining, at a third point in time later than the second point in time, whether the remote computer is accessible;

if it is determined that the remote computer is not accessible, retrieving map data of the first plurality of map partition data and the second plurality of map partition data from the memory;

assembling the map data representing a geographic region; and

generating a route to a destination using the map data.

10. The apparatus of claim 9, wherein the geographic region is either a predetermined range from a current position of the apparatus or a predetermined range from a segment of the route.

11. The apparatus of claim 10, wherein the second plurality of map partition data is fetched if it is determined that the apparatus has traveled beyond an area surrounding one location and into an area surrounding another location.

12. The apparatus of claim 9, wherein the first area includes a contiguous series of road between the start location and the destination location, and the second area includes a contiguous series of road within the predetermined distance from the current location of the user device.

13. The apparatus of claim 9, wherein the second area is larger than the first area when network connectivity in the second area is known to be weaker than network connectivity in the first area.

14. The apparatus of claim 9, wherein the first plurality of map partition data is prefetched automatically when the user device is turned on and is in an area with network access.

15. A non-transitory computer readable medium storing instructions executable by a computing device to perform a method of generating a route to a destination, the method comprising:

prefetching a first plurality of map partition data for a first area from a remote computer at a first point in time, each of the first plurality of map partition data being encoded with information for generating driving directions;

determining, at a second point in time later than the first point in time, whether the remote computer is accessible;

if the remote computer is accessible, fetching a second plurality of map partition data for a second area from the remote computer at the second point in time, the second plurality of map partition data being encoded with information for generating driving directions, the second area being within a predetermined distance from a current location of the user device and partially intersecting the first area;

storing the first plurality of map partition data and the second plurality of map partition data in a memory;

determining, and a third point in time later than the second point in time, whether the remote computer is accessible;

if it is determined that the remote computer is not accessible, retrieving map data of the first plurality of map partition data and the second plurality of map partition data from the memory;

assembling the map data representing a geographic region; and

generating a route to a destination using the map data.

16. The non-transitory computer readable medium of claim 15, wherein in the assembling the map data representing the geographic region, the geographic region is based on the current position of the user device or a segment of the route, the geographic region including segments that are not on the generated route.

17. The non-transitory computer readable medium of claim 16, the method further comprising prefetching a second plurality of map partition data if it is determined that the user device has traveled beyond an area surrounding one location and into an area surrounding another location.

18. The non-transitory computer readable medium of claim 15, wherein the first area includes a contiguous series of road between the start location and the destination location, and the second area includes a contiguous series of road within the predetermined distance from the current location of the user device.

19. The non-transitory computer readable medium of claim 15, wherein the second area is larger than the first area when network connectivity in the second area is known to be weaker than network connectivity in the first area.

20. The non-transitory computer readable medium of claim 15, wherein the first plurality of map partition data is prefetched automatically when the user device is turned on and is in an area with network access.