Method and apparatus of route guidance

• US 9,267,803 B2
• Filed: 12/07/2011
• Issued: 02/23/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:
  US13/313,628
• Publication Number:
  US 20120143504A1
• Time in Patent Office: 1,539 Days
• Field of Search: 701532-533, 701/410, 701/431, 701/454, 701/201, 701/209, 701/412, 701/420, 709/232, 709/239, 709/217, 709/219, 340/995.1, 340/995.12, 340/995.13, 455/421, 455/422.1, 455/456.1, 345/630, 345/520, 345/522, 707/999.107, 707/E17.018, 707/E17.142, 712/207, 712/205, 711/118, 711/E12.017
• 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, a plurality of map partition data from a remote computer at a first point in time, each of the plurality of map partition data being encoded with information for generating driving directions for a first area corresponding to one or more map image tiles, wherein the first area includes a first sub-map area and a second sub-map area, wherein it is known that network connectivity in the first sub-map area is weaker than network connectivity in the second sub-map area, and more map partition data is prefetched for the first sub-map area than for the second sub-map area based on the respective connectivity;

storing the plurality of map partition data in a memory;

determining whether the remote computer is accessible;

assembling, with the processor, map data representing a geographic region, the map data being an assemblage of map partition data of the stored plurality of map partition data stitched together to form a larger map from the one or more map image tiles if it is determined that the remote computer is not accessible; and

generating, with the processor, a route to a destination using the map data.

2. The method of claim 1, 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.

3. The method of claim 2, 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.

4. The method of claim 1, wherein the plurality of map partition data is a first plurality and the method further comprises:

fetching, with the processor, a second plurality of map partition data different from the first plurality from the remote computer at a second point in time later than the first point in time, each of the second plurality of map partition data being encoded with information for generating driving directions for a second area corresponding to one or more map image tiles, wherein the second area extends a predetermined radius from a current position of a user device;

wherein the second area partially intersects with the first area.

5. The method of claim 1, wherein each of the plurality of map partition data is further encoded with information to stitch the plurality of map partition data to each other so as to assemble the map data.

6. The method of claim 1, wherein generating the route comprises applying a routing algorithm to the map data.

7. The method of claim 1, wherein assembling the map data comprises constructing a graph.

8. The method of claim 7, wherein in the assembling the map data, each of the plurality of map partition data is structured as a different portion of the graph.

9. An apparatus comprising:

a memory caching map partition data;

a processor in communication with the memory so as to process the map partition data in accordance with instructions, the processor configured to;

prefetch a plurality of map partition data from a remote computer at a first point in time, each of the plurality of map partition data being encoded with information for generating driving directions for a first area corresponding to one or more map image tiles, wherein the first area includes a first sub-map area and a second sub-map area, wherein it is known that network connectivity in the first sub-map area is weaker than network connectivity in the second sub-map area, and more map partition data is prefetched for the first sub-map area than for the second sub-map area based on the respective connectivity;

store the plurality of map partition data in the memory;

determine whether the remote computer is accessible;

retrieve the stored plurality of map partition data from the memory, if it is determined that the remote computer is not accessible;

assemble map data representing a geographic region, the map data being an assemblage of map partition data of the stored plurality of map partition data stitched together to form a larger map from the one or more map image tiles; and

generate a route to a destination using the map data; and

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

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 processor is further configured to prefetch a second plurality of map partition data 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 in generating the route, the processor is configured to generate a shortest route or a least congested route.

13. The apparatus of claim 9, wherein the route is generated by applying one of Dijkstra'"'"'s routing algorithm, Floyd-Warshall'"'"'s routing algorithm, and Bellman-Ford'"'"'s routing algorithm to the map data.

14. The apparatus of claim 9, wherein the map data is structured as a graph.

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 plurality of map partition data from a remote computer at a first point in time, each of the plurality of map partition data being encoded with information for generating driving directions for a first area corresponding to one or more map image tiles, wherein the first area includes a first sub-map area and a second sub-map area, wherein it is known that network connectivity in the first sub-map area is weaker than network connectivity in the second sub-map area, and more map partition data is prefetched for the first sub-map area than for the second sub-map area based on the respective connectivity;

storing the plurality of map partition data in a memory;

determining whether the remote computer is accessible;

assembling map data representing a geographic region, the map data being an assemblage of map partition data of the stored plurality of map partition data stitched together to form a larger map from the one or more map image tiles if it is determined that the remote computer is not accessible; 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 generating the route comprises generating a shortest route or a least congested route.

19. The non-transitory computer readable medium of claim 15, wherein each of the plurality of map partition data is further encoded with information to stitch the plurality of map partition data to each other so as to assemble the map data.

20. The method of claim 15, wherein generating the route comprises applying a routing algorithm to the map data.

21. The non-transitory computer readable medium of claim 15, wherein assembling the map data comprises constructing a graph.

22. The non-transitory computer readable medium of claim 21, wherein each of the plurality of map partition data is structured as a different portion of the graph.