System and method for multi-resolution routing

• US 8,374,792 B2
• Filed: 07/30/2010
• Issued: 02/12/2013
• 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
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): MOTT, ADAM R
• Application Number:
  US12/847,845
• Publication Number:
  US 20120029804A1
• Time in Patent Office: 928 Days
• Field of Search: None
• US Class Current: 701/533
• 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:

one or more computer processors configured to perform the functions of;

a map generator that generates maps at multiple detail levels; and

a route generator that generates a complete higher detail route based upon one or more complete lower detail routes,

wherein the route generator favors candidate complete higher detail routes that fall within a search envelope surrounding the complete lower detail routes, and

the one or more computer processors are configured to display the generated maps and generated routes to a user on a display device.

2. The system of claim 1, wherein the route generator uses a graph search biased toward nodes that are closer to the complete lower detail routes.

3. The system of claim 1, wherein the search envelope'"'"'s dimensions depend on a current detail level.

4. The system in claim 1, further comprising a heuristic generator that favors the candidate complete higher detail routes that are near the complete lower detail routes.

5. The system of claim 1, wherein the map generator enlarges map features at lower detail levels to improve routing.

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

one or more computer processors configured to perform the steps of;

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

generating by a route generator a complete higher detail route based upon one or more complete lower detail routes,

wherein the route generator favors candidate complete higher detail routes that fall within a search envelope surrounding the complete lower detail routes, and

the one or more computer processors are configured to display the generated maps and generated routes to a user on a display device.

7. The method of claim 6, wherein the route generator uses a graph search biased toward nodes that are closer to the complete lower detail routes.

8. The method of claim 6, wherein the search envelope'"'"'s dimensions depend on a current detail level.

9. The method of claim 6, wherein a heuristic generator favors the candidate complete higher detail routes that are near the complete lower detail routes.

10. The method of claim 6, wherein the map generator enlarges map features at lower detail levels to improve routing.

11. 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 detail levels; and

generating by a route generator a complete higher detail route based upon one or more complete lower detail routes,

wherein the route generator favors candidate complete higher detail routes that fall within a search envelope surrounding the complete lower detail routes, and

the one or more computer processors are configured to display the generated maps and generated routes to a user on a display device.

12. The computer program product of claim 11, wherein the route generator uses a graph search biased toward nodes that are closer to the complete lower detail routes.

13. The computer program product of claim 11, wherein the search envelope'"'"'s dimensions depend on a current detail level.

14. The computer program product of claim 11, wherein a heuristic generator favors the candidate complete higher detail routes that are near the complete lower detail routes.

15. The computer program product of claim 11, wherein the map generator enlarges map features at lower detail levels to improve routing.