On-demand shortcut computation for routing

Patent metadata

Field	Value
Publication number	US-10060753-B2
Application number	US-201615239567-A
Country	US
Kind code	B2
Filing date	Aug 17, 2016
Priority date	Aug 17, 2016
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

Computing shortcuts for cells used in cell-based routing in a mobile navigation system re-computes shortcuts based on updated traffic conditions and estimated time of arrival (ETA) at an entry to the cell. Shortcuts are computed on demand and stored in a last recently used (LRU) cache. Shortcuts are computed using cost functions stored in the LRU cache. Shortcuts are computed in accordance with metadata stored in the LRU cache. Shortcuts are optionally based on predicted ETA and future traffic conditions to provide accurate estimates of best cost routes.

First claim

What is claimed is:

1. A computer-implemented method for generating minimum cost routes for a location-based navigation application operating on a device, the method comprising:
receiving, by a data processing system, a request to partition a map associated with a location-based navigation application into cells having respective numbers of intersections, each cell having entries into and exits from the cell;
receiving, by the data processing system, a request for a shortcut for a selected one of the cells;
determining, by the data processing system, that the requested shortcut is not in a last recently used (LRU) cache of shortcuts maintained for the cells into which the map is partitioned, each shortcut representing a minimum cost path between an entry and an exit of each cell based on a combination of any one or more of a cost function or a traffic configuration;
generating, by the data processing system, the shortcut based on the combination of any one or more of the cost function or the traffic configuration; and
outputting, by the data processing system, the shortcut to a device.

2. The computer-implemented method as in claim 1 , further comprising:
generating, by the data processing system based on metadata for the selected one of the cells, the shortcut according to the metadata to reduce a computational cost of generating the shortcut.

3. The computer-implemented method of claim 2 , wherein the metadata represents a characteristic of each cell that obviates the need for a specialized cost function for generating shortcuts.

4. The computer-implemented method of claim 3 , wherein the characteristic of each cell is any one or more of an absence of tolls or an absence of restricted access roads to be avoided that obviates the need for the specialized cost function for generating shortcuts that avoid any one or more of tolls or restricted access roads.

5. The computer-implemented method of claim 3 further comprising:
determining an estimated time of arrival (ETA) at the entry to the cell; and
generating the shortcut based on the traffic configuration corresponding to a traffic report for the ETA.

6. The computer-implemented method of claim 1 further comprising:
querying the LRU using a key composed of identifiers of the cell and identifiers of any one or more of: the cost function, and the traffic configuration for which the shortcut is requested; and
returning from the LRU cache a value matched to the key, the value representing the shortcut.

7. The computer-implemented method as in claim 1 , wherein the any one or more cost functions maintained in the LRU for each cell includes any of a standard cost function or a specialized cost function, wherein the standard cost function returns shortcuts without regard to specialized costs and the specialized cost function returns shortcuts that avoid specialized costs, the specialized costs including any one or more of tolls or restricted access roads.

8. A system for location-based navigation, the system comprising:
a server operating a navigation service in communication with devices, the server having a processor configured to partition a navigation map into cells having respective numbers of intersections, each cell having entries into and exits from the cell, the server having access to a last recently used (LRU) cache for storing shortcuts maintained for the cells into which the map is partitioned, each shortcut representing a minimum cost path between an entry and an exit of each cell based on a combination of any one or more of a cost function or a traffic configuration, wherein the server is further configured to:
receive a request fora shortcut for a selected cell from the LRU cache;
determine that the requested shortcut is not in the LRU cache;
generate the shortcut based on the combination of any one or more of the cost function or the traffic configuration; and
output, by the server, the shortcut to a device.

9. The system as in claim 8 , wherein the server is further configured to:
generate, based on metadata for the selected cell, the shortcut according to the metadata to reduce a computational cost of generating the shortcut.

10. The system as in claim 9 , wherein the metadata represents a characteristic of each cell that obviates the need for a specialized cost function for generating shortcuts.

11. The system as in claim 10 , wherein the characteristic of each cell is any one or more of an absence of tolls or an absence of restricted access roads to be avoided that obviates the need for the specialized cost function for generating shortcuts that avoid any one or more of tolls or restricted access roads.

12. The system as in claim 10 further comprising, wherein the server is further configured to:
determine an estimated time of arrival (ETA) at the entry to the cell; and
generate the shortcut based on the traffic configuration corresponding to a traffic report for the ETA.

13. The system as in claim 8 , wherein the server is further configured to:
query the LRU cache using a key composed of identifiers of the cell and identifiers of any one or more of: the cost function, or the traffic configuration for which the shortcut is requested; and
return from the LRU cache a value matched to the key, the value representing the shortcut.

14. The system as in claim 8 , wherein the any one or more cost functions maintained in the LRU for each cell includes any of a standard cost function or a specialized cost function, wherein the standard cost function returns shortcuts without regard to specialized costs and the specialized cost function returns shortcuts that avoid specialized costs, the specialized costs including any one or more of tolls or restricted access roads.

15. At least one computer-readable non-transitory storage medium including instructions that, when executed on a processor, cause the processor to:
receive a request to partition a map associated with a location-based navigation application into cells having respective numbers of intersections, each cell having entries into and exits from the cell;
receive a request for a shortcut for a selected one of the cells from a last recently used (LRU) cache of shortcuts maintained for the cells into which the map is partitioned, each shortcut representing a minimum cost path between an entry and an exit of each cell based on a combination of any one or more of a cost function or a traffic configuration;
determine that the requested shortcut is not in the LRU cache;
generate the shortcut based on the combination of any one or more of the cost function or the traffic configuration;
output the shortcut to a device.

16. The at least one computer-readable non-transitory storage medium as in claim 15 , the instructions further causing the processor to:
generate, based on metadata for the selected cell, the shortcut according to the metadata to reduce a computational cost of generating the shortcut.

17. The at least one computer-readable non-transitory storage medium as in claim 16 , wherein the metadata represents a characteristic of each cell that obviates the need for a specialized cost function for generating shortcuts.

18. The at least one computer-readable non-transitory storage medium as in claim 17 , wherein the characteristic of each cell is any one or more of an absence of tolls or an absence of restricted access roads to be avoided that obviates the need for the specialized cost function for generating shortcuts that avoid any one or more of tolls or restricted access roads.

19. The at leas

Assignees

• Apple Inc

Inventors

• Delling Daniel
• SCHIEFERDECKER Dennis
• Sommer Christian

Classifications

• H04L67/42

  Electricity · mapped topic

• G01C21/3415 Primary

  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 title

• G08G1/096838

  where the user preferences are taken into account or the user selects one route out of a plurality · CPC title

• G08G1/096844

  where the complete route is dynamically recomputed based on new data · CPC title

• G08G1/096883

  where input information is obtained using a mobile device, e.g. a mobile phone, a PDA · CPC title