METHOD AND APPARATUS OF ROUTE GUIDANCE

• US 20120143504A1
• Filed: 12/07/2011
• Published: 06/07/2012
• Est. Priority Date: 12/07/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ito, Keith, Siliski, Michael, Kalai, Iljya, Ulanov, Andrey Yuryevich, Miller, Andrew Tesch
• Granted Patent: US 9,267,803 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• 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, each of the plurality of map partition data being encoded with information for generating driving directions;

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 the plurality of map partition data if it is determined that the remote computer is not accessible; 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, 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 route is a shortest route or a least congested route.

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 the route is generated by applying a routing algorithm to the map data.

7. The method of claim 1, wherein the map data structure is a graph.

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

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 plurality of map partition data from a remote computer, each of the plurality of map partition data being encoded with information for generating driving directions;

storing the plurality of map partition data in a memory;

determining whether the remote computer is accessible;

retrieving the plurality of map partition data from the memory, 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 the plurality of map partition data; 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 instructions further comprise prefetching 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 the route is a shortest route or a least congested route.

13. The apparatus of claim 9, wherein the route is generated by applying a routing algorithm to the map data.

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

15. A method for transmitting map data, comprising:

generating, with a processor, a first route to a first destination;

the processor receiving a request from a client device for a plurality of map partition data that are portions of the map data representing a geographic region, the map data usable for generation of a second route toward a second destination different than the first generation;

the processor retrieving the plurality of map partition data; and

the processor transmitting the plurality of map partition data to the client device.

16. The method for supplying map data of claim 15, wherein the map data is structured as a graph.

17. The method for supplying map data of claim 15, wherein the plurality of map partition data is transmitted to the client device in a wire format.

18. A system comprising:

a memory storing at least one module and 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 in the at least one module;

the at least one module having instructions comprising;

generating a route to a first destination;

receiving a request from a client device for a plurality of map partition data that are portions of the map data representing a geographic region, the map data usable for route generation toward a second destination different than the first destination;

retrieving the plurality of map partition data; and

transmitting the plurality of map partition data to the client device.

19. The system of claim 18, wherein the geographic region includes potential route segments surrounding the current position of a user and a segment of the best route.

20. The system of claim 19, wherein the plurality of map partition data is transmitted to the client device in a wire format.

21. A method of displaying a route on a device comprising:

transmitting a start location and a destination location to a first computer over a network, the first computer having access to data identifying a first set of road locations;

receiving, from the first computer, a second set of road locations selected from a subset of the first set, wherein the second set of road locations contains a first route comprising a contiguous series of road locations between the start location and the destination location, and further contains additional road locations that are within a geographic region proximate to the first route; and

determining, with a processor, a second route of contiguous road locations based on the road locations contained in the second set when data identifying a current location of the device indicates that the current location of the device is different than the road locations in the first route, the second route being determined when the device is unable to receive the identification of road locations from the first computer.

22. The method of claim 21, wherein the current location of the device is identified as it changes over time.

23. The method of claim 21, wherein the second route is not equal to the first route.

24. The method of claim 21, wherein the geographic region covers a predetermined distance within the start location, the destination location, or the contiguous series of road locations.

25. The method of claim 21 further comprising displaying the second route.

26. The method of claim 25 wherein a road location of the second set is displayed to the user when the device is proximate to the road location.

27. A method of route guidance, comprising:

transmitting from a mobile device to a first computer a request for a route from a start location to a destination location;

receiving on the mobile device from the first computer a contiguous series of road locations defining the route from the start location to the destination location;

receiving on the mobile device from the first computer a set of additional road locations that are within a geographic region proximate to the route;

providing route guidance on the mobile device while the mobile device is moving along the route;

generating on the mobile device a new route based at least in part on the set of additional road locations if the mobile device determines that it has deviated from said contiguous series of road locations; and

providing route guidance on the mobile device while the mobile device is moving along the new route.