System and Method for Multi-Resolution Routing

• US 20120029804A1
• Filed: 07/30/2010
• Published: 02/02/2012
• Est. Priority Date: 07/30/2010
• Status: Active Grant

• Current Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Original Assignee: Primordial, Inc. (Polaris Inc.)
• Inventors: White, Dane, Freed, Erik
• Granted Patent: US 8,374,792 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A system, method and computer program product for efficiently generating on- and off-road travel routes using multi-resolution maps including a map generator (108), map database (106), route generator (100), heuristic generator (102), and search envelope factor generator (104). The map generator (108) converts input raster and vector map data into output multi-resolution raster map data suitable for routing and stores it in the map database (106). The route generator (100) uses the map database (106) to produce a route at a coarse zoom level and then regenerate the route at progressively higher zoom levels. The heuristic generator (102) penalizes high resolution routes that deviate too far from one or more low resolution routes. The search envelope factor generator (104) computes this penalty based on the distance from a given search graph node to the low resolution routes.

Claims

1. A system for generating a travel route comprising:

a map generator for generating maps at multiple zoom levels; and

a route generator for generating a high resolution route based upon one or more low resolution routes determined from the maps generated by the map generator.

2. The system in claim 1, wherein the route generator biases the high resolution route in favor of the low resolution routes with a bias that varies with distance to the low resolution routes.

3. The system in claim 1, wherein the route generator'"'"'s graph search is biased toward nodes that are closer to the low resolution routes.

4. The system in claim 1, wherein the route generator favors candidate high resolution routes that fall within a search envelope surrounding the low resolution routes.

5. The system in claim 4, wherein the search envelope'"'"'s dimensions depend on the current zoom level.

6. The system in claim 1, further comprising a heuristic generator that favors candidate high resolution routes that are near the low resolution routes.

7. The system in claim 6, wherein the heuristic generator biases the high resolution route in favor of the low resolution routes with a bias that varies with distance to the low resolution routes.

8. The system in claim 6, wherein the heuristic generator'"'"'s graph search is biased toward nodes that are closer to the low resolution routes.

9. The system in claim 6, wherein the heuristic generator favors candidate high resolution routes that fall within a search envelope surrounding the low resolution routes.

10. The system in claim 9, wherein the search envelope'"'"'s dimensions depend on the current zoom level.

11. The system in claim 1, wherein the map generator enlarges map features at lower zoom levels to improve routing.

12. The system in claim 11, wherein the route generator biases the high resolution route in favor of the low resolution routes with a bias that varies with distance to the low resolution routes.

13. The system in claim 11, wherein the route generator'"'"'s graph search is biased toward nodes that are closer to the low resolution routes.

14. The system in claim 11, wherein the route generator favors candidate high resolution routes that fall within a search envelope surrounding the low resolution routes.

15. The system in claim 14, wherein the search envelope'"'"'s dimensions depend on the current zoom level.

16. A method for generating a travel route, the method comprising:

generating by a map generator maps at multiple zoom levels; and

generating by a route generator a high resolution route based upon one or more low resolution routes determined from the maps generated by the map generator.

17. The method in claim 16, wherein the route generator biases the high resolution route in favor of the low resolution routes with a bias that varies with distance to the low resolution routes.

18. The method in claim 16, wherein the route generator uses a graph search biased toward nodes that are closer to the low resolution routes.

19. The method in claim 16, wherein the route generator favors candidate high resolution routes that fall within a search envelope surrounding the low resolution routes.

20. The method in claim 16, wherein the map generator enlarges map features at lower zoom levels to improve routing.

21. A computer program product for generating a travel route and including one or more computer readable instructions embedded on a tangible computer readable medium and configured to cause one or more computer processors to perform the steps of:

generating by a map generator maps at multiple zoom levels; and

generating by a route generator a high resolution route based upon one or more low resolution routes determined from the maps generated by the map generator.

22. The computer program product in claim 21, wherein the route generator biases the high resolution route in favor of the low resolution routes with a bias that varies with distance to the low resolution routes.

23. The computer program product in claim 21, wherein the route generator uses a graph search biased toward nodes that are closer to the low resolution routes.

24. The computer program product in claim 21, wherein the route generator favors candidate high resolution routes that fall within a search envelope surrounding the low resolution routes.

25. The computer program product in claim 21, wherein the map generator enlarges map features at lower zoom levels to improve routing.